Computer Science 15-111 (Sections A & B), Spring 2007

Class Notes: 09-Apr-2007

Logistics:

1. Quiz 7 is Wednesday
Covers Trees, Binary Trees, Binary Search Trees, Expression Trees, Maps, HashMaps, TreeMaps, Sets, HashSets, TreeSets,

2. Test 2 is Wednesday April 18^th (9 days from today). It is comprehensive.

3. Final Call for hw8 Partners (email me by noon today)

4. Reminder: Read your email for hw8 Q&A’s!!!

5. Reading:
Wikipedia page on Heaps
Note: you are responsible for insert and remove operations, not for increaseKey or merge, nor for heap variants.

Topics:

1. Quiz 6 – Part 1 (return and review)

2. Heaps

a. The heap property
Partially-sorted complete binary tree.

b. Insert
add at end of last row, then percolate up

c. Remove
return root, move last node to root, percolate down

3. Implementation

a. Linked structure (tree)

b. Array structure

4. Applications

a. PriorityQueue

i. Enqueue(Object obj, int priority)
Add to heap according to priority

ii. Dequeue()
Return root and reheap (or “heapify”)

b. HeapSort

i. Add all elements to heap, then remove them in order.

ii. average-case = worst-case = O(nlogn)

iii. But, unlike mergesort, this is in-place!

iv. What is the best-case of HeapSort? Is it stable? Parallelizable?

c. Best-First Search

i. Search with a Stack: Depth-First Search

ii. Search with a PriorityQueue: Best-First Search

iii. Search with a Queue: Breadth-First Search

d. Graph Algorithms (which we will visit later)

i. Prim’s Minimal Spanning Tree Algorithm

ii. Dijkstra’s Shortest Path Algorithm