The Angry Birds — Mighty Eagle

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

OMAR ELGABRY
Jan 21, 2017 · 3 min read
Mighty Eagle — angrybirds

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).

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
}

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.

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

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.

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.

  • 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).

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.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

OMAR ELGABRY

Written by

Software Engineer. Going to the moon 🌑. When I die, turn my blog into a story.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade