Top K and merging sorted lists with heapq

Why it matters

"Find the K largest" and "merge K sorted lists" are two of the most common heap problems in interviews. They also appear in real systems. A website shows the ten most viewed pages. A log viewer combines many sorted log files into one timeline. A map app lists the three closest drivers. Each of these asks for a small part of a large set, or for one sorted result built from several sorted inputs.

Both problems rely on the same trick. Keep a heap that holds only what you might still need, and let the heap throw away everything else. In this lesson you will see that trick in four places: for the K largest numbers, for the K most frequent words, for the K closest points, and for merging K sorted lists. You will also see why the heap is the tool that makes each one fast.

The problem with sorting everything

Suppose you have a million numbers and want the ten largest. The obvious plan is to sort all of them, then read the last ten. In Python, sorted(numbers)[-10:] does exactly that, and it is a fine plan for small lists. Sorting a million numbers costs about n log n steps, which is around twenty million steps. That is wasteful. You only need ten numbers, and you do not care about the order of the other 999,990.

Big-O notation, written as O(...), describes how the number of steps grows as the input grows. n means the size of the input, and log means the logarithm, which grows very slowly. The lesson uses it to compare plans.

A heap can do much better. The idea is to keep a small heap that always holds the best candidates seen so far, and to throw away anything that cannot make the final list. The total work becomes n steps of checking, each costing log K. When K is ten, log K is about three. Compare that with log n, which is about twenty. The saving is large.

The method also works on a stream. A stream is data that arrives one piece at a time, and you cannot store all of it. A heap of size K keeps the answer while the stream flows past. That is why these patterns matter for logs, sensors and network traffic.

The tool in Python: heapq

A heap is a structure that gives fast access to the smallest value. Python does not have a heap type in its basic set of tools. The standard library has a module called heapq that works on an ordinary list. A module is a file of ready-made code that you load with import.

Here is how the list works. The smallest value is always at index 0, which is the first position. Index 0 is called the top of the heap. The other values are arranged so that the top stays the smallest, but the rest of the list is not sorted. The functions you need are:

• heapq.heappush(heap, x) adds x to the heap.
• heapq.heappop(heap) removes the smallest value and returns it.
• heap[0] reads the smallest value without removing it.

The functions are named heappush and heappop because they work on a heap. A heap that holds the smallest value at the top is called a min-heap. heapq only makes min-heaps. A max-heap keeps the largest value on top, and you need one for some problems. The usual trick is to store negated numbers. Negating a number flips its sign, so 8 becomes -8. The smallest negated value is the largest original value, so a min-heap of negated numbers acts as a max-heap.

Change the list in the code to try your own numbers. The program prints the heap list, the smallest value, the values in pop order, and then the largest value using the negation trick.

The output is:

heap list: [1, 3, 8, 5]
smallest: 1
pop order: [1, 3, 5, 8]
largest: 8

The heap list is not sorted. [1, 3, 8, 5] is a valid heap, because each value is smaller than the values below it. Only index 0 is guaranteed to be the smallest. Each heappop takes the top out and rearranges the rest, so the values come out in sorted order.

If you know Java, heapq is the closest match to PriorityQueue. Two differences matter here. heapq has only a min-heap, and it has no comparator argument, so you change the order by changing the values you store.

Pattern 1: the K largest with a min-heap

Here is the surprising part. To find the K largest numbers, use a min-heap of size K, not a max-heap. That sounds backward at first, so take a moment with it.

Think of a leaderboard with K seats. The seats are filled by the best scores so far. The lowest score on the board sits at the top of a min-heap, because the top of a min-heap is always the smallest value. A new score can only get on the board if it beats the lowest score. When it does, the lowest score is removed, which is exactly what heappop does on the min-heap.

The steps are:

1. For each number, push it onto the min-heap.
2. If the heap now holds more than K numbers, pop once. That removes the smallest one, which is the weakest candidate.
3. At the end, the heap holds the K largest numbers. Its top, the smallest of those K, is the Kth largest overall.

The cost is O(n log K) time, because each number costs at most one push and one pop on a heap of size at most K plus one. The space is O(K), because the heap never holds more than K plus one numbers.

Why a max-heap would be wrong here: a max-heap of size K would remove its largest item, which is the best candidate. Each new number would then push out a good number, so the heap would end up holding the smallest numbers. A max-heap of all numbers works, but it needs room for all n numbers, which defeats the purpose of K. For the K smallest numbers, flip the logic: use a max-heap of size K, and remove the largest.

