Min Heap & Max Heap
Complete binary tree where parent nodes are smaller (min heap) or larger (max heap) than children. Fundamental data structure invented for heapsort by J.W.J. Williams in 1964, later improved by Robert Floyd. Heaps provide O(1) access to minimum/maximum and O(log n) insertion/deletion, essential for priority queues.
Visualization
Interactive visualization for Min Heap & Max Heap
Min Heap:
Max Heap:
Min/Max Heap:
- • Min: parent ≤ children
- • Max: parent ≥ children
Interactive visualization with step-by-step execution
Implementation
1class MinHeap {
2 private heap: number[] = [];
3
4 private parent(i: number): number { return Math.floor((i - 1) / 2); }
5 private left(i: number): number { return 2 * i + 1; }
6 private right(i: number): number { return 2 * i + 2; }
7
8 private swap(i: number, j: number): void {
9 [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
10 }
11
12 insert(value: number): void {
13 this.heap.push(value);
14 this.heapifyUp(this.heap.length - 1);
15 }
16
17 private heapifyUp(index: number): void {
18 while (index > 0 && this.heap[this.parent(index)] > this.heap[index]) {
19 this.swap(index, this.parent(index));
20 index = this.parent(index);
21 }
22 }
23
24 extractMin(): number | null {
25 if (this.heap.length === 0) return null;
26 if (this.heap.length === 1) return this.heap.pop()!;
27
28 const min = this.heap[0];
29 this.heap[0] = this.heap.pop()!;
30 this.heapifyDown(0);
31 return min;
32 }
33
34 private heapifyDown(index: number): void {
35 while (this.left(index) < this.heap.length) {
36 let smallerChild = this.left(index);
37 const right = this.right(index);
38
39 if (right < this.heap.length && this.heap[right] < this.heap[smallerChild]) {
40 smallerChild = right;
41 }
42
43 if (this.heap[index] <= this.heap[smallerChild]) break;
44
45 this.swap(index, smallerChild);
46 index = smallerChild;
47 }
48 }
49
50 peek(): number | null {
51 return this.heap.length > 0 ? this.heap[0] : null;
52 }
53
54 size(): number {
55 return this.heap.length;
56 }
57
58 // Build heap from array in O(n)
59 static buildHeap(arr: number[]): MinHeap {
60 const heap = new MinHeap();
61 heap.heap = [...arr];
62
63 for (let i = Math.floor(heap.heap.length / 2) - 1; i >= 0; i--) {
64 heap.heapifyDown(i);
65 }
66
67 return heap;
68 }
69}
70
71// Max Heap (similar structure, reversed comparisons)
72class MaxHeap {
73 private heap: number[] = [];
74
75 private parent(i: number): number { return Math.floor((i - 1) / 2); }
76 private left(i: number): number { return 2 * i + 1; }
77 private right(i: number): number { return 2 * i + 2; }
78
79 private swap(i: number, j: number): void {
80 [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
81 }
82
83 insert(value: number): void {
84 this.heap.push(value);
85 this.heapifyUp(this.heap.length - 1);
86 }
87
88 private heapifyUp(index: number): void {
89 while (index > 0 && this.heap[this.parent(index)] < this.heap[index]) {
90 this.swap(index, this.parent(index));
91 index = this.parent(index);
92 }
93 }
94
95 extractMax(): number | null {
96 if (this.heap.length === 0) return null;
97 if (this.heap.length === 1) return this.heap.pop()!;
98
99 const max = this.heap[0];
100 this.heap[0] = this.heap.pop()!;
101 this.heapifyDown(0);
102 return max;
103 }
104
105 private heapifyDown(index: number): void {
106 while (this.left(index) < this.heap.length) {
107 let largerChild = this.left(index);
108 const right = this.right(index);
109
110 if (right < this.heap.length && this.heap[right] > this.heap[largerChild]) {
111 largerChild = right;
112 }
113
114 if (this.heap[index] >= this.heap[largerChild]) break;
115
116 this.swap(index, largerChild);
117 index = largerChild;
118 }
119 }
120
121 peek(): number | null {
122 return this.heap.length > 0 ? this.heap[0] : null;
123 }
124}Deep Dive
Theoretical Foundation
Heap is array-based complete binary tree. For index i: left child = 2i+1, right child = 2i+2, parent = ⌊(i-1)/2⌋. Heap property: parent ≤ children (min heap) or parent ≥ children (max heap). Operations maintain this property through 'bubble up' (heapify up) and 'bubble down' (heapify down).
Complexity
Time
O(1) peek, O(log n) insert/delete
O(1) peek, O(log n) insert/delete
O(1) peek, O(log n) insert/delete
Space
O(n)
Applications
Industry Use
Operating system process scheduling
Dijkstra's shortest path algorithm
Huffman coding for data compression
Event-driven simulation systems
Median maintenance in streaming data
Top K elements problems
Memory management and garbage collection
A* pathfinding algorithm
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.