Heap
A heap is a complete binary tree that satisfies the heap property. In a max-heap, every node's value is greater than or equal to the values of its children...
Heap as a Complete Binary Tree
A heap is a complete binary tree that satisfies the heap property. In a max-heap, every node's value is greater than or equal to the values of its children. In a min-heap, every node's value is less than or equal to the values of its children. These constraints apply recursively throughout the entire tree. The heap property does not impose any ordering between siblings, nor does it sort the tree — it only guarantees that the root holds the extreme value (maximum or minimum).
Because a heap is a complete binary tree, it can be stored compactly in an array without any pointers. For a node at index i (using zero-based indexing), its left child is at index 2i plus one, its right child is at index 2i plus two, and its parent is at index floor of (i minus one divided by two). This array representation makes heaps extremely cache-friendly and memory-efficient.
Heaps are the data structure underlying priority queues — abstract data types that allow efficient insertion and extraction of the highest- (or lowest-) priority element. They are also the backbone of the heap sort algorithm and Dijkstra's shortest path algorithm.
Heapify, Insert, and Extract
The core operations on a heap are insert, extract-min (or extract-max), and heapify. To insert an element, place it at the end of the array (the next available position in the complete tree) and bubble it up: repeatedly compare it with its parent and swap if it violates the heap property. This process, called sift-up or percolate-up, runs in O(log N) time because the tree height is O(log N).
To extract the root (the minimum or maximum), replace the root with the last element, remove the last element, and sift-down: compare the new root with its children and swap with the smaller (or larger) child until the heap property is restored. Extract also runs in O(log N) time.
Heapify — building a heap from an arbitrary array — can be done in O(N) time by applying sift-down to every non-leaf node starting from the last non-leaf and working toward the root. Despite appearances, this is O(N) not O(N log N) because most nodes are near the bottom and their sift-down distances are short.
Heap Sort and Interview Tips
Worked example: build a max-heap from the array [3, 1, 4, 1, 5, 9, 2, 6]. Start heapify from index 3 (last non-leaf). After heapifying all non-leaf nodes bottom-up, the array becomes [9, 6, 4, 3, 5, 1, 2, 1]. Extract the max (9), swap it to the end, reduce heap size by one, and sift-down. Repeat until the heap size is one. The result is a sorted array. This is heap sort, which runs in O(N log N) time and O(1) extra space — it is an in-place comparison sort.
Heap sort is not stable (equal elements may change relative order) and has poor cache performance compared to quicksort because of its non-sequential access pattern, which is why quicksort is preferred in practice despite both being O(N log N).
Interview tip: whenever a problem asks for the k largest or k smallest elements from a stream or large array, think heap immediately. Maintain a min-heap of size k; for each incoming element, if it is larger than the heap's minimum, push it and pop the minimum. After processing all elements, the heap contains the k largest. Time complexity is O(N log K), and space is O(K) — far better than sorting the entire array when K is small.