Heap
A heap is a data structure designed for one job: quickly giving you the “most important” element(usually the smallest or the largest). That’s why heaps are most commonly used to implement a priority queue.
There are many kind of heaps, but in algorithm interviews and competetive programming, “heap” almost always means a binary heap(heap that have maximum 2 children).
Heap vs. Priority Queue
- Priority queue: an abstract idea — “store items with priorities; always pop the best one.”
- Binary heap: a concrete implementation that makes those operations fast.
The Two Core Properties of a Binary Heap
- Heap property (ordering rule)
There are two common variants:
Min-heap: Every node is smaller or equal than its children. The minimum element is always at the root.
Max-heap: Every node is larger or equal than its children. the maximum element is always at the root.
Important point is, heap is not a sorted structure. Only the root is guaranteed to be min or max; deeper levels are only partially ordered.
2. Shape property (structure rule)
A binary heap is a complete binray tree:
- All levels are completely filled except possibly the last
- The last level is filled from left to right
This “complete tree” rule is the reason a heap can be stored efficiently in an array.
Array Implementation:
Instead of pointers and tree nodes, we store hte heap in a dynamic array(like vector in c++).
****
Remember: pointer-based tree representations tend to scatter nodes across memory. This hurts cache locality and makes access patterns more “random” than a contiguous array, which can be significantly slower in practice. In addition, a node-based structure usually requires many small dynamic allocations, adding overhead and (in languages with manual memory management) increasing the risk of bugs such as leaks or dangling pointers.
- ****
Assume 0-based indexing:
parten(i) = (i — 1) / 2
Get Dogukanbayhan’s stories in your inbox
Join Medium for free to get updates from this writer.
left(i) = 2*i + 1
right(i) = 2*i + 2
So the root is at index 0. Its children are at indices 1 and 2, 1’s childrens are 2 * 1 + 1 = 3 and 2 * 1 + 2 = 4, and so on.
The Two Fundamental “Fixing” Operations
Every heap operation reduces to restoring the heap property by moving one element:
- Sift Up:
Used after inserting a new element.
Idea: you insert at hte end (to keep the tree complete), then keep swapping upward while the heap property is violated.
Time: O(log n)
2. Sift Down:
Used after removing the root(extract-min / extract-max).
Idea: you replace the root with the last element (to keep the tree complete), then push it downward by swapping with the “better” child until the heap property is restored.
Time: O(log n)
Building a Heap from an Array (Heapify)
If you have an unsorted array and want a heap, you could insert one-by-one: O(n log n).
But there is a faster method:
Bottom-up heapify:
1- start from the lart non-leaf node: i = n/2–1
2- run sift down for i, i-1, …, 0
This builds the heap in O(n) time.
