Outline 49: Heaps

Held: Monday, 1 December 2014

Summary

We explore heaps, a useful and relatively efficient implementation of priority queues.

Related Pages

Overview

Administrivia

New partners (assuming I can find the cards)
I hope that you had a wonderful Thanksgiving break.
Sorry for the delay in getting the exam code out. We'll have time for questions on the exam today.
Random numbers for the exams distributed.
We will debrief on the project and the exam makeup on Friday.
- I should return the makeup exams before then.
I need eight relatively small integers from you for today's work.
We will talk about heaps today and then do a lab on them tomorrow.

Ajuna's Radio show Mondays at 8pm. Listen to African music. (TONIGHT)
Ezra's Radio show Thursdays at midnight. Radio melodrama.
Charlie's Friday Night "War in Animated Film" ExCo.
Women's Basketball, Saturday vs. Lake Forest, Sunday vs. Presentation.
December 4 and 5: Dance show (Once Upon a Time, Splintered), with vocals by Noteworthy and dancing lights by our own ZW.
One Acts on December 5 and 6 with our own EE.

Structure
- Short introduction to the problem (Sam)
- Individual presentations (5 minutes each, 1-2 minute evals)
- Voting!
  - If you needed to hire someone to develop a scheduling application, which team would you hire?
  - If you had to develop a scheduling application, which codebase would you want to start with?
Slots 1. 2. 3. 4. 5. 6.
Email me your presentations (4 slides, including title) by 11 p.m. on Tuesday evening.
Your goals:
- Core: Explain the algorithm you've designed.
- Sales: Distinguish your work from that of your peers.
- (You may also want to distribute the schedule you've created.)
Audiences
- Your peers.
- Students who might be called upon to generalize your code or write a UI for your code.
- The director of the midwest conference (I hope).

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?

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?
- It turns out that both will help.
Binary search trees are cool, but would be cooler if we could keep them balanced.

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?

Sorting using heaps. Turn the array into a heap. Then repeatedly grab the top element and put it at the end.