Heaps

Heap Implementation

Heaps are typically implemented with a data structure such as an array or Python list. These sequential structures allow access to elements in a particular order which is key to efficient use of heaps. Although binary trees are helpful for understanding the relationships between nodes of a heap, implementation using a tree is less efficient for storage and retrieval of elements.

Adding Elements: Heapify Up

When a new element is added to a heap, if heap properties are violated, the new child must swap with its parent until both child and root properties are restored. This process is called heapifying up, because of the upwards movement of the new element in this restorative process.

An example of the heapifying up process; adding an element to a heap.

The initial heap: the root value is 2, its left child value is 5, and its right child value is 10.
The value 5 has two children, its left child value is 11, and its right child value is 14.
On the right side of the heap, the value 10 has two children, its left child value is 20, its right child value 12.

We want to add 3 to the heap which starts as the left-most child value, as a child of the value 11.

First we compare 11 to 3. Since 3, the child value, is less than the parent value, 11, we will swap the values and make 11 a child value of 3. Next, we compare 3 to its new parent value, 5. Because the child value is less than its parent we swap the 3 and 5. Finally, we compare 3 to its new parent value, 2, which is the root. Because 3 is greater than 2 we do not need to swap the values.

Our final heap is as follows:
The root is 2. 2 has two children, the left child is 3, the right is 10.
3 has two children, the left is 5 and the right is 14.
5 has one child, 11.

The right side of the heap remains the same.

Heaps as Binary Trees

A proper representation of a heap is a complete binary tree, which is a tree whose nodes have at most two children, and whose levels are filled completely from left to right (with no gaps in children). It’s possible for the last level to be semi-completely filled, but all of its nodes are as far left as possible.

Java MinHeap Behavior

A min-heap can be implemented in Java by creating a MinHeap class with these methods. Each adjusts the heap in a different way.

a constructor with heap and size properties
an .add() method that adds an element to the heap
a .popMin() method that returns the minimum value in the heap
a .bubbleUp() method that maintains the min-heap condition after addition
a .heapify() method that maintains the min-heap condition after removal

This class also includes multiple helper methods that allow for the proper functionality of the class methods.

public class MinHeap {
	public ArrayList<Integer> heap;
	public int size;
  
  public MinHeap() 
    
  public void add(int value)
  
  public int popMin() 
    
  private void bubbleUp()
  
  private void heapify()
  
}

Java MinHeap: popMin()

The .popMin() method of the Java MinHeap class removes and returns the minimum value in the heap, which is at the top. It does so using the MinHeap helper method .swap() and the LinkedList method .remove(). The .popMin() method also decreases size and calls .heapify() to reorganize the heap after the removal. If the heap is empty, .popMin() throws an error. This method does not take any arguments.

public int popMin() {
    if (this.size == 0) {
        throw new Error("Heap is empty!");
    }
    this.swap(1, this.size);
    int min = this.heap.remove(this.size);
    this.size--;
    this.heapify();
    return min;
}

Java MinHeap: add()

The .add() method of the Java MinHeap class takes one value as an argument and adds this value to the end of the heap using the LinkedList .add() method. It then increases size and calls .bubbleUp(). This call ensures that the newly added value finds its proper place in the heap.

public void add(int value) {
    this.heap.add(value);
    this.size++;
    this.bubbleUp();
}

Java MinHeap: bubbleUp()

The .bubbleUp() method of the Java MinHeap class “bubbles up” (moves up) the last value added to the heap until it is at the correct place in the heap using the MinHeap helper method, .swap(). The placement ensures that the min-heap condition is maintained. The .bubbleUp() method does not take any arguments and does not return anything. It should be declared as private.

private void bubbleUp() {
    int current = this.size;
    while (current > 1 && this.heap.get(current) < this.heap.get(this.getParent(current))) {
        this.swap(current, this.getParent(current));
        current = this.getParent(current);
    }
}

Java MinHeap: heapify()

The .heapify() method of the Java MinHeap class maintains the min-heap condition after a value is removed from the heap using .popMin(). It does so by comparing the new root node value with its children; if it is greater than its children, it swaps with the lesser child using the MinHeap helper method .swap(). If it is less than both its children, no swapping is necessary. It continues to do this until the min-heap condition is met. The .heapify() method does not take any arguments and does not return anything. It should be declared as private.

private void heapify() {
    int current = 1;
    int leftChild = this.getLeft(current);
    int rightChild = this.getRight(current);

    while (this.canSwap(current, leftChild, rightChild)) {
        if (this.exists(leftChild) && this.exists(rightChild)) {
            if (this.heap.get(leftChild) < this.heap.get(rightChild)) {
                this.swap(current, leftChild);
                current = leftChild;
            } else {
                this.swap(current, rightChild);
                current = rightChild;
            }
        } else {
            this.swap(current,leftChild);
            current = leftChild;
        }
        leftChild = this.getLeft(current);
        rightChild = this.getRight(current);
    }
}

Java MinHeap: Constructor

The constructor for the Java MinHeap class instantiates two instance variables:

heap, an ArrayList of integers representing the nodes of the heap, initially filled with just one value, null
size, an integer value that keeps track of the current size of the min-heap, initially set to 0

public MinHeap() {
    this.heap = new ArrayList<Integer>();
    this.heap.add(null);
    this.size = 0;
}

Java MinHeap: Helper Methods

The Java MinHeap class should implement helper methods to access the indices of the parent, left child and right child of any element in the heap. These methods are provided in the class.

.getParent() returns the index of the parent of the current element
.getLeft() returns the index of the left child of the current element
.getRight() returns the index of the right child of the current element

These helper methods are used in the MinHeap class methods .bubbleUp() and .heapify()

public int getParent(int current) {
    return (int) Math.floor(current / 2);
}

public int getLeft(int current) {
    return current * 2;
}

public int getRight(int current) {
    return (current * 2) + 1;
}