The Angry Birds — Mighty Eagle

In-spite of being one of the angry birds. Mighty Eagle has a secret power.

Mighty Eagle — angrybirds

This series of articles inspired by Algorithms, Part I course from Princeton University & Algorithms, 4th Edition. The full series of articles can be found here.

Heapsort

When insert all the keys to be sorted into a minimum-oriented priority queue, then repeatedly use remove the minimum to return them all in order. When using a heap for the priority queue, we obtain heapsort.

Focusing on the task of sorting an array, we are going to construct a max heap, and then repeatedly remove the max item so that we can have the array sorted (see implementation below).

Implementation

We’ll construct a max heap tree from an array with arbitrary order of items, then sortdown; where we repeatedly remove the max items.

public void sort(Comparable[] pq) {
    int N = pq.length;
    // 1. max heap construction
    // 2. sortdown
}

— heap construction (bottom-up)

Examine each parent node (leafs aren’t included) from bottom to up, right to left, If it’s smaller than one of it’s children, then do sink() on the parent node.

Why leafs aren’t included? Because leafs are already sorted in the max heap tree as long as it’s smaller than it’s parent. That’s why we do care only about parent nodes only.

Heap Construction — algs4.cs.princeton.edu

public void sort(Comparable[] pq) {
    int N = pq.length;
    // 1. max heap construction
    for (int k = N/2; k >= 1; k--)
        sink(pq, k, N);   // sink node at index k
}

Now, since every parent is greater than it’s children, we’ve constructed the max heap binary tree.

— sortdown

Repeatedly remove the max node and then do sink() on the root node.

Sortdown — algs4.cs.princeton.edu

public void sort(Comparable[] pq) {
    int N = pq.length;
    // 1. max heap construction (already done)
    // 2. sortdown
    while(N > 1){
        swap(pq, 1, N--);
        sink(pq, 1, N);
    }
}

Don’t set the last(removed) node to null, Why? We still need all the nodes; we’re just sorting them.

The implementation of heaps use 1-based index, while the given array pq is 0-based index. So, whenever you access an array element(i.e. In less() & swap() methods), just decrement the index by 1.

Analysis

Time →It uses 2 * NLogN compares and exchanges at the worst case, and NLogN at best case.

Memory →HeapSort is done in-place; no linear extra space needed.

Heapsort Vs Mergesort Vs Quicksort

• Mergesort: not in-place, but has guaranteed worst case O(NLogN).
• Quicksort: in-place, but the worst case is O(N²); can’t guarantee O(NLogN).
• Heapsort: both; in-place sort, and worst case guarantee O(NLogN).

Why Heapsort Isn’t Used A Lot?

Heapsort is optimal for both space and size, but …

• The inner loop(of sink operation) is longer than in Quicksort, because each node gets compared with it’s 2 children; two compares each done NLogN times.
• It makes poor use of cache memory since it points to nodes far away from each other, which in turn makes it slower in a lot of situations where caching is important. Unlike Quicksort, it checks nearby elements.
• It’s not stable.