A Heap/Binary Heap is a data structure that takes the form of Binary Tree. Heaps are commonly used to implement priority queues (check out the PriorityQueue class in Java). Priority queues are great ways to identify the highest (or lowest) priority items in a collection.

A Max Heap is a binary tree data structure in which the root node is the largest/maximum in the tree. This means the root node will be >= to all others. As seen the example below, all objects in our max heap implement the Comparable interface.

Implementing a Max Heap using an Array

The most common (and generally very efficient) way to implement a max heap is by using an array. There are 4 major methods for implementing a max heap. These include add(), remove(), siftUp(), and siftDown() which are explained below.

The add() Method

When objects are first added to the heap they are initially added to the end of the heap. When using a traditional binary tree structure objects are added to the tree from top to bottom then left to right. When using an array, as we are in this example, objects are added to the end of the array. The final location in the tree or array depends on how the object compares to the others. Since the the object is initially inserted at the end of the array, we use the siftUp() method to move it to its new location.

The siftUp() Method

The siftUp() method is used to move a newly inserted object from the last position in the array to its final location. It works by comparing the newly inserted object to its parent. Remember, we are using an array here to simulate a tree data structure. To find and object’s parent within the array we can use the formula parentIndex = childIndex/2.

Since we are building a max heap, if the child object is larger than the parent, we swap the two objects within the array. We continue doing this until the child object is no longer larger than the parent, or the child becomes the largest in the heap (located at the front of the array).

The remove() Method

Removing a node from the max heap will remove (and return) its largest object. The remove() method removes the root object (or first object in the array). This root object is immediately replaced with the last object in the heap.

Most likely, this new root object is no longer the largest in the heap. This newly added root object is moved to its final location using the siftDown() method, which is explained below.

The siftDown() Method

The siftDown() method is used to move the newly added root object (or first object in the array) to its correct position. It works by comparing the root object to its children. Remember, we are using an array to simulate a tree data structure. To find an object’s children within the array we can use the formula leftChild = 2 * nodeIndex + 1 and rightChild = 2 * nodeIndex + 2.

Because we are building a max heap, if the parent object is smaller than either of its children, the parent object is swapped with the larger of its children. We continue these compare and swap steps until the parent object is no longer smaller than its children, or the original root object becomes the smallest in the heap (located at the end of the array).

The Code

package com.bigdatums.interview;

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class MaxHeapArray<T extends Comparable<T>> {
    private ArrayList<T> items = new ArrayList<T>();

    public void insert(T item) {
        items.add(item);
        siftUp();
    }

    private void siftUp() {
        int k = items.size() - 1;

        while(k > 0) {
            int p = (k - 1) / 2;

            T child = items.get(k);
            T parent = items.get(p);

            if (child.compareTo(parent) > 0) {
                //swap
                items.set(k, parent);
                items.set(p, child);

                //adjust k
                k = p;
            } else {
                break;
            }
        }

    }

    private void siftDown() {
        int k = 0;
        int left = 1;

        while(left < items.size()) {
            int max = left;
            int right = left + 1;
            if(right < items.size()) {
                if(items.get(right).compareTo(items.get(left)) > 0) {
                    max = right;
                }
            }
            T parent = items.get(k);
            T child = items.get(max);

            if(parent.compareTo(child) < 0) {
                //swap
                items.set(k, child);
                items.set(max, parent);

                k = max;
                left = 2*k+1;
            }
            else {
                break;
            }
        }
    }

    public T remove() throws NoSuchElementException {
        if(items.size() == 0) {
            throw new NoSuchElementException();
        }
        else if (items.size() == 1) {
           return items.remove(0);
        }

        T tmp = items.get(0);
        items.set(0, items.remove(items.size()-1));
        siftDown();
        return tmp;
    }

}