The program below reads the list and K from the code. It prints the top K in descending order, and the Kth largest. To try other numbers, change the list or the value of K in the last lines.

The output is:

top 3: [9, 9, 7]
kth largest: 7

Trace the input. The heap never holds more than three numbers. When 1 arrives, the heap holds 4, 9 and 1, which is three numbers, so no pop happens. When 7 arrives, the heap holds 1, 4, 7 and 9, which is four, so heappop removes 1. The heap is now 4, 7, 9. The next 9 arrives and the heap becomes 4, 7, 9, 9, so heappop removes 4. Then 2 arrives and is removed at once, because it is smaller than every value in the heap. The same happens with 6 and 3. The final heap is 7, 9, 9. Its top is 7, which is the third largest. Sorted from largest to smallest, the list is [9, 9, 7].

Notice the line kth largest: 7. It reads heap[0], which is the smallest value still in the heap. Because the heap holds the K largest, the smallest of those is the Kth largest overall. This is a common interview question: "find the kth largest element" answered with a size-K heap.

The function heapq.heappushpop(heap, x) pushes x and pops the smallest value in one call. Once the heap is full, it does the same job as the push and the pop in the loop above, in one step. The program above keeps the two steps separate because they are easier to read.

Ties and a total order

Suppose two numbers are equal and both could be the last place on the board. Which one stays? For plain numbers, it does not matter, because the printed value is the same. For objects, it does matter. If two items have the same score but different names, the answer can change depending on which one the heap removes.

The fix is to define a total order. A total order is a comparison rule that never returns "equal" for two different items. You get one by adding a second key that breaks the tie. The next two examples use that idea, and you should use it in your own work whenever the output must be exact.

Python has a built-in way to do this for tuples. A tuple is a fixed group of values in parentheses, such as (5, "ann"). Python compares two tuples item by item from the left. The first items decide the order. Only when they are equal does Python look at the second items. So (5, "ann") is smaller than (5, "bob"), and both are smaller than (6, "al").

Pattern 2: K most frequent words

Here is a problem that combines a dictionary with a heap. A dictionary is a Python structure that maps each key to a value, such as a word to its count. Count the words first. The Counter class from the collections module does this for you. It is a dictionary that counts how many times each item appears. Then find the K words with the highest counts. The counting costs O(n). The heap does the selection in O(m log K), where m is the number of different words.

Heap items are not plain numbers here, so heapq needs to know how to compare them. A class is a way to group data and the functions that work on it. The Entry class below holds a word and its count. The method named __lt__ answers the question "is this entry smaller than that one?" The heapq module calls it every time it compares two entries.

The comparison makes the weakest entry the smallest. A lower count is weaker. When two words have the same count, the alphabetically later word is weaker, so the alphabetically earlier one is kept. After the whole input has gone through, the heap holds the K best entries. Popping them gives the weakest first, so the program reverses the list to print the strongest first.

The text is the cat and the dog and the bird cat. The program prints the top 3 words with their counts.

The output is:

the 3
and 2
cat 2

The word the appears three times, so it is first. The words and and cat both appear twice. The alphabetical rule puts and before cat. The word dog appears once, and so does bird. They are weaker than the others and are removed when the heap is full.

Look at __lt__ once more. The count check comes first. The second check returns self.word > other.word, which makes the alphabetically later word the smaller one, because it is the one that loses a tie. When the heap pops them, the weaker entries come out first, which is why the program reverses the list at the end.

A common mistake is to forget this reversal, and to print the list in the order it was popped. The output then starts with the weakest word and ends with the strongest. Always check the direction of the output against the problem statement.

Counter has a method called most_common(k) that returns the top items. For this text, Counter(text.split()).most_common(3) returns [('the', 3), ('cat', 2), ('and', 2)]. Its ties come out in the order the words were first seen, so cat comes before and. That is not the alphabetical rule used in this lesson. When the tie rule must be your own, the heap is the way to get it.

The answer does not depend on the order of the input. Shuffling the words 200 times and running the program each time gave the same three entries every time. The total order is what makes this true.

Pattern 3: K closest points

The same heap works for geometric problems. Suppose you want the K points closest to the origin, the point (0, 0). Compare distances, not their square roots. The squared distance x * x + y * y gives the same order as the real distance, and it avoids the square root, which is slower to compute.

