2010 November 3 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

Assignment: Heaps

Carleton College CS 201, Prof. Joshua R. Davis

Introduction

The goal of this assignment is to implement a priority queue using a binary heap. This topic is covered in your textbook. In fact, the textbook provides code to implement the whole thing. However, our priority queue differs from the book's in several ways:

• Our naming scheme for the class and its methods is different from the book's. Our naming scheme emphasizes the purpose of the data structure (i.e., it's a priority queue) rather than the implementation (i.e., a binary heap), because that's what our users care about.
• Our class supports an increasePriority method; the book's does not.
• For us, high priorities are large numbers (e.g. 17 is higher-priority than 12); in the textbook, high priorities are small numbers (e.g. 12 is higher-priority than 17).
• The textbook's implementation wastes the 0-entry in the heap list, for no good reason. We will not.
• I require you to implement percolation recursively.

You will complete this assignment with an assigned partner. It is due Sunday at 11:59 PM.

Implement PriorityQueue

On the course web site, download the file priorityqueue_avltn.py. Rename it to priorityqueue_heap.py; this is the file you'll be editing and handing in.

You need to change the docstring for the PriorityQueue class. The AVL tree implementation handles equal priorities in a FIFO manner, but our heap implementation will not. Change the docstring to reflect this. What does this mean for our users? The users should not assume that all implementations of PriorityQueue break ties FIFO; some do, and some don't. We're very forthright about this issue, so the users can't complain.

Now rewrite all of the methods of PriorityQueue. Do not change any docstrings; the methods should work exactly as they do in the AVL tree PriorityQueue (with the exception of the FIFO behavior). I have some specific requirements.

• You must implement PriorityQueue using a binary heap stored as a list. The list must be indexed from 0, not 1 as in our textbook. As we've discussed in class, the children of node i are nodes 2 i + 1 and 2 i + 2. The parent of node i is node (i - 2) / 2 or node (i - 1) / 2, depending on whether i is even or odd.
• Your initialization method must build the heap using the fast heap-building algorithm discussed in class, rather than manually enqueueing everything.
• You must add methods percolateUp and percolateDown. They must be implemented recursively. Their docstrings should state that they are "private" — meaning, they exist for the class' own use and should not be used by users. Even though they are private, they should still have clear, detailed docstrings. (Why? For whom?) In general, when implementing a data structure you are allowed to add whatever private methods you like; they don't change the data structure's public interface.

Submit Your Work

Submit your file priorityqueue_heap.py electronically as usual. It will be graded according to these criteria:

• The priority queue works (6 points).
• The code exhibits Good Python Style (3 points).