-
Notifications
You must be signed in to change notification settings - Fork 4
/
pq.py
160 lines (131 loc) · 4.61 KB
/
pq.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
from Heap.BinaryHeap.maxHeap import MaxHeap
from copy import deepcopy
class PriorityQueue(object):
def __init__(self, pq_capacity=10):
self._pq_capacity_ = pq_capacity
self._pq_size_ = 0
self._pq_heap_ = MaxHeap(pq_capacity)
# Time Complexity : O(log(n))
def insert(self, item, priority):
res = False
if self.is_full():
print("Priority queue is full, please delete older items in order to insert newer ones.")
return res
e = Entry(item, priority)
res = self._pq_heap_.insert(e)
if res:
self._pq_size_ += 1
return res
# Time Complexity : O(log(n))
def delete_item_with_highest_priority(self):
res = False
if self.is_empty():
print("Priority queue is empty")
return res
res = self._pq_heap_.delete_max()
if isinstance(res, bool) and res == False:
pass
else:
self._pq_size_ -= 1
return res
# Time Complexity : O(1)
def get_item_with_highest_priority(self):
if self.is_empty():
print("Priority queue is empty")
return False
return self._pq_heap_.get_max()
def is_full(self):
return self._pq_size_ >= self._pq_capacity_
def is_empty(self):
return self._pq_size_ <= 0
def pq_print(self):
return deepcopy(self._pq_heap_.heap_arr()[0:self.pq_size()])
def pq_size(self):
return self._pq_size_
def pq_capacity(self):
return self._pq_capacity_
class Entry(object):
"""
Represents an entry(combination of item & priority) of priority queue.
"""
def __init__(self, item, priority):
self.item = item
self.priority = priority
def __str__(self):
return "({}:{})".format(self.item, self.priority)
def __repr__(self):
return "({}:{})".format(self.item, self.priority)
def __le__(self, other):
return self.priority <= other.priority
def __lt__(self, other):
return self.priority < other.priority
def __ge__(self, other):
return self.priority >= other.priority
def __gt__(self, other):
return self.priority > other.priority
def __eq__(self, other):
return self.priority == other.priority
def __ne__(self, other):
return self.priority != other.priority
def test():
pq_arr_test = ["5 2", "6 1", "2 7", "4 3", "7 0", "8 5", "9 6"]
pq_capacity = len(pq_arr_test)
pq = PriorityQueue(pq_capacity)
mh_test = MaxHeap(pq_capacity)
for item_priority in pq_arr_test:
item_priority = item_priority.split(" ")
item = int(item_priority[0].strip())
priority = int(item_priority[1].strip())
mh_test.insert(priority)
pq.insert(item, priority)
print(pq.pq_arr())
print(mh_test.heap_arr())
print("Element with highest priority: ", pq.get_item_with_highest_priority())
if __name__ == '__main__':
pq_capacity = input("Please enter the size/capacity of priority queue - ")
pq = PriorityQueue(pq_capacity)
menu = """
Menu:
1. Insert.
2. Print priority queue.
3. Get item with maximum priority.
4. Delete item with maximum priority.
5. Get the size and capacity of priority queue.
6. Stop.
"""
print(menu)
while True:
try:
choice = input("Please enter your choice - ")
except:
print("Incorrect choice, please select from menu.")
continue
try:
if choice == 1:
item_priority = input("Enter item & priority separated by a white-space - ")
item_priority = item_priority.split(" ")
item = item_priority[0].strip()
priority = item_priority[1].strip()
res = pq.insert(item, priority)
print(res)
continue
if choice == 2:
print(pq.pq_print())
continue
if choice == 3:
res = pq.get_item_with_highest_priority()
print(res)
continue
if choice == 4:
res = pq.delete_item_with_highest_priority()
print(res)
continue
if choice == 5:
print("Size : {} | Capacity: {}".format(pq.pq_size(), pq.pq_capacity()))
continue
if choice == 6:
break
except Exception as ex:
print("Error occurred while performing last operation(choice: {}):".format(choice))
print(ex.message, ex.args)
print(menu)