CSCI 4041
Part B - Priority Queue (Programming Problem)
Submission: Submit the following file to “Homework 3B” submission on Gradescope.
• priority queue .py
Problem H3.6: Update Priority (20 points)
Instructions: Many advanced algorithms require the update of a key in a priority queue. For example, Dijkstra’s single source shortest path algorithm described in Section 22.3 of our textbook takes advantage of the MAX-HEAP-INCREASE-KEY described in Section 6.5. The update of a key, however, needs to be efficient to improve the runtime requirements. For this problem, we will extend a heap to create a priority queue. Using our priority queue, we can update an item’s key in O(lg n) time. This is because we also ensure that each time we lookup an index by id, the algorithm runs in O(1) time.
Task: You are given a set of tasks to add to a priority queue. Each task has an id and a priority key. You are provided with the following base code:
• H3 6.py - This file has example code for testing your implementation. (You will not need to modify this file)
• binary heap.py - This file implements a binary heap. (You will not need to modify this file).
• task.py - This file defines the task object. (You will not need to modify this file) Below are a description of the methods:
◦ get id() - Returns the id of a task.
◦ get name() - Returns the name of the task.
◦ get key() - Returns the key of a task, which represents a task’s priority. The higher the key is, the higher the priority.
◦ set key(key) - Changes the priority of a task.
• priority queue .py - This file implements a priority queue, which inherits from a binary heap. (You will need to modify and submit this file.) Extend the heap functionality to create a priority queue. Our priority queue expects that item.get id(), item.get key(), and item .set key() exist, therefore, allowing the use of the Task object.
You will need to implement the following methods:
◦ extract max() - Take the top item off of the heap, and maintain the heap property. The method should run in O(lg n) time.
◦ insert(item) - Add the item to the heap in the correct location based off the item’s priority (e.g. item.get key()). The method should run in O(lg n) time.
◦ lookup by id(id) - Return the index of the item in the heap structure. If the id is not found, -1 is returned. The method should run in O(1) time.
◦ update priority(id, key) - Looks up an item in the heap, set’s the key for that item, and maintains the heap property. The method should run in O(lg n) time.
◦ on index changed(item, index) - This method may be helpful for monitoring when an item’s index changes during the heapify() method of the binary heap.
Testing: on the following page...
Testing: To test the program you can run H3 6.py, which creates a priority queue and calls the methods you implemented. You can test your program with the following command:
python3 H3 _ 6 . py
You should see the following output based on a hypothetical scenario involving CSCI 4041:
Tasks :
------------------------------
Id : Name ( Priority )
------------------------------
1 : Study for midterm . ( 20 )
2 : Email professor . ( 21 )
3 : Start homework . ( 20 )
4 : Study induction for midterm . ( 19 )
5 : Start homework problem H3 .1. ( 18 )
6 : Email professor and TAs . ( 25 )
7 : Start homework problem H3 .6. ( 16 )
8 : Finish homework problem H3 .1. ( 20 )
9 : Post to Piazza for help on H3 .6. ( 15 )
10 : Study Master Theorem for midterm . ( 14 )
11 : Request homework extension . ( 42 )
12 : Take a picture of my cat . ( 6 )
13 : Attend discussion . ( 5 )
14 : Feed the dog . ( 2 )
15 : Live dangerously . ( 1 )