The heap is a max-heap of size K, which is the mirror of pattern 1. The top is the farthest point kept so far. A new point is added, and if the heap grows past K, the farthest point is removed. At the end, the heap holds the K closest points.

The total order here has three keys: distance, then x, then y. Each heap item is a tuple (-distance, -x, -y). Negating all three keys turns the min-heap into a max-heap under the full order. The smallest tuple is then the largest point under the order, which is the farthest, and among ties the one with the largest x and y. That is the point to remove.

Python integers have no size limit. The square of 50000 is 2500000000, and Python handles it without wrapping, so no special type is needed.

The input in the next block has three points at squared distance 1: (0, 1), (1, 0) and (0, -1). With K equal to 3, all three must be kept, and the order among them must be fixed. The tuple order defines the sort, so the output is fixed too.

The output is:

0 -1
0 1
1 0

The list comprehension [(-nx, -ny) for _, nx, ny in heap] turns each stored tuple back into a point. The underscore _ is a name for a value the code does not use. The sort call uses a key function, which gives the sort the same three-part order as the heap.

Notice what the total order does. Without the x and y checks, the three points at squared distance 1 would be tied, and the heap would keep whichever three it happened to hold. The printed answer could change if the input order changed. With the full order, the answer is always the same, because the three smallest points under the order are fixed.

K closest points by hand

The closest-points program is easy to run and hard to trace in your head, so do the trace on paper. The input has seven points and K = 3. The heap is a max-heap under the total order: distance first, then x, then y. Its top is the largest point under that order, which is the one to remove when the heap grows past three.

Read the table in order. The first three points fill the heap. After the fourth point, the heap holds four points, so the largest under the order leaves. Here that is (3, 3), which is far away with distance 18. The same happens for each new point. The farthest point in the heap is always the one removed, so the heap keeps the three closest points seen so far.

The last row is the interesting one. The final heap holds three points at distance 1: (0, 1), (1, 0) and (0, -1). These points are tied on distance, so the total order breaks the tie. Compare x first: 0 is less than 1, so the two points with x = 0 come first. Between them, (0, -1) has the smaller y, so it comes before (0, 1). The sorted output is therefore 0 -1, 0 1, 1 0, which is exactly what the program prints.

Merging K sorted lists

Now the second big problem. You have K sorted lists and want one sorted list with every value. The simplest plan merges two lists at a time. Merge the first two, then merge the result with the third, and so on. That repeats the copying of early values, and the work grows with K. With N total values, the total is O(N * K), which is slow when K is large.

The heap plan is cleaner. Every list is already sorted, so its smallest value is at its front. The smallest value overall must be one of the K fronts. Put those K fronts into a min-heap. Pop the smallest, add it to the output, and push the next value from the same list. Repeat until the heap is empty.

The heap never holds more than K values, so each push and pop costs O(log K). With N values in total, the time is O(N log K), and the extra space is O(K). This is much better than O(N * K) when K is big.

The lists in an interview are often linked lists. A linked list is a chain of small objects, called nodes. Each node holds a value and a reference called next, which points to the following node. The last node has next set to None, which is Python's word for "nothing". The next block builds that version. It uses a dummy node, which is a placeholder head that makes the code simpler. You will see below why that helps.

Step through the visualizer below to see how a linked list is built from nodes that point to the next node. Keep that picture in mind for the merge. The output list is built the same way: each step attaches one node to the end and moves the tail pointer forward.

Here is the merge in Python. The class ListNode holds a value and the next reference. The function merge_k takes a list of list heads. It pushes every head that is not None onto the heap, then repeatedly pops the smallest and attaches it to the output tail. After the pop, it pushes the node after the one just popped, if there is one. The last lines test two cases: three non-empty lists, and a list that includes an empty list and a None entry.

The heap entries are tuples of three items: the value, a tie-breaker number, and the node. Two nodes can have the same value, and Python cannot compare two ListNode objects with <. The tie-breaker makes sure the comparison never reaches the node itself. The count() function from the itertools module gives 0, 1, 2 and so on, so each entry gets a different number.

The output is:

merged: 1 2 3 4 5 6 7 8
with empty lists: -3 0 10

