Priority Queues Using Heaps

Intro

As discussed in class, one of the ways we can implement a Priority Queue is with a Heap. As a reminder, a Heap is a binary tree that conforms to these rules:

1. all entries can be compared using the < operator applying strict weak ordering
2. the value of a given tree Node is never less than that of its children
3. the binary tree is complete

Complete Binary Tree as an Array

As it turns out, one of the most efficient ways that we can implement a complete binary tree is with an array because there is a simple mathmatical relationship that we can use to associate parents with their children (and vice versa) using their indices within the array, provided that they exist.

Using Zero-Based Indexing

To find the children of a node with index i:	To find the parents of a node with index i:
Index of the left child = 2i + 1 Index of the right child = 2i + 2	if i is ODD index of parent = (i - 1) / 2 if i is EVEN index of parent = (i - 2) / 2 Or ignore ODD and EVEN with integer math: index of parent = (i - 1) / 2

Using One-Based Indexing

To find the children of a node with index i:	To find the parents of a node with index i:
Index of the left child = 2i Index of the right child = 2i + 1	if i is ODD index of parent = i / 2 if i is EVEN index of parent = (i - 1) / 2 Or ignore ODD and EVEN with integer math: index of parent = i / 2

See Complete Binary Tree as an Array as a graphical backup to the description above.

Assignment

For this lab, you will complete the functions necessary to add and remove elements in a Priority Queue, as well as return information about the Priority Queue, such as the size, whether it's empty, etc.

Note: The Priority Queue's underlying complete binary tree is implemented as an array as described above.

You have been provided a test driver file which provides some rudimentary testing. You'll need to comment out parts of it to start with until you've completed the required implementations. You should modify the main() function as you see fit to accomplish this task. I will test your submission with my own main() functions and a more robust data set, so be sure to cover all edge cases when conducting your testing.

Download these files to get started: lab11_files.zip

Note: You will have to choose whether you are going to implement the zero-based indexing or one-based indexing for your heap and set the BASE variable accordingly at the top of the PriQueue.h file.

Part 1 (50 points)

Implement the enqueue method of the PriorityQueue class (found in PriQueue.h), such that an element can be added to the Priority Queue while retaining the properties of a Heap. In order to do this, you'll also need to implement the following private helper methods:

• swap
• getRightChild
• getLeftChild

Note: getRightChild and getLeftChild are not required for the enque function per se, but they are required for the printTree function in order to see if your enqueue worked correctly.

For this lab, make the following assumptions:

• No Element in the Priority Queue will have the same priority
• We will never attempt to enqueue more than CAPACITY number of Elements (as defined in PriQueue.h)

Part 2 (30 points)

Complete the dequeue method of the PriorityQueue class. In order to do this, you'll also need to implement the following private helper methods:

• isChildHigher
• findHighestChild

Part 3 (20 points)

Complete the getFront, size, and isEmpty member functions of the PriorityQueue class as described at the top of PriQueue.h

Sample Output

Here's what your output should look like using an unmodified version of PQDriver.cpp:

Deliverables

Due: 2359, Thursday 29 Nov 2018

Submit your modified source code via the the submisison website: submit.cs.usna.edu.

Specifically:

• PriQueue.h

Do NOT submit any executable, .o, or provided/unaltered files (i.e. PQDriver.cpp)!

~/bin/submit -c=SI221 -p=Lab11 PriQueue.h