COSC 350: Data Structures
April 8, 2009

Priority Queues and Heapsort

Complete binary tree—insert from left, fill level before going to next

Easily represent as a list without gaps, e.g., [None, root, left child of root, right child of root, left child of left child of root, right child of left child of root, ...]
Properties:
left child of any node n is at index 2n,
right child of any node n is at index 2n+1, and
parent of any node n is at index floor(n/2).

Heap Order Property—parent's key < children's keys

Operations (to preserve heap order property):
Insert—maintain a complete binary tree by inserting into last position,
then bubble up to maintain heap order (repeatedly exchange subtree's root with smallest child)
Delete—restore complete binary tree by swapping last item into deleted item's location,
then bubble down to maintain heap order

Homework

Friday, April 10: Bring in any questions you have for the test on Monday, April 13

Monday, April 13: Test—No homework

Wednesday, April 15: No homework, continue working on project

Friday, April 17: Sorting Project (Counts triple)

This page was created by Joe Sloan.
It was last modified on or after: 15 April 2009
Send mail to: sloanjd@wofford.edu