Trace the first case by hand. The heads are 1, 2 and 3. The heap holds {1, 2, 3}. Pop 1, attach it, and push 4, the next node of list one. The heap is now {2, 3, 4}. Pop 2, attach it, push 5. Pop 3, push 6. Pop 4, push 7. Pop 5, list two is now empty, so nothing is pushed. Pop 6, push 8. Pop 7, list one is now empty. Pop 8, and the heap is empty. The output is the eight numbers in order.

The second case has four inputs. The first is None, so the code skips it. The second is 0 10. The third is an empty list, which build() returns as None, so it is skipped too. The fourth is -3. The heap starts with 0 and -3. The output is -3 0 10.

The dummy node in merge_k is the reason the code has no special case for the first node. Without it, the first attach would need an if to set the head. With it, every attach is the same line: tail.next = node. At the end, dummy.next is the real head. The line tail.next = None is a safety step that cuts off any stale reference, although the loop already sets the last link correctly.

Python also has a built-in version for plain lists. heapq.merge(*lists) takes any number of sorted lists and returns an iterator that gives the merged values one at a time. For the first case, list(heapq.merge([1, 4, 7], [2, 5], [3, 6, 8])) gives [1, 2, 3, 4, 5, 6, 7, 8]. It uses the same heap idea inside. The hand-written version is here so that you can see the heap work on linked nodes.

What happens inside the computer

Each ListNode is a separate object in memory. An object is a block of data with its own fields. It holds the val field and the next reference. A reference is an address that points to an object. The heap does not copy the nodes. Each heap entry holds a reference to a node, so heappop returns the same node that is in the list. Attaching a node to the output changes only its next field. No values are copied. The output is built by moving references.

Because the heap holds tuples that hold references, the comparisons read the value part of each tuple. The heap list holds at most K entries at any time, so the memory for the heap is small even when the total number of values is large.

The word count by hand

Trace the word program on the same input as before: k = 3, and the words the cat and the dog and the bird cat. First the counts. the appears three times, cat two, and two, and dog and bird once each. A Counter keeps the words in the order they were first seen in a dictionary, so the program reads them as the, cat, and, dog, bird. Python dictionaries keep insertion order, so this order is the same on every run.

The table shows the heap after each push and each pop. The top of the heap is the weakest entry, so the table names it in each row.

The third row needs a closer look. When and and cat both have count 2, the tie rule makes the alphabetically later word the weaker one. cat comes after and, so cat is weaker and sits at the top. The fourth and fifth rows show the removal. Both dog and bird have count 1, which is the lowest possible here, so each one leaves as soon as the heap has four entries.

The heap ends with the 3, and 2 and cat 2. The pop order is weakest first, so the program reverses the list and prints the 3, then and 2, then cat 2. That is the expected output.

Now suppose the words came in another order, such as bird, dog, cat, and, the. Work through the table again. The final heap is still and 2, cat 2 and the 3, because the comparison is a total order. Any three entries that rank highest under the order survive, and the order itself never changes. That is why the output is the same whatever order the words arrive in.

Why a heap beats sorting, with numbers

Big-O notation is easier to feel with real numbers. Take a list of one million numbers and ask for the top 10. Sorting the whole list costs about n log2 n steps. With n equal to 1,000,000, log2 n is about 20, so sorting takes about 20 million steps. The top-K heap costs about n log2 K steps. With K equal to 10, log2 10 is about 3.3, so the heap takes about 3.3 million steps. That is roughly six times less work, from a change in one line of design.

Now take K equal to 1,000. The heap costs about n log2 1000, which is about 10 steps per number, so about 10 million steps in total. The sort is still about 20 million steps. The heap is still faster, but the gap has shrunk. This is the pattern to remember: the heap wins by a factor of about log n divided by log K. When K gets close to n, the heap does almost the same work as a sort, so the sort is then the simpler choice.

Memory tells the same story. Sorting needs the whole list in memory, and it may need a copy. The top-K heap holds at most K plus one values at a time, so it can read a stream that is too big to store. A program reading a log file of 50 gigabytes can keep the 10 largest numbers in it using a small amount of memory.

Keep one caution in mind. Python stores each number as a separate object, which uses more memory than a number in a compact array from a lower-level language. That is fine for a heap of ten items. For a heap of ten million items, the memory cost matters, and a different tool or a compact array may be better. Interviews rarely go that far, but a strong answer mentions it.

An interview conversation

A typical prompt is: "Given a stream of search queries, return the ten most frequent queries at the end." The interviewer wants three things: the right structure, the right costs, and a careful tie rule.

