Held: Monday, 2 December 2013
Back to Outline 48 - Hash Tables, Continued.
On to Outline 50 - Heap Sort.
Summary
We explore heaps, an alternate implementation of priority queues.
Related Pages
Overview
- Priority queues, revisited.
- Recent implementation techniques.
- Heaps.
- Adding elements to heaps.
- Removing elements from heaps.
- Heap sort.
Administrivia
- Exam 2 returned.
- I tried to be very detailed in my comments, even though I used a
coarse-grained grading system.
- Please turn in your academic honesty statements.
- Please follow formatting conventions.
- I hope to distribute additional notes later this week.
- Upcoming extra credit opportunities:
- Learning from Alumni Thursday: Erik Hanson (in person)
- CS Extras Thursday: Multiple Models for Mediascripting (Manuella et al.)
- CS Table Friday: TBD.
- Any self-care week activity.
- One Grinnell rally on December 4 at 4pm (unless you are taking photos).
- And yes, I've sent a note to Dean Arora about the scheduling.
Priority Queues, Reviewed
- What is a priority queue?
- What are the primary operations?
- What are the implementations we have? What are the running times
of the key operations?
Implementation Techniques
- What are implementation techniques we've learned since we last looked
at priority queues?
- I know of two: We've started looking at trees and we've learned some
clever ways of using arrays (in hash tables).
- Will either help?
- Binary search trees are cool, but would be cooler if we could keep
them balanced.
Heaps
- Simplified binary search trees.
- 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.
Adding Elements
- 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.
Removing Elements
- The largest 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).
Using Arrays
- Here's the really clever part: We can store heaps in arrays.
Heap Sort
- Sorting using heaps. Turn the array into a heap. Then repeatedly grab
the top element and put it at the end.
