How to implement a binary heap in java ?

A binary heap is a complete binary tree which satisfies the heap ordering property.

There are two types of heap :

  • Max heap : Every parent is greater than or equal to its children
  • Min heap: every parent is less than or equal to its children

A binary heap must be a complete tree,children are added at each level from left to right,and usually implemented as arrays.The maximum or minimum value will always be at the root of the tree, this is the advantage of using a heap.

For Heapify,the process of converting a binary tree into a heap,is often has to be done after an insertion or deletion.

To implement the heaps as arrays:

  • We put the root at array[0]
  • Then we traverse each level from left to right,and so the left child of the root would go into array[1],its right child would be into array[2],etc.

For the node at array[i], we can get left child using this formula (2i + 1), for the right child we can use this one (2i + 2),and for parent item floor((i — 1) / 2).This works just with complete binary trees.

To insert into heap :

  • Always add new items to the end of the array
  • Then we have to fix the heap(heapify process)
  • We compare the new item against its parent
  • If the item is greater than its parent, we swap it with its parent
  • We then rinse and repeat

Example of implementation in java :

public class Heap {

private int[] heap;
private int size;

public Heap(int capacity) {
heap = new int[capacity];
}

public void insert(int value) {
if (isFull()) throw new IndexOutOfBoundsException("Heap is full");

heap[size] = value;

fixHeapAbove(size);
size++;
}

private void fixHeapAbove(int index) {
int newValue = heap[index];

while (index > 0 && newValue > heap[getParent(index)]) {
heap[index] = heap[getParent(index)];
index = getParent(index);
}

heap[index] = newValue;
}

public boolean isFull() {
return heap.length == size;
}

public int getParent(int index) {
return (index - 1) / 2;
}
}

As a conclusion,in java JDK we have PriorityQueue, an unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at queue construction time, depending on which constructor is used.