CSc 7003, Programming for Data Science (Summer 2019)

Program 12 - Priority Queue Simple Implementations using sorted and unsorted lists

Array/List Implementation

Complete the following definitions of Sorted and Unsorted list implementations of Priority Queues:

class PQSortedArray:

    def __init__(self):
        self._data = []
        self._size = 0

    def __str__(self):
        return str(self._data)

    def is_empty(self):
        return self._size == 0

    def insert(self,num):

    def delete_min(self):

class PQUnsortedArray:

    def __init__(self):
        self._data = []
        self._size = 0

    def __str__(self):
        return str(self._data)

    def is_empty(self):
        return self._size == 0

    def insert(self,num):

    def delete_min(self):

## The following is the main program to test the above two implementations
import random

def test_PQ(twenty,q):
    print("list = ",twenty)
    for x in twenty:
        q.insert(x)
    sorted_twenty = []
    while not q.is_empty():
        sorted_twenty.append(q.delete_min())
    print("sorted list = ",sorted_twenty)

def main():
    print("Testing Sorted Array Implementation of Priority Queue")
    q1 = PQSortedArray()
    twenty = list(range(20))
    random.shuffle(twenty)
    test_PQ(twenty,q1)
    print()
    print("Testing Unsorted Array Implementation of Priority Queue")
    q2 = PQUnsortedArray()
    twenty = list(range(20))
    random.shuffle(twenty)
    test_PQ(twenty,q2)

main()

A sample run of the main program is given below:

macbook-pro:LL raj$ python3 PQ.py 
Testing Sorted Array Implementation of Priority Queue
list =  [1, 3, 15, 7, 14, 4, 5, 19, 8, 13, 11, 6, 0, 16, 2, 10, 18, 9, 17, 12]
sorted list =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Testing Unsorted Array Implementation of Priority Queue
list =  [8, 12, 14, 10, 18, 15, 16, 17, 1, 9, 19, 5, 13, 4, 0, 6, 7, 3, 2, 11]
sorted list =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]