Understanding how binary heaps work and why insert operations are logarithmic time
A heap is a special type of binary tree that satisfies the heap property. In a min-heap, every parent node is smaller than or equal to its children. In a max-heap, every parent node is larger than or equal to its children.
Key Properties:
Heaps are commonly used for priority queues, heap sort, and finding the minimum/maximum element efficiently.
A binary tree is a tree data structure where each node has at most two children (left and right). In a heap:
Parent ≤ Children
Root is the minimum value
Used for priority queues (smallest first)
Parent ≥ Children
Root is the maximum value
Used for finding maximum efficiently
Heaps are stored in arrays for efficiency. The tree structure is implicit:
Array: [10, 20, 30, 40, 50, 60, 70]Tree structure:
10 (index 0)
/ \
20 (1) 30 (2)
/ \ / \
40 (3) 50 (4) 60 (5) 70 (6)Insert the new element at the end of the array (maintaining the complete binary tree property).
Compare the new element with its parent. If it violates the heap property, swap with the parent. Repeat until the heap property is satisfied or you reach the root.
The element may need to bubble up from the bottom level to the root. In the worst case, this requires traversing the height of the tree, which is O(log n):
Code Example:
// Min-heap insert with heapify up
function insert(heap, value) {
heap.push(value); // Add to end - O(1)
heapifyUp(heap, heap.length - 1); // Bubble up - O(log n)
}
function heapifyUp(heap, index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (heap[parent] <= heap[index]) break;
[heap[parent], heap[index]] = [heap[index], heap[parent]];
index = parent;
}
}A complete binary tree with n nodes has height ⌊log₂(n)⌋. Since we insert at the bottom and may need to bubble up to the root, the worst case is traversing the entire height.
During heapify up, we compare with the parent and swap if needed. We move up one level at a time, so at most we do ⌊log₂(n)⌋ comparisons and swaps.
Heap operations complexity:
| Operation | Heap | Sorted Array | Unsorted Array | Explanation |
|---|---|---|---|---|
| Insert | O(log n) | O(n) | O(1) | Heap: bubble up. Sorted: shift elements. Unsorted: just append |
| Get Min/Max | O(1) | O(1) | O(n) | Heap: root. Sorted: first/last. Unsorted: must search |
| Extract Min/Max | O(log n) | O(n) | O(n) | Heap: bubble down. Others: remove and shift |
| Build from Array | O(n) | O(n log n) | N/A | Heap: efficient bottom-up. Sorted: need to sort |
Operating systems use heaps for task scheduling. High-priority tasks are processed first, and new tasks can be inserted efficiently.
Emergency rooms use priority queues (heaps) to determine which patients to treat first based on severity. New patients are inserted with their priority level.
Calendar applications use heaps to manage events by time. The earliest event is always at the root, and new events are inserted efficiently.
Pathfinding algorithms like A* use priority queues (heaps) to explore the most promising paths first, inserting new nodes as they're discovered.
Heap sort uses a heap to sort an array. It builds a heap (O(n)) then repeatedly extracts the minimum (O(log n) each), resulting in O(n log n) overall.
Inserting requires bubbling up through at most the height of the tree, which is logarithmic
All levels are filled except possibly the last, filled left to right
Heaps excel at maintaining min/max while allowing efficient insertions and removals
Storing heaps in arrays avoids pointer overhead and provides cache-friendly access patterns