Heap - Basics
Heaps are a type of binary tree that are used to implement priority queues.
There are two types of heaps: max-heaps and min-heaps.
In a max-heap, the key of each node is greater than or equal to the keys of its children.
In a min-heap, the key of each node is less than or equal to the keys of its children.
The max-heap property implies that the largest element in the heap is stored at the root.
The min-heap property implies that the smallest element in the heap is stored at the root.
A heap is a complete binary tree.
Complete binary tree is a binary tree in which every level, except possibly the last,
is completely filled, and all nodes are as far left as possible.
Heaps can have duplicate elements.
Although heap is drawn as a binary tree, it is usually implemented as an array.
Also, we don't start the heap from index 0, but from index 1.
This is because, if we have a node at index i, then its left child is at index
2i and right child is at index 2i+1.
and its parent is at index i/2.
The height of a complete binary tree is O(log n), where n is the number of nodes in the tree.
Therefore, the time complexity of the basic heap operations, such as insertion,
deletion, and finding the minimum/maximum element is O(log n).
Push - O(log n)
Pop - O(log n)
Read Min/Max - O(1)
Heapify - O(n)
Finding any random element - O(n) but in binary search tree it is O(log n)
class Heap {
constructor() {
this.heap = new Array();
this.heap.push(0);
}
}
Push element - Percolate Up: O(log n)
const push = (val) => {
this.heap.push(val);
let i = this.heap.length - 1;
// Percolate up
while (i > 1 && this.heap[i] < this.heap[Math.floor(i / 2)]) {
let tmp = this.heap[i];
this.heap[i] = this.heap[Math.floor(i / 2)];
this.heap[Math.floor(i / 2)] = tmp;
i = Math.floor(i / 2);
}
};
Read element (Get Min/Max) - O(1) - Just read the root element, or heap[1]
Pop element - Percolate Down: O(log n)
const pop = () => {
if (this.heap.length === 1) return null; // heap is empty
if (this.heap.length === 2) return this.heap.pop(); // only one element in heap
const min = this.heap[1]; // root element
this.heap[1] = this.heap.pop(); // replace root with last element
let i = 1;
// Percolate down
while (true) {
let left = 2 * i;
let right = 2 * i + 1;
let smallest = i;
if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if (smallest === i) break; // heap property is satisfied
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]]; // swap
i = smallest;
}
return min;
};
Heapify - O(n)
by usual, pushing all elements one by one - O(n log n), but
we can do it in O(n) by percolating down from the last non-leaf node to the root.
why it is linear time complexity?
The time complexity of the heapify operation is O(n) because it takes advantage of the
properties of a complete binary tree.
In a complete binary tree, the number of nodes at each level doubles as you move down the tree.
The height of the tree is log(n), where n is the number of nodes in the tree.
o(n) = sum of (number of nodes at level i * time to percolate down from level i)
= sum of (2^i * (log(n) - i)) for i = 0 to log(n)
= n * sum of ((log(n) - i) / 2^(log(n) - i)) for i = 0 to log(n)
= n * sum of (i / 2^i) for i = 0 to log(n)
= O(n)
const heapify = (arr) => {
this.heap = [0, ...arr]; // add a dummy element at index 0
let n = this.heap.length;
// Start from the last non-leaf node and percolate down
for (let i = Math.floor((n - 1) / 2); i >= 1; i--) {
percolateDown(i);
}
};
const percolateDown = (i) => {
while (true) {
let left = 2 * i;
let right = 2 * i + 1;
let smallest = i;
if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if (smallest === i) break; // heap property is satisfied
[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]]; // swap
i = smallest;
}
};