What is a Heap?¶
Imagine you have a pile of files and want to prioritize handling the most important ones first (e.g., urgent documents) or the least important ones first (e.g., trash files). In this case, a “heap” acts like a special “container” that allows you to quickly access the largest or smallest element.
A heap is essentially a special complete binary tree with a core property: each parent node satisfies a certain rule (either ≤ or ≥ its children). This property enables the heap to efficiently retrieve the “maximum” or “minimum” element, functioning like a “priority queue.”
The Structural Foundation of Heaps: Complete Binary Trees¶
A heap is built on a complete binary tree. Here are the key characteristics of a complete binary tree:
- Every level is fully filled, except possibly the last level;
- Nodes in the last level are filled from left to right without gaps.
Example:
1
/ \
3 2
/ \ /
6 4 5
This is a complete binary tree where each level is mostly filled, and the last level (level 3) has 3 nodes (6, 4, 5) arranged left to right.
Min-Heap vs. Max-Heap¶
Heaps come in two types, differing in the size relationship between parent and child nodes:
Min-Heap¶
- Rule: A parent node’s value is less than or equal to all its children’s values.
- Heap Top: The smallest element (root node).
Array Representation:
When stored in an array, the indices correspond to node positions, with these rules:
- Left child index = 2×parent index + 1
- Right child index = 2×parent index + 2
- Parent index = (child index - 1) // 2
For example, the array [1, 3, 2, 6, 4, 5] represents a min-heap:
- The root (index 0) is 1 (smallest);
- 1’s left child (index 1) is 3, right child (index 2) is 2, satisfying 1 ≤ 3 and 1 ≤ 2;
- 3’s left child (index 3) is 6, right child (index 4) is 4, satisfying 3 ≤ 6 and 3 ≤ 4;
- 2’s left child (index 5) is 5, satisfying 2 ≤ 5.
Max-Heap¶
- Rule: A parent node’s value is greater than or equal to all its children’s values.
- Heap Top: The largest element (root node).
Array Representation:
For the array [10, 5, 8, 3, 2, 1] (max-heap):
- The root (index 0) is 10 (largest);
- 10’s left child (index 1) is 5, right child (index 2) is 8, satisfying 10 ≥ 5 and 10 ≥ 8;
- 5’s left child (index 3) is 3, right child (index 4) is 2, satisfying 5 ≥ 3 and 5 ≥ 2;
- 8’s left child (index 5) is 1, satisfying 8 ≥ 1.
Array Representation and Index Relationships¶
Heaps are most efficiently stored in arrays due to the natural fit of complete binary trees with array indices. Remember these “parent-child index formulas”:
- For a node at index i:
- Left child: 2*i + 1
- Right child: 2*i + 2
- Parent: (i - 1) // 2 (integer division)
Example with [1, 3, 2, 6, 4, 5] (min-heap):
- Node 1 (index 0) has children 3 (index 1) and 2 (index 2);
- Node 3 (index 1) has children 6 (index 3) and 4 (index 4);
- Node 2 (index 2) has child 5 (index 5).
Basic Heap Operations: Insertion and Deletion¶
The core advantage of heaps is their high efficiency for insertion and deletion (O(log n) time complexity), as the height of the heap is log n (where n is the number of elements).
1. Insertion (Min-Heap Example)¶
Steps:
1. Add the new element to the end of the array;
2. “Bubble up” (percolate up): Compare the new element with its parent. If the new element is smaller (for min-heap), swap them and continue until the parent is smaller or the root is reached.
Example:
Original min-heap array: [1, 3, 2, 6, 4, 5] (root: 1)
Insert new element 0:
- Add to end: array becomes [1, 3, 2, 6, 4, 5, 0];
- Bubble up:
- Parent of 0 (index 6) is 6 (index 3): 0 < 6 → swap → [1, 3, 2, 0, 4, 5, 6];
- Parent of 0 (index 3) is 3 (index 1): 0 < 3 → swap → [1, 0, 2, 3, 4, 5, 6];
- Parent of 0 (index 1) is 1 (index 0): 0 < 1 → swap → [0, 1, 2, 3, 4, 5, 6].
The array now satisfies the min-heap property.
2. Deletion (Min-Heap Example)¶
Steps:
1. Remove the root (smallest element);
2. Replace the root with the last element in the array;
3. “Bubble down” (percolate down): Compare the new root with its children. If a child is smaller (for min-heap), swap them and continue until children are larger or a leaf is reached.
Example:
Original min-heap array: [0, 1, 2, 3, 4, 5, 6] (root: 0)
Delete the root:
- Remove 0, array becomes [1, 2, 3, 4, 5, 6];
- Replace root with last element (6): array becomes [6, 2, 3, 4, 5, 6];
- Bubble down:
- Children of 6 (index 0) are 2 (index 1) and 3 (index 2); smallest child is 2: 6 > 2 → swap → [2, 6, 3, 4, 5, 6];
- Children of 6 (index 1) are 4 (index 3) and 5 (index 4); smallest child is 4: 6 > 4 → swap → [2, 4, 3, 6, 5, 6];
- Child of 6 (index 3) is 5 (index 4): 6 > 5 → swap → [2, 4, 3, 5, 6, 6].
The new heap now satisfies the min-heap property with root 2.
Applications of Heaps¶
The most classic use of heaps is in priority queues, where the highest (max/min) priority element is retrieved first. Common scenarios include:
1. Priority Queues (Task Scheduling)¶
- Server task processing: Use a max-heap to always select the highest-priority task.
- Hospital emergency rooms: Max-heap to quickly access the most critical patient.
2. Finding the k-th Largest Element¶
- Use a min-heap to keep track of the top k elements. The root of the heap is the k-th largest element. For example, to find the 3rd largest element:
- Traverse the array, maintaining a heap of size 3. If a new element is larger than the root, replace the root and adjust the heap. The final root is the 3rd largest.
3. Huffman Coding (Compression Algorithm)¶
- Use a min-heap to merge the two least frequent nodes, building a Huffman tree for data compression.
Summary¶
A heap is a special structure based on a complete binary tree, with the core property being the size relationship between parent and child nodes. Min-heaps and max-heaps allow efficient retrieval of the smallest or largest elements, maintained via insertion (bubble up) and deletion (bubble down) operations.
Heaps excel in applications requiring efficient retrieval of extreme values (O(log n) time). For beginners, start by understanding array representation and insertion/deletion steps through examples, then apply these concepts to real-world problems like priority queues and k-th largest element problems. Mastering heaps will significantly boost your algorithm efficiency!