Heaps and Priority Queues
85 / 170Heaps and Priority QueuesLesson 5 of 8About 68 min
One candidate from each source in a heap, and the answer comes out in order.
A common design version of this: several users each have a list of posts in reverse chronological order, and you must produce the newest few across all of them.
Whatever the domain, the same three things have to be right. Seed the heap with one entry per source. Give each entry enough to continue with. Replace what you pop from the source it came from.
import heapq sources = [[1, 4, 5], [1, 3, 4], [2, 6]] heap = [(source[0], index, 0) for index, source in enumerate(sources)]heapq.heapify(heap)print("one candidate per source:", sorted(heap)) value, which, position = heapq.heappop(heap)print("smallest overall:", value, "came from source", which)print("so the replacement to push is", sources[which][position + 1])Merging k sorted sources holding n items in total, using a heap with one entry per source. Give the time and the extra space beyond the output.
heap = [(source[0], index, 0) for index, source in enumerate(sources) if source]heapq.heapify(heap)while heap: value, source_index, position = heapq.heappop(heap) emit(value) if position + 1 < len(sources[source_index]): heapq.heappush(heap, (sources[source_index][position + 1], source_index, position + 1))Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
You solved this in Unit 7 by pairing lists and merging two at a time. Build it again with a heap holding one node from each list. Same complexity, completely different shape, and having both is the point.