You have been provided a Python file, heap.py, which constructs a min-heap structure with a list. Using that code as a guide: Develop a LinkedHeap data structure in a file named LinkedHeap with the extension appropriate to your chosen langauge using a linked tree structure (Nodes and Pointers).

you MUST use and not alter the BinaryNode provided in the lab.

The key is that the publicly visible interface is the same and that you must make it so that the element of the node is immutable, meaning that moving an element in the heap MUST be done by moving the entire node and changing all pointers.

The heap must support the following interface: - insert(key, value) This method/subroutine inserts the (key, value) pair into the appropriate position within the min heap.

- delete() This method/subroutine deletes and returns a (key, value) pair with the minimum key value within the heap.

- peek() This method/subroutine returns a (key, value) pair with the minimum key value within the heap without altering the contents of the heap.

- You may add any additional private helper methods that you see fit.

All operations must 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 PriorityQueue data structure in a file named PriorityQueue that is backed by a linked heap.

Implement the normal methods that accompany a priority queue structure:

- add(key, value) This method/subroutine adds the (key, value) pair into the appropriate position within the min heap.

- remove() This method/subroutine removes and returns a (key, value) pair with the minimum key value within the heap.

- min() This method/subroutine returns a (key, value) pair with the minimum key within the heap but leaves the heap unaltered.

- is_empty() This method/subroutine returns True (or the language-specific equivalent) if the heap contains no key/value pairs, False (or the language-specific equivalent) otherwise.

- len(pq) (or the langauge-specific equivalent) This method/subroutine/function call returns the number of (key, value) pairs stored in the heap using the methodology appropriate to the language in which this structure is implemented.

Perform the following operations to showcase your working priority queue: - Enqueue the following items: 11, 7, 8, 6, 5, 9, 4 - Dequeue 3 items by priority, they should be 4, 5, & 6.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

heap.py

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], 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

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]

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)

The attached image is heap.py

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[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]