---
description: 'Operations: swim and sink.'
---

# 2.2. Binary Heap

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:&#x20;

* The index of its parent: $$\lfloor \frac{k}{2} \rfloor$$&#x20;
* 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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/BinaryHeap.java) class inheriting `AbstractPriorityQueue`:

{% code lineNumbers="true" %}
```java
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;
    }
}
```
{% endcode %}

* `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:

{% code lineNumbers="true" %}
```java
/**
 * @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));
}
```
{% endcode %}

* `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:

{% code lineNumbers="true" %}
```java
@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);
}
```
{% endcode %}

* `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()`](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Collections.html#swap\(java.util.List,int,int\)) them.

{% embed url="https://www.slideshare.net/jchoi7s/dsajava-binary-heap-add-238005046" %}
[https://www.slideshare.net/jchoi7s/dsajava-binary-heap-add-238005046](https://www.slideshare.net/jchoi7s/dsajava-binary-heap-add-238005046)
{% endembed %}

> 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:

{% code lineNumbers="true" %}
```java
@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);
    }
}
```
{% endcode %}

* `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.

{% embed url="https://www.slideshare.net/jchoi7s/dsajava-binary-heap-remove-238005081" %}
[https://www.slideshare.net/jchoi7s/dsajava-binary-heap-remove-238005081](https://www.slideshare.net/jchoi7s/dsajava-binary-heap-remove-238005081)
{% endembed %}

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