Heaps & Priority Queues

Binary Heap · Sift Up/Down · O(log n)

1:00

How a binary heap stores a complete tree in a plain array to deliver the minimum element in O(1) and support insert and extract in O(log n).

By the end, you can

Explain what makes a priority queue different from a FIFO queue.
State the heap-order property and identify whether a given array is a valid min-heap.
Compute the left child, right child, and parent of any node using the index formulas.
Trace a sift-up sequence after inserting a new value.
Trace a sift-down sequence after extracting the minimum.
Explain why build-heap runs in O(n) using the halving-sum argument.
Identify the time complexities of peek, insert, extract, build-heap, and arbitrary search.
Describe how heap sort works and why it is not stable.
Name at least two real-world algorithms or problems that rely on a priority queue.

Up next in Math, Memory & Files