CSC301.01 2015F, Class 17: Heap Sort
====================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Background.
* Heaps.
* Inserting into Heaps.
* Removing from Heaps.
* Heap Sort.

Preliminaries
-------------

### Admin

* How well do you remember heaps and heap sort?
    * Really well
    * Somewhat
    * Barely

### Upcoming Work

* For Wednesday: Work on the Exam
* For next Wednesday: The Exam

### Extra Credit

* Don't forget that you can send these to me in advance!

#### Academic

* CS Table Tuesday at noon: NSA Barbie
* CS Table Thursday: Blake

#### Peer

### Exam 1

* 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 T(N) <= 2T(N/3) + T(2N/3) + cN
  (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.

### Questions

Is this Sam's normal: "Use any reasonable resource, but no posting questions?"

> Yes.

Lower Bounds on Comparison-Based Sorting

n! leaves = Theta(2^(nlogn))

Weak proof by induction:

Base cases: n = 1, n = 2

Inductive cases: 

* Step 1: n! = n*((n-1)!)
* Inductive hypotheseis: (n-1)! =~ 2^((n-1)log(n-1))
* Step 2: n! =~ n * 2^((n-1)log(n-1))
* n! =~ 2^(logn) * 2^((n-1)log(n-1))
* n! =~ 2^(logn) * 2^((n-1)log(n)*(log(n-1)/log(n)))
* For sufficiently large n, log(n-1)/log(n) is pretty damn close to 1
* n! =~ 2^(logn) * 2^((n-1)log(n))
* n! =~ 2^(logn + (n-1)log(n))
* n! =~ 2^(nlogn)

Proof by Authority: According to famous people like Knuth, n! =~ 2^(nlogn)

The tree has 2^(nlogn) leaves.  The minimum height of a tree with k leaves
is log(k).  So, the tree has minimum height log(2^(nlogn)) = nlogn.

Background
----------

* Merge sort: O(nlogn), but O(n) space
* Quicksort: O(1) space, O(nlogn) *expected* running time,
  complex analysis; some bad cases - If you pick pivots badly, it's
  O(n^2)
    * Pick randomly - really complex analysis
    * Pick the first element in the subarray, but permute the array
      randomly first. - similarly complex analysis
* Heapsort: O(nlogn) always, O(1) extra space

Heaps
-----

Key ideas:

* Heaps are binary trees with certain properties
     * The value in a node is higher priority than the values of the nodes
       below it (higher priority might be "larger" or "smaller" or ...)
     * The tree is *nearly* complete
         * Either complete or ...
         * All but the bottom level are complete and last level is
           all at the left.
* Heaps implement priority queues
* We can store heaps in arrays
    * Using a simple model of where children go
* If we can implement insert and remove in O(height), we get O(nlogn)
  sorting by: INSERT EVERYTHING; REMOVE EVERYTHING IN ORDER

Inserting into Heaps
--------------------

* Two properties to maintain.  Which is harder?  It turns out that
  nearly complete is harder.
* So put the new value in where it maintains near completeness
* Now, restore the other property; Repeatedly swap with parent if higher
  priority than parent

Removing from Heaps
-------------------

* Two properties to maintain: near completeness and heap property
* Maintain near completeness by putting the rightmost bottom element
  at the top
* Repeatedly swap with higher priority child until swapping is done

Heap Sort
---------

* Put all the values in an array (or start with all the values in the
  array) using breadth-first ordering of nodes.
* Turn the array into a heap by calling swap-up from postions 1 to n-1

        for k = n-1 down to 1
          swap(A, 0, k)
          swapDown(A, 0)

* This requires us to be able to identify the indices of children and
  parent

        left child of value at position k: 2k+1
        right child of value at position k: 2k+2
        parent of value at position k: floor((k-1)/2)