Heap / Priority Queue

A heap is a complete binary tree stored in an array where every parent is no larger (min-heap) or no smaller (max-heap) than its children, so the smallest or largest item is always at the top: peek in O(1), push and pop in O(log n).

To find the k largest items, keep a min-heap of size k: its top is the weakest of the current winners, so each new item either beats it and replaces it or is ignored, for O(n log k) time and O(k) memory.

To merge k sorted lists, keep only the current head of each list in a min-heap; repeatedly pop the smallest and push its successor from the same list, for O(N log k) time over N total items.

Split the numbers into a max-heap for the smaller half and a min-heap for the larger half, keep their sizes within one, and the median is always at one or both tops: O(log n) per insert and O(1) to read the median.

Scheduling problems become simple when a heap always tells you the next thing that matters: the earliest-ending meeting, the shortest ready task or the most urgent job, each found in O(log n).