class ListNode:
def __init__(self, data, priority):
self.data = data
self.priority = priority
self.next = None
class Heap:
def __init__(self):
self.head = ListNode(0, 0)
self.size = 0
def add(self, data, priority):
self.size += 1
cur = self.head
newNode = ListNode(data, priority)
while (cur.next is not None) and (cur.next.priority < priority):
cur = cur.next
newNode.next = cur.next
cur.next = newNode
def remove(self):
self.size -= 1
item = self.head.next.data
self.head.next = self.head.next.next
return item
def search(self, data):
cur = self.head.next
while cur is not None:
if cur.data == data:
return True
cur = cur.next
return False
class PriorityQueue:
def __init__(self):
self.h = Heap()
def enqueue(self, data):
self.h.add(data, data)
def dequeue(self):
return self.h.remove()
def peek(self):
return self.h.head.next.data
def length(self):
return self.h.size
def isEmpty(self):
return self.h.size == 0
if __name__ == “__main__”:
“””
# Test Heap
h = Heap()
for i in (4, 8, 7, 2, 9, 10, 5, 1, 3, 6):
h.add(i, i)
print(f”3 is Present ? {h.search(3)}”)
print(f”11 is Present ? {h.search(11)}”)
print(f”7 is Present ? {h.search(7)}”)
print(f”31 is Present ? {h.search(31)}”)
for _ in range(10):
print(f”Heap Size : {h.size}”)
n = h.remove()
print(f”Item Popped : {n}”)
“””
pq = PriorityQueue()
for data in [4, 7, 5, 11, 8, 6, 9]:
pq.enqueue(data)
print(f”Heap Size : {pq.length()}”)
for _ in range(3):
print(“dequeue item … “)
print(f”Item to dequeue : {pq.peek()}”)
_ = pq.dequeue()
print(f”Heap Size : {pq.length()}”)