Start by naming the structure. Count with a dictionary or Counter, which costs O(1) per query on average. Then keep a min-heap of size ten, ordered by count, with a tie rule that you state out loud. Say the cost: O(m log 10) for m distinct queries, which is effectively O(m) because ten is a constant. Then state the space: the dictionary grows with the number of distinct queries, and the heap is constant size.

The interviewer may then say that the stream is too big for the dictionary. A good answer says that exact counts would need the dictionary, so you would switch to an approximate method. You might name a sketch structure, such as a count-min sketch, and say that it trades exactness for memory. You do not need to implement it. You need to show that you know a bound exists and what it costs.

Finish with a test plan. Name the edge cases: fewer than ten distinct queries, a tie at the tenth place, one query repeated many times, and an empty stream. A candidate who lists those cases before being asked usually leaves a strong impression.

Common mistakes and the messages they produce

Mistake 1: using a min-heap of all values and reading the top as the largest. heapq puts the smallest value on top. Pushing every number and reading heap[0] gives the smallest, not the largest. For the list [4, 9, 1], heap[0] is 1, while the largest is 9. Python gives no error for this, so the wrong answer can go unnoticed. Use a min-heap of size K for the K largest, or negate the values for a max-heap.

Mistake 2: reading the top of an empty heap. On an empty list, heap[0] raises an error. This happens when K is 0, or when fewer than one value was pushed. Python prints:

IndexError: list index out of range

Check the size first, or make sure K is at least 1.

Mistake 3: putting every node of every list into the heap at the start. That costs O(N log N) and wastes memory. Push only the K heads, then push the next node from a list only when you take its node out.

Mistake 4: forgetting that a list head can be None. An empty list is None, not an object. Reading .val of None raises an error:

AttributeError: 'NoneType' object has no attribute 'val'

Check if head is not None before you read its fields, as the merge_k code does.

Mistake 5: reading .next without a check. If the last node of a list is popped and you read node.next.val anyway, you get the same error as in mistake 4. The fix is the check if node.next is not None before you read it. A related mistake is pushing None into a heap of numbers, which raises this message:

TypeError: '<' not supported between instances of 'NoneType' and 'int'

Mistake 6: heap entries with equal values and no tie-breaker. If two heap entries are equal on the first item, Python compares the next item. For two ListNode objects with no tie-breaker, the comparison fails:

TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'

Add a number that is different for each entry, as the merge_k code does with count().

Mistake 7: sorting the whole list for top K. That works, but it is slower. Sorting costs O(n log n). Use the heap when K is much smaller than n.

Debugging walkthrough

Suppose your top-K program prints the wrong set. Start with a tiny input that you can trace by hand. Use K = 2 and the numbers 3 1 2. The answer should be 3 and 2. Print the heap after each push and each pop. If the heap holds 1 and 2 at the end, the pop is removing the wrong value. Check the sign and the direction. A max-heap of size K would keep 1 and 2 here, which is the smallest pair, so the logic is flipped.

Suppose your merge prints numbers out of order. Print the heap contents after each pop. The output is sorted only if each pop returns the smallest head. If the output is unsorted, check that you push node.next, not node or the head of another list. A common bug is to push the old head again, which creates a loop of the same node.

Suppose your word program prints the wrong words for ties. Print the entries as they are popped from the heap. If the alphabetical order is reversed, check the second return in __lt__. It must be self.word > other.word, not self.word < other.word. Then check the reversal of the output.

Variations and edge cases

K equal to 1 is the same as finding the maximum. The heap holds one value, and each new value replaces it when it is larger.

K larger than n means every value is kept. The heap never pops. The answer is the whole set, sorted in the right order.

K equal to the number of distinct words means the top-K words are all the words. The output is then the full frequency table in order.

Merging lists of very different sizes works without change. A short list runs out early, and the others keep going. The heap only ever holds one node per live list.

Choosing the Kth largest without a full heap is possible. A known method called quickselect finds the Kth element in O(n) on average, but it is harder to write and its worst case is O(n²) unless you add tricks. In an interview, the heap answer is usually the one to give first, because it is clear and has a good guarantee.

Interview patterns and real uses

The three patterns in this lesson cover a large share of heap questions. Name the pattern when you answer. "This is a top-K problem, so I will keep a min-heap of size K" tells the interviewer that you know the trick. Then state the cost: O(n log K) time and O(K) space.

