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

• 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

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.

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

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.

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