In this video we look at what heaps are and how to implement a binary heap.
/* | |
A min heap implementation | |
Array Form: [ 5, 7, 6, 10, 15, 17, 12 ] | |
Complete Binary Tree Form: | |
5 | |
/ \ | |
7 6 | |
/ \ / \ | |
10 15 17 12 | |
Mappings: | |
Parent -> (childIndex - 1) / 2 | |
Left Child -> 2 * parentIndex + 1 | |
Right Child -> 2 * parentIndex + 2 | |
YouTube explanation: https://www.youtube.com/watch?v=g9YK6sftDi0 | |
Heap Sort explanation: https://www.youtube.com/watch?v=k72DtCnY4MU | |
*/ | |
import java.util.*; | |
public class ImplementAMinHeap { | |
public static void main(String args[]) { | |
MinHeap minHeap = new MinHeap(); | |
int[] insertItems = new int[]{ 0, 1, 3, 2, -4, 9, 1, 2 }; | |
for (int i = 0; i < insertItems.length; i++) { | |
minHeap.add(insertItems[i]); | |
System.out.println("Add " + insertItems[i]); | |
System.out.println("Min is " + minHeap.peek()); | |
minHeap.printUnderlyingArray(); | |
System.out.println("\n"); | |
} | |
System.out.println("\n\n"); | |
for (int i = 0; i < insertItems.length; i++) { | |
System.out.println("Remove " + minHeap.remove()); | |
System.out.println("Min is " + minHeap.peek()); | |
minHeap.printUnderlyingArray(); | |
System.out.println("\n"); | |
} | |
} | |
private static class MinHeap { | |
private int capacity = 5; | |
private int heap[]; | |
private int size; | |
public MinHeap() { | |
heap = new int[capacity]; | |
} | |
public boolean isEmpty() { | |
return size == 0; | |
} | |
public int peek() { | |
if (isEmpty()) { | |
throw new NoSuchElementException("Heap is empty."); | |
} | |
return heap[0]; | |
} | |
public int remove() { | |
if (isEmpty()) { | |
throw new NoSuchElementException("Heap is empty."); | |
} | |
/* | |
-> Grab the min item. It is at index 0. | |
-> Move the last item in the heap to the "top" of the | |
heap at index 0. | |
-> Reduce size. | |
*/ | |
int minItem = heap[0]; | |
heap[0] = heap[size - 1]; | |
size--; | |
/* | |
Restore the heap since it is very likely messed up now | |
by bubbling down the element we swapped up to index 0 | |
*/ | |
heapifyDown(); | |
return minItem; | |
} | |
public void add(int itemToAdd) { | |
ensureExtraCapacity(); | |
/* | |
-> Place the item at the bottom, far right, of the | |
conceptual binary heap structure | |
-> Increment size | |
*/ | |
heap[size] = itemToAdd; | |
size++; | |
/* | |
Restore the heap since it is very likely messed up now | |
by bubbling up the element we just put in the last empty | |
position of the conceptual complete binary tree | |
*/ | |
siftUp(); | |
} | |
/*********************************** | |
Heap restoration helpers | |
***********************************/ | |
private void heapifyDown() { | |
/* | |
We will bubble down the item just swapped to the "top" of the heap | |
after a removal operation to restore the heap | |
*/ | |
int index = 0; | |
/* | |
Since a binary heap is a complete binary tree, if we have no left child | |
then we have no right child. So we continue to bubble down as long as | |
there is a left child. | |
A non-existent left child immediately tells us that a right child does | |
not exist. | |
*/ | |
while (hasLeftChild(index)) { | |
/* | |
By default assume that left child is smaller. If a right | |
child exists see if it can overtake the left child by | |
being smaller | |
*/ | |
int smallerChildIndex = getLeftChildIndex(index); | |
if (hasRightChild(index) && rightChild(index) < leftChild(index)) { | |
smallerChildIndex = getRightChildIndex(index); | |
} | |
/* | |
If the item we are sitting on is < the smaller child then | |
nothing needs to happen & sifting down is finished. | |
But if the smaller child is smaller than the node we are | |
holding, we should swap and continue sifting down. | |
*/ | |
if (heap[index] < heap[smallerChildIndex]) { | |
break; | |
} else { | |
swap(index, smallerChildIndex); | |
} | |
// Move to the node we just swapped down | |
index = smallerChildIndex; | |
} | |
} | |
// Bubble up the item we inserted at the "end" of the heap | |
private void siftUp() { | |
/* | |
We will bubble up the item just inserted into to the "bottom" | |
of the heap after an insert operation. It will be at the last index | |
so index 'size' - 1 | |
*/ | |
int index = size - 1; | |
/* | |
While the item has a parent and the item beats its parent in | |
smallness, bubble this item up. | |
*/ | |
while (hasParent(index) && heap[index] < parent(index)) { | |
swap(getParentIndex(index), index); | |
index = getParentIndex(index); | |
} | |
} | |
/************************************************ | |
Helpers to access our array easily, perform | |
rudimentary operations, and manipulate capacity | |
************************************************/ | |
private void swap(int indexOne, int indexTwo) { | |
int temp = heap[indexOne]; | |
heap[indexOne] = heap[indexTwo]; | |
heap[indexTwo] = temp; | |
} | |
// If heap is full then double capacity | |
private void ensureExtraCapacity() { | |
if (size == capacity) { | |
heap = Arrays.copyOf(heap, capacity * 2); | |
capacity *= 2; | |
} | |
} | |
private int getLeftChildIndex(int parentIndex) { | |
return 2 * parentIndex + 1; | |
} | |
private int getRightChildIndex(int parentIndex) { | |
return 2 * parentIndex + 2; | |
} | |
private int getParentIndex(int childIndex) { | |
return (childIndex - 1) / 2; | |
} | |
private boolean hasLeftChild(int index) { | |
return getLeftChildIndex(index) < size; | |
} | |
private boolean hasRightChild(int index) { | |
return getRightChildIndex(index) < size; | |
} | |
private boolean hasParent(int index) { | |
return getParentIndex(index) >= 0; | |
} | |
private int leftChild(int index) { | |
return heap[getLeftChildIndex(index)]; | |
} | |
private int rightChild(int index) { | |
return heap[getRightChildIndex(index)]; | |
} | |
private int parent(int index) { | |
return heap[getParentIndex(index)]; | |
} | |
/***********************************************/ | |
private void printUnderlyingArray() { | |
System.out.print("[ "); | |
for (int item: heap) { | |
System.out.print(item + " "); | |
} | |
System.out.print("]"); | |
} | |
} | |
} |