Outline 17: Heap Sort

Held: Monday, 5 October 2015

Summary

We consider the famous heap-sort routine.

Related Pages

Overview

Administrivia

Five problems. Blind grading.
Problem 1: Find an algorithm with a triply-nested loop and do the summation analysis.
Problem 2: For the recurrence relation .... (a) draw the recurrence tree, (b) solve using master theorem or estimate using top-down or bottom-up models; (c) prove.
Problem 3: Three proofs involving big-O notation
- I can drop the lower order term: if f(n) is in O(g(n)) and h(n) is in O(f(n) + g(n)) then h(n) is in O(g(n) )
- I don't care about constant multipliers if f(n) is in O(c*g(n)) then f(n) is in O(g(n))
- I can combine functions if f(n) is in O(g(n)) and h(n) is in O(g(n)) then (f(n) + h(n)) is in O(g(n))
- Optional: If f(n,k) is in O((n-1)(k-1)), then f(n,k) is in O(nk).
Problem 4: Show the correspondence between insertion in 2-3-4 trees and insertion in red-black trees.
Problem 5: Merge sort with only n/2 scratch space.

Background

We are considering O(nlogn) sorting algorithms.
Merge sort is guaranteed O(nlogn), but requires O(n) extra space.
Quicksort requires O(1) extra space, but is not guaranteed to be O(nlogn)
Can we have something that uses O(1) extra space and is guarateed O(nlogn)
Priority queues provide obvious sorting algorithms
A really good implementation of priority queues can give a fast sorting algorithm
A spectacularly good implementation of priority queues can provide in-place sorting.

Something like search trees, but different.
Binary trees with the heap property
- Each node is at least as big as the roots of its subtrees.
- Each subtree also has the same property.
Binary trees that are nearly complete
- It's complete in the sense that most nodes have two children
- At the last level all the nodes are at the left.
Check in: Which of the following are heaps (drawn on whiteboard)

Two invariants to maintain: The shape of the tree and the heap property.
- Which is harder? Probably getting the shape right.
So we add an element at the end of the last level.
And then we restore the heap property by repeatedly swapping up.
Sample tree: Build with eight or so numbers.

The largest (highest priority) element is at the top.
Once we remove it, what do we do?
Once again, two invariants to maintain: The shape of the tree and the heap property.
So, we take the last element and put it at the root.
And then we swap it down to the right place?
- Repeatedly swap with the larger child (provided it's smaller than the larger child).
Exercise: Remove the three largest values from our tree.

But how do we know where the last element on the last row is (for both insertion and removal)?
Here's the really clever part: We can store heaps in arrays.
Can you figure out the index of children and parents?
And once we use arrays, we can build and destruct the heaps in place