Lab 7 Minimum Priority Queue

Lab 7
Minimum Priority Queue
Objective
Implement Minimum Priority Queue ADT. Complete the class definition of MinPQ class.
You can copy some of your code, such as enlarge, and shrink functions, from previous
labs and projects. Do not forget to implement shift_up and shift_down operations.
Review the lecture slides on Min Heap. You are free to create helper functions.
Implementation
Create a file, min_pq.py, and write the following class with methods and top-level
functions.
Use only < operator to compare two items: do not use <=, , =.
It will be important when you use the MinPQ in project 3 to do
HuffmanCoding.
Implement MinPQ class with following attributes and methods:
class MinPQ:
"""Minimum Priority Queue
Attributes:
capacity (int): The capacity of the queue.
The default capacity is 2, but will be increased automatically.
num_items (int): The number of items in the queue.
This also points to the position where a new item will be added.
arr (list): an array which contains the items in the queue.
"""
def __init__(self, arr=None):
"""initializes an object of MinPQ
If the arr is None (default), it initializes its capacity as 2,
and creates an array: [None] * self.capacity. The num_items shall be initialized as 0.
1
CPE202 Spring 2020
Otherwise, the arr shall be transformed into a min heap with heapify() method.
In this case, the capacity and num_items are set to the size of the arr, which is len(arr):
self.arr = arr
self.capacity = len(arr)
self.num_items = len(arr) - 1
self.heapify()
Args:
arr (list): the default value is None.
"""
def heapify(self):
"""convert the array, self.arr, into a min heap.
"""
def insert(self, item):
"""inserts an item to the queue.
Before inserting an item it checks if the array is full,
if so, it enlarges the array by doubling the capacity.
Args:
item (any): an item to be inserted to the queue. It is of any data type.
"""
def del_min(self)-any:
"""deletes the minimum item in the queue.
After the deletion and just before returning the removed item,
it checks if the array needs to be shrinked.
If so, it downsizes the array by halving the capacity:
if self.capacity 2 and self.num_items and self.capacity = self.num_items * 4:
self.shrink()
YOU ARE NOT ALLOWED TO USE PYTHON LIST’s BUILT-IN FUNCTIONS
such as append, pop, insert, extend, and + operator with lists.
Returns:
any : it returns the minimum item, which has just been deleted
Raises:
IndexError : Raises IndexError when the queue is empty
"""
def min(self)-any:
"""returns the minimum item in the queue without deleting the item
Returns:
any : it returns the minimum item
Raises:
IndexError : Raises IndexError when the queue is empty
"""
2
CPE202 Spring 2020
def is_empty(self)-bool:
"""checks if the queue is empty
Returns:
bool : True if empty, False otherwise.
"""
def size(self)-int:
"""returns the number of items in the queue
Returns:
int : it returns the number of items, self.num_items, in the queue
"""
def shift_up(self, idx):
"""shifts up an item in the queue using tail recursion.
Use only < operator to compare two items: do not use <=, , =.
Args:
idx (int): the index of the item to be shifted up in the array.
"""
def shift_down(self, idx):
"""shifts down an item in the queue using tail recursion.
Use only < operator to compare two items: do not use <=, , =.
YOU NEED TO DETERMINE WHERE THE END OF THE HEAP IS.
YOU CAN USE self.num_items FOR DOING SO.
Args:
idx (int): the index of the item to be shifted down in the array.
"""
def enlarge(self):
"""enlarges the array.
"""
def shrink(self):
"""shrinks the array.
"""
Example Use Cases
Use case #1
pq = MinPQ()
pq.insert(5)
pq.insert(3)
3
CPE202 Spring 2020
pq.capacity == 2 #It shall be True
pq.insert(6)
pq.size() # It shall return 3
pq.capacity == 4 #It shall be True
pq.find_min() # It shall return 3
pq.del_min() # It shall return 3
pq.del_min() # It shall return 5
pq.del_min() # It shall return 6
pq.size() # It shall return 0
pq.is_empty() # It shall return True
pq.capacity == 2 #It shall be True
Use case #2
pq = MinPQ([5, 4, 3, 2, 1])
pq.size() # It shall return 5
pq.capacity == 5 #It shall be True
pq.num_items == pq.capacity # It shall be True
pq.arr == [1, 2, 3, 5, 4] # It shall be True
pq.find_min() # It shall return 1
pq.del_min() # It shall return 1
pq.del_min() # It shall return 2
pq.del_min() # It shall return 3
pq.del_min() # It shall return 4
pq.del_min() # It shall return 5
pq.capacity == 2 #It shall be True
pq.size() # It shall return 0
pq.is_empty() # It shall return True
Tests
Create a file, min_pq_tests.py, and write tests for your program. You will be using your min
priority queue to do Huffman coding. Items will be enqueued and dequeued repeatedly. The
goal of your tests should be to make sure that your min priority queue works without a glitch in
all possible use cases.
Submission
You must submit the following files to the Gradzilla and then to Canvas:
● min_pq.py
4
CPE202 Spring 2020
○ The functions specified and any helper functions necessary.
● min_pq_tests.py
○ Include test cases you used in developing your programs.
5