# The Angry Birds — Mighty Eagle

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

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

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

`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’tset 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.