Real systems use the same ideas. A search engine keeps the top ten results for each query. A log tool merges many sorted log files into one stream. A stock feed keeps the highest-moving stocks. A ride app keeps the nearest few drivers. Each one keeps a small heap and lets everything else go.

Complexity summary

Here n is the number of inputs, m is the number of different words, and N is the total number of values in all the lists.

Practice

1. Find the three smallest numbers in [9, 4, 7, 1, 8, 2] using the right heap. State which heap you use and why. Hint: a max-heap of size 3, which you can build from negated numbers.

Show the answer

Use a max-heap of size 3, built as a min-heap of negated numbers. Pushing 9, 4 and 7 gives three values. Pushing 1 makes four, so the pop removes the largest, 9. Pushing 8 makes four, and 8 is the largest, so it is removed. Pushing 2 makes four, so the pop removes 7. The three values left are 1, 2 and 4, which are the three smallest.

2. You merge 100 sorted lists with 1,000 values each. What is the time, using O(N log K)? Hint: N is 100,000 and K is 100.

Show the answer

N is 100,000 and K is 100. log2 100 is about 6.6, so the work is about 100,000 times 6.6, roughly 660,000 steps. Merging pairwise one list at a time would cost about N * K, which is 10 million.

3. Why does the K-largest heap use a min-heap, not a max-heap?

Show the answer

The top of a min-heap is the weakest kept value. Only the weakest value needs to be removed when a better value arrives. A max-heap would remove the best value, which is the wrong one to remove.

4. Change the word counter so that words with equal counts come out in reverse alphabetical order. Which line do you change, and what does it look like?

Show the answer

Change the second return in __lt__ to return self.word < other.word. That makes the alphabetically earlier word the weaker one when counts are equal, so it is removed first, and the later words stay. With k = 3 on the sample text, the printed output is the 3, cat 2 and and 2, so the later word comes first among equal counts.

5. Write a comparator for points, ordered by x and then by y, both from smallest to largest.

Show the answer

Python tuples already compare the first item and then the second, so sorted(points) gives this order for points written as (x, y) tuples. For a list of lists, use sorted(points, key=lambda p: (p[0], p[1])). Neither form needs subtraction, because Python does not wrap numbers around.

6. Some languages store integers in 32 bits, which holds values up to about 2.1 billion. In those languages the square of a value above about 46,340 wraps to a negative number. Does the closest-points program need a bigger integer type in Python? Give the reason.

Show the answer

No. Python integers have no size limit, so 50000 * 50000 gives 2500000000 without any special type. The same code is correct in Python without a change.

7. In the merge program, what happens if you remove the line if node.next is not None and always push node.next?

Show the answer

When the last node of a list is popped, node.next is None. Pushing (node.next.val, ...) reads .val of None, which raises AttributeError: 'NoneType' object has no attribute 'val'. The check stops the program from reading a field of None.

8. You need the top 5 trending words from a stream of posts, and the stream is too large to store. Which data structures do you keep, and what is the memory use?

Show the answer

Keep a dictionary of word counts, which grows with the number of distinct words, and a min-heap of size 5 for the top words. Memory is the dictionary plus five entries. If the dictionary is also too big, keep counts approximately, which is an advanced topic beyond this module.

9. Given [3, 1, 2] and K = 2, trace the top-K heap by hand and write the heap after each step.

Show the answer

Push 3: [3]. Push 1: [1, 3]. Push 2: [1, 2, 3], which has three values, so the pop removes 1, leaving [2, 3]. The final heap holds 2 and 3, and its top is 2, the second largest.

10. A merge of K lists has all lists empty except one that has 50 values. What is the running time of the heap merge?

Show the answer

Only one node is ever in the heap, so each push and pop works on a heap of size one. The total is about 50 steps, which is O(N). The bound O(N log K) is still correct, because the heap is never bigger than the number of non-empty lists.

Summary

• For the K largest values, keep a min-heap of size K and pop whenever it grows past K.
• For the K smallest values, flip the logic: keep a max-heap of size K, built from negated numbers.
• For the K most frequent items, count with a dictionary or Counter, then keep a size-K heap ordered by count, with a tie rule written in __lt__.
• For K closest points, push tuples of negated keys so that the heap's top is the point to remove.
• To merge K sorted lists, keep one heap entry per list, pop the smallest, and push the next node from that list.
• The costs are O(n log K) for top-K and O(N log K) for merging, with O(K) extra space.