Nothing special here. It’s just a blog post for summarising my algorithm learning course. Probably this was taught in the University but I don’t remember anything, I have no idea about its definition and applications until I take this course.

Heap-ordered Binary Tree

• Each node represents a key
• Parent’s key is not smaller than children’s keys

Array Representation

Taking the tree above in level order gives the array below. Index 0 is left unused so that the parent/child arithmetic stays simple:

• Indices start at 1.
• Take nodes in level order.
• No explicit links needed!
• Largest key is a[1], which is root of binary tree
• Can use array indices to move through tree
  • Parent of node at k is at k/2
  • Children of node at k are at 2k and 2k+1

Promotion in a heap

• Scenario: Child’s key becomes larger key than its parent’s key.
• To eliminate the violation:
  • Exchange key in child with key in parent.
  • Repeat until heap order restored.
• In the below image, the 5th item T is not in the correct order
  • T is larger than P (its parent), exchange
  • T is still larger than S (its parent), exchange
  • Finally, T is in the correct order

T starts at index 5. Since it is larger than its parent P (index 2) it swims up, and it is still larger than the new parent S (index 1), so it swims up once more to become the root:

Before swim:

After swim:

private void swim(int k) {
    while (k > 1 && less(k/2, k)) {
        exch(k, k/2);
        k = k/2;
    }
}

Insertion in a heap

• Add node at end, then swim it up.
• Cost: At most 1 + lgN compares.

Inserting T adds it at the next free slot (index 7), then swims it up until heap order is restored:

New key added at the end:

After swimming up:

public void insert(Key x) {
    pq[++N] = x;
    swim(N);
}

Demotion in a heap

• Scenario: Parent’s key becomes smaller than one (or both) of its children’s.
• To eliminate the violation:
  • Exchange key in parent with key in larger child.
  • Repeat until heap order restored.
• In the below image, the 2nd item H is not in the right order
  • H is smaller than its children, exchange with the larger child S
  • H is still smaller than its children, exchange with the larger child N
  • Finally, H is in the correct order

H starts at index 2. It is smaller than its children, so it sinks by swapping with the larger child S (index 4), and then again with the larger child N (index 8):

Before sink:

After sink:

private void sink(int k) {
    while (2*k <= N) {
        int j = 2*k;
        // children of node at k are 2k and 2k+1, decide which one is larger
        if (j < N && less(j, j+1)) j++;
        // when the item is in the right order, stop
        if (!less(k, j)) break;
        // otherwise, exchange
        exch(k, j);
        k = j;
    }
}

Delete the Maximum in a heap

• Exchange root with node at end, then sink it down.
• Cost: At most 2 lgN compares.

The max T is swapped with the last node E, then removed. E now sits at the root and sinks down until the heap order is restored:

Before delMax (swap root with last node):

After removing T and sinking E:

public Key delMax() {
    Key max = pq[1];
    exch(1, N--);
    sink(1);
    // prevent lotering
    pq[N+1] = null;
    return max;
}

To be continued

Part 2 Binary Heap and Heapsort Summary - Part 2 - Heapsort