What is a Heap?

A heap is a specialized data structure that is designed to always yield the smallest element in O(lg(n)) time (assuming it is a min-heap; a max-heap would do the opposite.

It is logically represented as a balanced binary tree with all the elements shifted as left as possible. Practically it is represented as an array because it is actually very easy to map a left-shifted binary tree into an array. The left child of any node is index 2 * N + 1 in the array and the right child of any node is index 2 * N + 2 of the array.

The O(lg(n)) retrieval time of a min or max element makes heaps ideal to be used as a priority queue.

How Does it Work?

The key to it providing this performance is that all elements are stored in such way that every element is guaranteed to be less than either of its child elements (so, logically this means the root is the smallest element). If it was a max-heap the opposite would be true.

It accomplishes this in a pretty simple way. Let’s say we’re using a min-heap:

• The smallest element will be at the root of the tree.
• So, to get the next smallest element, we just:
  • Take the root of the tree.
  • Move the last element in the tree (the rightmost leaf node)
    up to where the root element was.
  • Repeatedly switch this node with any nodes below it that are
    less than it (this is called “percolating down”.
  • Taking the root takes O(1) time, and percolating down at most
    takes the height of the tree, which for a binary tree is O(lg(n)).
    So, this is how we get O(lg(n)) time for taking each element.
• If we want to insert new elements, we basically do the opposite:
  • Add the new element at the last position of the tree.
  • Repeatedly switch it upwards if it is less than its parent.
  • This is called “percolating up” and also is O(log(n)) time since
    it is also dependent on the height of the tree.

Creating a Heap

Surprisingly, a heap can actually be constructed in linear time O(n) from an existing array of objects.

This is a little time consuming to prove, so please refer to the method here: https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/.

Implementation

Here is a full sample implementation of a heap (minus the construction of a heap from an existing array; in this case we just build it up using add and remove).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

public class MinHeap<T extends Comparable> {

    private List heap;

    public MinHeap() {
        heap = new ArrayList();
    }

    //Add to end, percolate up to correct position.
    public void add(T value) {
        heap.add(value);

        for (int index = heap.size() - 1; index > 0; index = index / 2) {
            int parent = index / 2;
            if (heap.get(index).compareTo(heap.get(parent)) < 0) {
                T temp = heap.get(index);
                heap.set(index, heap.get(parent));
                heap.set(parent, temp);
            }
        }
    }

    private static int getLeft(int i) { return i * 2 + 1; }
    private static int getRight(int i) { return i * 2 + 2; }

    //Take from top, move last element to root, percolate down.
    public T remove() {
        if (heap.size() == 0) throw new NoSuchElementException();
        T result = heap.get(0);

        //Remove the last element.  If this makes the heap empty,
        //then just return the result.
        T last = heap.remove(heap.size() - 1);
        if (heap.size() == 0) return result;

        //If we got here, the heap still has elements, so add the last
        //element to the root (0) and percolate down.  Percolating down
        //means swapping the root with its children recursively until
        //it is smaller than both of its children.
        heap.set(0, last);
        int i = 0;
        while (i = getRight(i)) {
                T leftChild  = heap.get(getLeft(i));
                T rightChild = heap.get(getRight(i));
                if (leftChild.compareTo(rightChild) > 0) {
                    minChildIndex = getRight(i);
                }
            }
            if (heap.get(i).compareTo(heap.get(minChildIndex)) > 0) {
                T temp = heap.get(i);
                heap.set(i, heap.get(minChildIndex));
                heap.set(minChildIndex, temp);
                i = minChildIndex;
            }
            else break;
        }

        return result;
    }

    public boolean isEmpty() { return heap.isEmpty(); }

    public static void main(String[] args) {
        MinHeap h = new MinHeap();
        Arrays.asList(7, 6, 2, 9, 8, 17, 46, 12, 13, 1, 7)
            .forEach(h::add);
        while(!h.isEmpty()) { System.out.print(h.remove() + " "); }
        System.out.println();

        Arrays.asList(7, 6, 2, 9, 8, 17, 46, 12, 13, 1, 7, 51)
            .forEach(h::add);
        while(!h.isEmpty()) { System.out.print(h.remove() + " "); }

        System.out.println();
        h.add(1);
        while(!h.isEmpty()) { System.out.print(h.remove() + " "); }
    }
}

Attributions

• Image Taken From: https://commons.wikimedia.org/wiki/File:Max-Heap.svg