Min heap implementation

What is a min heap?

A min-heap is a complete binary tree where all levels, except the last level, are completely filled. There is no “hole” in the tree. A min heap should meet these criteria: the parent’s value is less than both children’s values. The smallest value is at the root.

A min heap is in the opposite order of a max heap. Please refer to the max heap for more information.

Table of Content

Map of heap implementations

Part 1 – Max-heap implementation

you are here

Part 2 – Min-heap implementation

Insert

We declare 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 the actual number of elements in the array. It starts from 0.

To insert a new element, we put the new value at the end of the array. Then we move it up in the heap based on its value compared to its parent. If its value is less than its parent, it should be switched the position with its parent. We keep doing it until it is below a node with a smaller value and above one or two nodes with larger values. We call this process bubble up.

Java

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(logn), Space O(1), n is number of items in heap
	public void insert(T value) {		
		if (length == maxSize) {
			System.out.println("heap is full, cannot insert " + value);
			return;
		}
		heap[length]= value;
		bubbleUp(length);
		length++;
	}
	
	//Time O(logn), Space O(1)
	private void bubbleUp(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; 
	}

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(logn), Space O(1), n is number of items in heap

public void insert(T value) {

if (length == maxSize) {

System.out.println("heap is full, cannot insert " + value);

return;

}

heap[length]= value;

bubbleUp(length);

length++;

}

//Time O(logn), Space O(1)

private void bubbleUp(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

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(logn), Space O(1), n is number of items in heap
    insert(value) {
    	if (this.length >= this.maxSize) {
    		console.log("heap is full, cannot insert");
    		return;
    	}
        this.heap[this.length] = value;
		this.bubbleUp(this.length);
		this.length++;
    }

	//Time O(logn), Space O(1)
	bubbleUp(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; 
	}

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(logn), Space O(1), n is number of items in heap

insert(value) {

if (this.length >= this.maxSize) {

console.log("heap is full, cannot insert");

return;

}

this.heap[this.length] = value;

this.bubbleUp(this.length);

this.length++;

}

//Time O(logn), Space O(1)

bubbleUp(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

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(logn), Space O(1), n is number of items in heap
	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.bubble_up(self.length)
		self.length += 1

	# Time O(logn), Space O(1)	
	def	bubble_up(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

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(logn), Space O(1), n is number of items in heap

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.bubble_up(self.length)

self.length += 1

# Time O(logn), Space O(1)

def bubble_up(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

Remove

The removal operation is to remove the element at the root, which has the smallest value. This is the first element in the underlying array. When we remove the first element in the array, we move the last element to the first to fill out the empty spot. But this element’s value might be larger than its children’s. To correct this, we compare its value with its children’s values and switch with the child with the smaller value. We keep doing it until it is below a node with a smaller value and above one or two 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

	//Remove from min (first one), Time O(logn), 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--;		
		bubbleDown(0);		
		return min;
	}
	
	//Time O(logn), space O(1)
	private void bubbleDown(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;
	}

//Remove from min (first one), Time O(logn), 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--;

bubbleDown(0);

return min;

}

//Time O(logn), space O(1)

private void bubbleDown(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

    //Remove from min (first one), Time O(logn), 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.bubbleDown(0);
        return min;
    }

    //Time O(logn), Space O(1)
    bubbleDown(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;   
    }

//Remove from min (first one), Time O(logn), 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.bubbleDown(0);

return min;

}

//Time O(logn), Space O(1)

bubbleDown(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

    # Remove from min (first one), Time O(logn), 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.bubble_down(0)
		return min
    
    # Time O(logn), Space O(1)
	def bubble_down(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

# Remove from min (first one), Time O(logn), 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.bubble_down(0)

return min

# Time O(logn), Space O(1)

def bubble_down(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 Min-heap implementation in Java, JavaScript and Python
Data structures introduction

Login

What is a min heap?

Table of Content

Map of heap implementations

Insert

Java

Javascript

Python

Remove

Java

Javascript

Python

Free download