Binary Heap

It is a binary tree. Root is MAX.

What is making Binary Heap which is so great ?

• Extremely Fast: Extract Max : O(1)
• Compact
• Few lines

public class MaxIntHeap {
    private int capacity =10;
    private int size = 0;
    private int[] items = new int[capacity];

    public void insert(int item) {
        this.ensureCapacity();
        items[size] = item; // put in last spot
        size ++;
        heapifyUp();
    }

    public void heapifyUp(){
        int index = size -1; //start at last element
        // while my parents are less than me
        while (hasParent(index) && parent(index) < items[index]) {
            swap(parentIndex(index), index);
            index = parentIndex(index); // walk upwards to next node
        }
    }

    public void heapifyDown(){
        int index = 0; // start at the top

        while(hasLeftChild(index)) {

            // take the larger of the two indexes
            int smallerChildIndex = leftChildIndex(index);
            if(hasRightChild(index) && rightChildIndex(index) > leftChildIndex(index)) {
                smallerChildIndex = rightChildIndex(index);
            }

            // now compare
            // if I am smaller than the items of my two children..
            // then everything is good. I am sorted
            if(items[index] > items[smallerChildIndex]) {
                break;
            }else {
                // we are still not in order - swap
                swap(index, smallerChildIndex);
            }
            // then move down to smaller child
            index = smallerChildIndex;

        }
    }

    public int extractMax() {
        if(size == 0) throw new IllegalStateException();
        int item = items[0]; // grab max
        items[0] = items[size -1]; // swap top and bottom
        size --;
        heapifyDown(); // re-order
        return  item; // return max
    }

    private int leftChildIndex(int parentIndex) {return 2 * parentIndex +1;}
    private int rightChildIndex(int parentIndex) {return 2 * parentIndex +2;}
    private int parentIndex(int childIndex) {return (childIndex-1)/2;}

    private boolean hasLeftChild(int index) {return  leftChildIndex(index) < size;}
    private boolean hasRightChild(int index) {return  rightChildIndex(index) < size;}
    private boolean hasParent(int index) {return  parentIndex(index) > 0;}

    private int parent(int index) {
        return items[parentIndex(index)];
    }

    private void swap(int xIndex, int yIndex) {
        items[xIndex] = items[yIndex];
    }

    private void ensureCapacity() {
        if(size == capacity) {
            items = Arrays.copyOf(items, capacity *2);
            capacity *=2;
        }
    }
}

Summary

• Peek : O(1) – extract max
• Heap Order
  • Insert – Up
  • Extract – Down
• Use cases : Priority Queues (Scheduling) , Priority routing