You have been provided a Python file, heap.py, which constructs a heap structure with a list. Using that code as a guide:
Develop a heap data structure using a linked structure (Nodes and Pointers)
The heap must support add and remove from the heap
All operations most abide by the rules that govern a heap (see lecture slides for reference)
Once you have your heap structure created, next you must use it as a backing structure to a priority queue.
Develop a priority queue data structure that is backed by a heap (linked structure NOT A LIST)
Implement the normal methods that accompany a priority queue structure
Enqueue, dequeue, and peek by priority not position
Also length and whether or not the structure is empty (is_empty)
Perform the following operations to showcase your working structure
Enqueue the following items: 4, 7, 5, 11, 8, 6, 9
Dequeue 3 items by priority, they should be 4, 5, & 6.
related heap.py file code is below
class Heap:
def __init__(self):
self.heap = [0]
self.size = 0
def float(self, k):
while k // 2 > 0:
if self.heap[k] < self.heap[k//2]:
self.heap[k], self.heap[k//2] = self.heap[k//2], self.heap[k]
k //= 2
def insert(self, item):
self.heap.append(item)
self.size += 1
self.float(self.size)
def sink(self, k):
while k * 2 <= self.size:
mc = self.minchild(k)
if self.heap[k] > self.heap[mc]:
self.heap[k], self.heap[mc] = self.heap[mc], self.heap[k]
k = mc
def minchild(self, k):
if k * 2 + 1 > self.size:
return k * 2
elif self.heap[k*2] < self.heap[k*2+1]:
return k * 2
else:
return k * 2 + 1
def pop(self):
item = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
self.sink(1)
return item
h = Heap()
for i in (4, 8, 7, 2, 9, 10, 5, 1, 3, 6):
h.insert(i)
print(h.heap)
for i in range(10):
n = h.pop()
print(n)
print(h.heap)