2.2. Binary Heap

Operations: swim and sink.

A binary heap is a PQ that takes$O(\log n)$for both add() and remove(), where keys are stored in a balanced binary tree in which every node has a higher priority than its children (when used as a max-PQ).

When should we use a binary heap over a lazy PQ or an eager PQ?

Balanced Binary Tree

A balanced binary tree can be implemented by a list such that given the $k$'th key in the list:

• The index of its parent: $\lfloor \frac{k}{2} \rfloor$

• The index of its left child: $2 \cdot k$.

• The index of its right child: $2 \cdot k + 1$.

• e.g., given the list [1, 2, 3, 4, 5], 1 is the root, 2 and 3 are the left and right children of 1, and 4 and 5 are the left and right children of 2, respectively.

Is the tree represented by the list [1, 2, 3, 4, 5] balanced?

Implementation

Let us create the BinaryHeap class inheriting AbstractPriorityQueue:

public class BinaryHeap<T extends Comparable<T>> extends AbstractPriorityQueue<T> {
    private final List<T> keys;

    public BinaryHeap() {
        this(Comparator.naturalOrder());
    }

    public BinaryHeap(Comparator<T> priority) {
        super(priority);
        keys = new ArrayList<>();
        keys.add(null);
    }

    @Override
    public int size() {
        return keys.size() - 1;
    }
}

• L11: adding null as the first item makes it easier to calculate the indices of parents and children.

• L16: keys has the extra item of null from L11 that is not an input key.

How does adding null make the calculation of the indices easier?

Additionally, let us define the helper method compare() that compares two keys in the list:

/**
 * @param i1 the index of the first key in {@link #keys}.
 * @param i2 the index of the second key in {@link #keys}.
 * @return a negative integer, zero, or a positive integer as the first key is
 * less than, equal to, or greater than the second key.
 */
private int compare(int k1, int k2) {
    return priority.compare(keys.get(k1), keys.get(k2));
}

• L8: calls the compare() method in the member field priority declared in the super class.

Add() with Swim

The add() method in a heap uses the operation called swim as follows:

@Override
public void add(T key) {
    keys.add(key);
    swim(size());
}

private void swim(int k) {
    for (; 1 < k && compare(k / 2, k) < 0; k /= 2)
        Collections.swap(keys, k / 2, k);
}

• L3: appends the new key to the list.

• L7-10: keeps swimming until the list becomes a heap:

  • L8: compares the new key to its parent if exists.

  • L9: if the new key has a higher priority than its parent, Collections.swap() them.

https://www.slideshare.net/jchoi7s/dsajava-binary-heap-add-238005046

How many keys are compared at most for the `add operation?

Remove() with Sink

The remove() method in a heap uses the operation called sink as follows:

@Override
public T remove() {
    if (isEmpty()) return null;
    Collections.swap(keys, 1, size());
    T max = keys.remove(size());
    sink();
    return max;
}

private void sink() {
    for (int k = 1, i = 2; i <= size(); k = i, i *= 2) {
        if (i < size() && compare(i, i + 1) < 0) i++;
        if (compare(k, i) >= 0) break;
        Collections.swap(keys, k, i);
    }
}

• L3: checks if the heap is empty.

• L4: swaps the root and the last key in the list.

• L3: removes the (swapped) last key with the highest priority in this heap.

• L10-16: keeps sinking until the list becomes a heap:

  • L12: finds the child with a higher priority.

  • L13: breaks if the parent has a higher priority than the child.

  • L14: swaps if the child has a higher priority than the parent.

https://www.slideshare.net/jchoi7s/dsajava-binary-heap-remove-238005081

How many keys are compared at most for the remove operation?