Data structures · 3 lessons
Heap / Priority QueueAlways the largest or smallest, in O(log n)
A heap is a complete binary tree stored in an array, where a parent is always smaller (or larger) than its children. It does not sort everything — it only guarantees the top — which is why insert and extract are both logarithmic. It is the standard way to build a priority queue.
Why learn Heap / Priority Queue
Where it shows upOS process scheduling
High-priority processes run first and new ones arrive at any time. A priority queue makes both "add" and "take the highest" fast; Linux's CFS uses a related structure.
→ Lesson: Binary HeapTop 10 most-read articles
Ten million articles, and you want the ten most read. You do not need to sort them. Keep a min-heap of size 10 and make one pass.
→ Lesson: Top-K ProblemsA running median
Data keeps arriving and you need the median at any moment. A max-heap holds the lower half, a min-heap the upper half, and the median sits at the two tops.
→ Lesson: Two HeapsLessons
3 lessons#AlgorithmComplexityDifficultyStatus
01Binary Heap Binary heapsArray representation, sift up / sift down, heapifyUsed for: Priority queues, Dijkstra, event simulationpush/pop O(log n)Space O(n)available02Top-K Problems Top KKeep a heap of size K, or use Quick SelectUsed for: Leaderboards, shortlisting candidates in a recommenderO(n log k)Space O(k)available03Two Heaps Two heapsA max-heap on the left, a min-heap on the right, kept balancedUsed for: Median of a stream, median over a sliding windowO(log n)Space O(n)available