Min heap is a complete binary tree, in which all levels are completely filled and all the nodes in the last level are as left as possible. Min heap also meets this criteria: the parent’s key is less than both children’s keys. The smallest value is at the root. This post is about how to implement min heap.
A max heap is opposite order. Note the search and traversal in min heap implementation is the same as max heap, so please refer to max heap for these two operation implementations.
Table of Content
Concepts
A heap is a complete binary tree conceptually. The underlying data structure is an array. Each node’s position in the heap is corresponding to the index in the array. The root’s position is 0, corresponding to the index 0. The node’s position increases by 1 from left to right, from upper level to lower level.
The formula to get the parent and two children’s positions from the current node’s position in a heap:
parentPos = (pos-1)/2
left = 2*pos+1
right=2*pos+2
Insert
In MinHeap class, there are three attributes: heap, length and maxSize. heap is an array. maxSize is the max length of the array. It is used to initialize the array. length is actual number of elements in the array. It starts from 0.
To insert a new element, you put the new value at the end of the array. Then you move it up based on its value compared to its parent. If it’s value less than its parent, it should be switched the position with its parent, until it is below a node with smaller value and above nodes with larger values. We call this process bubble up.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.*; public class MinHeap<T extends Comparable<T>> { T[] heap; int length; int maxSize; //Time O(1) Space O(1) @SuppressWarnings("unchecked") public MinHeap(int capacity) { maxSize = capacity; heap = (T[]) new Comparable[capacity]; length = 0; // means queue is empty } //Insert a new value, Time O(h), Space O(1), n is number of items in heap //h is height of heap (complete binary tree) h = log(n) public void insert(T value) { if (length == maxSize) { System.out.println("heap is full, cannot insert " + value); return; } heap[length]= value; heapUp(length++); } //Time O(h), Space O(1) private void heapUp(int pos) { int parentPos = (pos-1)/2; T value = heap[pos]; while (pos > 0 && (value.compareTo(heap[parentPos]) < 0)) { heap[pos] = heap[parentPos]; pos = parentPos; parentPos= (parentPos-1)/2; } heap[pos] = value; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class MinHeap { //Constructor, Time O(1) Space O(1) constructor(capacity) { this.maxSize = capacity; this.length = 0; this.heap = {}; } //Insert a new value, Time O(h), Space O(1), n is number of items in heap //h is height of heap (complete binary tree) h=log(n) insert(value) { if (this.length >= this.maxSize) { console.log("heap is full, cannot insert"); return; } this.heap[this.length] = value; this.heapUp(this.length++); } //Time O(h), Space O(1) heapUp(pos) { var parentPos = Math.floor((pos-1)/2); var value = this.heap[pos]; while (pos > 0 && value < this.heap[parentPos]) { this.heap[pos] = this.heap[parentPos]; pos = parentPos; parentPos= Math.floor((parentPos-1)/2); } this.heap[pos] = value; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class MinHeap : # Time O(1) Space O(1) def __init__(self, capacity) : self.maxSize = capacity self.length = 0 self.heap = [None]*capacity # Insert a new value, Time O(h), Space O(1), n is number of items in heap # h is height of heap (complete binary tree) h = log(n) def insert(self, value): if self.length >= self.maxSize : print("heap reach max size, return") return self.heap[self.length] = value # start from last self.heapUp(self.length) # Time O(h), Space O(1) def heapUp(self, pos) : parentPos = int((pos-1)/2) value = self.heap[pos] while pos > 0 and value < self.heap[parentPos] : self.heap[pos] = self.heap[parentPos] pos = parentPos parentPos= int((parentPos-1)/2) self.heap[pos] = value; self.length += 1 |
Remove
The removal operation is to remove the element with the smallest value, which is the first one in the array. When you remove the first element in the array, you move the last element in the array to the first to fill out the empty spot. But this element’s value might be larger than its children’s. To correct this, you compare its value with its children’s values, and switch with the child with the smaller value, until it is below a node with smaller value and above nodes with larger values. This process is called bubble down. Bubble down is more complicated than bubble up because it has two children to compare.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//Remove from min (first one), Time O(h), Space O(1) public T remove() { if (length == 0) { System.out.println("heap is empty"); return null; } T min = heap[0]; heap[0] = heap[length-1]; //last put first length--; heapDown(0); return min; } //Time O(h), space O(1) private void heapDown(int pos) { T item = heap[pos]; int index; while (pos < length/2) { int left = 2*pos + 1; int right = 2*pos + 2; if (right < length && heap[left].compareTo(heap[right]) > 0) index = right; else index = left; if (item.compareTo(heap[index]) <= 0) break; heap[pos] = heap[index]; pos = index; } heap[pos] = item; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//Remove from min (first one), Time O(h), Space O(1) remove() { if (this.length == 0) { console.log("heap is empty"); return null; } var min = this.heap[0]; this.heap[0] = this.heap[this.length-1]; //put last at first this.length--; this.heapDown(0); return min; } //Time O(h), Space O(1) heapDown(pos) { var item = this.heap[pos]; var index; while (pos < Math.floor(this.length/2)) { let left = 2*pos + 1; let right = 2*pos + 2; if (right < this.length && this.heap[left] > this.heap[right]) index = right; else index = left; if (item <= this.heap[index]) break; this.heap[pos] = this.heap[index]; pos = index; } this.heap[pos] = item; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# Remove from min (first one), Time O(h), Space O(1) def remove(self) : if self.length == 0: print("heap is empty") return None min = self.heap[0] self.heap[0] = self.heap[self.length-1] # put the last at first self.length -= 1 self.heapDown(0) return min # Time O(h), Space O(1) def heapDown(self, pos) : item = self.heap[pos] index = 0 while pos < int(self.length/2) : left = 2*pos + 1 right = 2*pos + 2 if right < self.length and self.heap[left] > self.heap[right]: index = right else: index = left if item <= self.heap[index]: break self.heap[pos] = self.heap[index] pos = index self.heap[pos] = item; |
Free download
Download MinHeap.java
Download MinHeap.js
Download MinHeap.py
To insert a new element in a heap, the algorithm bubble up is used. It is to put the new item in the first vacant cell of the array. Then move it up in the heap based on its value compared to its parent. In a max heap, it should be below a node with a larger key and above 1 or 2 child nodes with smaller keys.
Bubble down is an algorithm used in heap deletion. It is to compare the parent node with child nodes in a subtree. If the parent node is smaller, you should switch the parent element with child nodes in a max heap.
