Max 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. Max heap also meets this criteria: the parent’s key is larger than both children’s keys. The largest value is at the root. Heap is related to priority queue and heapsort. This post is about how to implement max heap.
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 MaxHeap 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 larger than its parent, it should be switched the position with its parent, until it is below a node with a larger value and above nodes with smaller values. We call this process bubble up (or heap 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 35 |
import java.util.*; public class MaxHeap<T extends Comparable<T>> { T[] heap; int length; int maxSize; //Time O(1) Space O(1) @SuppressWarnings("unchecked") public MaxHeap(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 30 31 32 |
class MaxHeap { //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 |
class MaxHeap : #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 highest 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 fill out the empty spot. But this element’s value might be smaller than its children’s. To correct this, you compare its value with its children’s values, and switch with the child with the larger value, until it is below a larger node and above a smaller one. This process is called bubble down or heap 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 max (first one), Time O(h), Space O(1) public T remove() { if (length == 0) { System.out.println("heap is empty"); return null; } T max = heap[0]; heap[0] = heap[length-1]; //put last at first length--; heapDown(0); return max; } //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 31 |
//Remove from max (first one), Time O(h), Space O(1) remove() { if (this.length == 0) { console.log("heap is empty"); return null; } var max = this.heap[0]; this.heap[0] = this.heap[this.length-1];//put last to first this.length--; //reduce length this.heapDown(0); return max; } //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 max (first one), Time O(h), Space O(1) def remove(self) : if self.length == 0: print("heap is empty") return None max = self.heap[0] self.heap[0] = self.heap[self.length-1] # put last at first self.length -= 1 self.heapDown(0) return max # 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; |
Search
Since the underlying data structure is an array, you iterate through all elements to find the one matched with the key.
Java
|
1 2 3 4 5 6 7 8 |
//Time O(n), Space O(1), n is number of items in heap public boolean search(T key) { for (int i = 0; i < length; i++) { if (key.compareTo(heap[i]) == 0) return true; } return false; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Time O(n), Space O(1), n is number of items in heap search(key) { for (let i = 0; i < this.length; i++) { if (key == this.heap[i]) return true; } return false; } |
Python
|
1 2 3 4 5 6 |
#Time O(n), Space O(1), n is number of items in heap def search(self, key) : for i in range(0, self.length) : if key == self.heap[i]: return True return False |
Traversal
Traversal is to visit all nodes in a tree in some specified order. Please note the heap is a tree in conceptual context, the underlying implementation is array. Therefore there are no actual nodes (there is no root node). But you still can traverse all elements in the same way as any tree traversal, by level order, preorder, inorder and postorder.
Level order is to visit node level by level from top to bottom. The order is the same as visiting array from index 0 to its length.
Java
|
1 2 3 4 5 6 7 8 |
//Traverse as array, it is also level order of tree, Time O(n), Space O(n) public List<T> levelOrder() { List<T> list = new ArrayList<>(); for(int i = 0; i < length; i++) { list.add(heap[i]); } return list; } |
Javascript
|
1 2 3 4 5 6 7 8 |
//Traverse as array, it is also level order of tree, Time O(n), Space O(n) levelOrder() { var str = []; for(let i = 0; i < this.length; i++) { str.push(this.heap[i]); } return str; } |
Python
|
1 2 3 4 5 6 |
# Traverse as array, it is also level order of tree, Time O(n), Space O(n) def levelOrder(self) : s = [] for i in range(0, self.length): s.append(self.heap[i]) return s |
Preorder is to visit the root, traverse the left subtree, traverse the right subtree. The implementation is using DFS with recursion. To get the children “node”, you use the formula 2pos+1 for left child, and 2pos+2 for right child.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Traverse as tree preorder, Time O(n), Space (n) public List<T> preorder() { List<T> list = new ArrayList<>(); preorderRec(0, list); return list; } //Recursion helper, Time O(n), Space (h) private void preorderRec(int nodeIndex, List<T> list ) { if (nodeIndex > length-1) return; list.add(heap[nodeIndex]); preorderRec(2*nodeIndex + 1, list); preorderRec(2*nodeIndex + 2, list); } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Traverse as tree preorder, Time O(n), Space (n) preorder() { var output = []; this.preorderRec(0, output); return output; } //Recursion helper, Time O(n), Space (h) preorderRec(nodeIndex, output) { if (nodeIndex > this.length-1) return; output.push(this.heap[nodeIndex]); this.preorderRec( 2*nodeIndex + 1, output); this.preorderRec( 2*nodeIndex + 2, output ) ; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Traverse as tree preorder, Time O(n), Space (n) def preorder(self) : output = [] self.preorderRec(0, output) return output # Recursion helper, Time O(n), Space (h) def preorderRec(self, nodeIndex, output) : if nodeIndex > self.length-1 : return output.append(self.heap[nodeIndex]) self.preorderRec( 2*nodeIndex + 1, output) self.preorderRec( 2*nodeIndex + 2, output) |
Inorder is to traverse the left subtree, visit the root, traverse the right subtree. The implementation is using DFS with recursion. To get the children “node”, you use the formula 2*pos+1 for left child, and 2*pos+2 for right child.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Traverse as tree inorder, Time O(n), Space (n) public List<T> inorder() { List<T> list = new ArrayList<>(); inorderRec(0, list); return list; } //Recursion helper, Time O(n), Space (h) private void inorderRec(int nodeIndex, List<T> list) { if (nodeIndex > length-1) return; inorderRec(2*nodeIndex + 1, list); list.add(heap[nodeIndex]) ; inorderRec(2*nodeIndex + 2, list); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Traverse as tree inorder, Time O(n), Space (n) inorder() { var output = []; this.inorderRec(0, output); return output; } //Recursion helper, Time O(n), Space (h) inorderRec(nodeIndex, output) { if (nodeIndex > this.length-1) return; this.inorderRec(2*nodeIndex + 1, output); output.push(this.heap[nodeIndex]) ; this.inorderRec(2*nodeIndex + 2, output ) ; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Traverse as tree inorder, Time O(n), Space (n) def inorder(self) : output = [] self.inorderRec(0, output) return output # Recursion helper, Time O(n), Space (h) def inorderRec(self, nodeIndex, output) : if nodeIndex > self.length-1 : return self.inorderRec(2* nodeIndex +1, output) output.append(self.heap[nodeIndex]) self.inorderRec(2*nodeIndex + 2, output) |
Postorder is to traverse the left subtree, traverse the right subtree, visit the root. The implementation is using DFS with recursion. To get the children “node”, you use the formula 2*pos+1 for left child, and 2*pos+2 for right child.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Traverse as tree postorder, Time O(n), Space O(n) public List<T> postorder() { List<T> list = new ArrayList<>(); postorderRec(0, list); return list; } //Recursion helper, Time O(n), Space (h) private void postorderRec(int nodeIndex, List<T> list) { if (nodeIndex > length-1) return; postorderRec(2*nodeIndex + 1, list); postorderRec(2*nodeIndex + 2, list); list.add(heap[nodeIndex]) ; } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Traverse as tree postorder, Time O(n), Space O(n) postorder() { var output = []; this.postorderRec(0, output); return output; } //recursion helper, Time O(n), Space (h) postorderRec(nodeIndex, output) { if (nodeIndex > this.length-1) return; this.postorderRec(2*nodeIndex + 1, output); this.postorderRec(2*nodeIndex + 2, output ) ; output.push(this.heap[nodeIndex]); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Traverse as tree postorder, Time O(n), Space O(n) def postorder(self) : output = [] self.postorderRec(0, output) return output # Recursion helper, Time O(n), Space (h) def postorderRec(self, nodeIndex, output) : if (nodeIndex > self.length-1): return self.postorderRec(2*nodeIndex + 1, output) self.postorderRec(2*nodeIndex + 2, output) output.append(self.heap[nodeIndex]) |
Free download
Download MaxHeap.java
Download MaxHeap.js
Download MaxHeap.py
Implement min heap
