LeetCode Patterns Flashcards: Heap and Priority Queue, Top K, Merge K Sorted

A heap is a complete binary tree satisfying the heap property: in a min-heap every parent is smaller than its children, in a max-heap every parent is larger. Heaps support insertion and extraction of the minimum or maximum element in O of log n time, and peeking at the top in O of one. Use a heap when the problem asks for the k largest or smallest elements, when you need to repeatedly access the extreme value, or when you need to merge k sorted sequences. Building a heap from n elements takes O of n time.

Maintain a min-heap of size k. Iterate through all elements: add each to the heap, and if the heap size exceeds k, remove the minimum. After processing all elements, the heap top is the k-th largest because the heap contains exactly the k largest elements with the smallest of them on top. This runs in O of n log k time and O of k space, which is better than sorting in O of n log n when k is much smaller than n. An alternative is the quickselect algorithm with O of n average time but O of n squared worst case without randomization.

Insert the first element from each of the k lists into a min-heap, along with which list it came from and its position. Repeatedly extract the minimum from the heap, add it to the result, and insert the next element from the same list if one exists. This runs in O of n log k time where n is the total number of elements across all lists, because each of the n elements is inserted and extracted from a heap of size at most k. This is more efficient than merging two lists at a time, which would take O of n times k total time. The heap always gives you the globally smallest unprocessed element.

Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep their sizes balanced so they differ by at most one element. When a new number arrives, add it to the max-heap if it is less than or equal to the max-heap top, otherwise add it to the min-heap. Then rebalance if sizes differ by more than one by moving the top of the larger heap to the smaller. The median is the top of the larger heap if sizes differ, or the average of both tops if sizes are equal. Each insertion takes O of log n time. This maintains a running median efficiently.

First, build a frequency map counting occurrences of each element in O of n time. Then use a min-heap of size k: iterate through the frequency map, push each element with its count, and if the heap exceeds size k, remove the element with the lowest frequency. After processing all entries, the heap contains the k most frequent elements. This runs in O of m log k where m is the number of unique elements. An alternative O of n approach uses bucket sort: create an array of lists indexed by frequency, place elements into their frequency bucket, then collect from the highest buckets.

A min-heap places the smallest element at the root, so the parent is always smaller than or equal to its children. Extracting the minimum takes O of log n. A max-heap places the largest element at the root, so the parent is always larger than or equal to its children. Extracting the maximum takes O of log n. Most language libraries provide min-heaps by default. To simulate a max-heap, negate all values before insertion and negate them back when extracting. Choose min-heap when you need repeated access to the smallest element, and max-heap when you need the largest.