Python Heaps Complete the implement basic procedures of a mi

[Python] [Heaps] Complete the implement basic procedures of a min-heap data structure from max-heap, and use it to construct a min-priority queue ADT.

Provide max-heap implement

min-heap skeleton

import math class PriorityQueue \"\" \"Abstract base class for a priority queue. \"\" class Item: \"\" \"Lightweight composite to store priority queue items.\"\" slots-= -key\', \'-value. def-init--(self, k, v): self-key k self. valuev def-It-(self, other): return self._keyother._key def gt-(self, return self._key> other._key other): def-eq-(self, other): return self-key == other-key def e(self, other): return self-key other._key is_empty (self): \"\"\"Return True if the priority queue is empty.\"\"\" return len(self) def parent(i): \"\" \"Return the index of the parent of node i in a binary heap.\"\"\" return i//2 def left(i): \"\" \"Return the index of the left child of node i in a binary heap.\"\"\" return 2*1 def right(i): \"\" \"Return the index of the right child of node i in a binary heap. \"\"\" return 2*i + 1 def max_heapify (A, i, heap_size): 1 = left (i) r- right(i) if I A[i]: else: if r A[largest]; if largest != 1: largest = 1 largest i largest- r A[1], A[largest] = A[largest], A[i] max_heapify(A, largest, heap size) def build_max_heap (A) \"\" \"Build max-heap from an unordered array A. \"\"\" heap-size = len(A) -1 for i in range (math.floor (len (A)/2), 0, 1): max_heapify(A, i, heap_size) class MaxHeapPriorityQueue (PriorityQueue): \"\" \"A priority queue implemented with a max-heap data structure.\"\"\" def-init-(self): \"\" \"Create a new empty heap based priority queue.\"\"\" self. heap_size self-heap- [self.-Item(-math. inf, None)] #A/a] is unused. def en_(self): \"\" \"Return the number of items in the priority queue. \"\"\" return self._heap_size def max(self): \"\"\"Return but do not remove (k, v) tuple with maximum key (highest priority) Ref: HEAP-MAXIMUM maxitemself._heap[self._find_max()] return (maxitem._key, maxitem._value) def delmax (self): \"\"Remove and return (k, v) tuple with maximum key (highest priority). Ref: HEAP-EXTRACT-MAX assert self-heap-size >= 1, \"error: heap underflow.\" maxitem = self, heap[self, find max()] self-heap[1] = self-heap[self.-heap-size] self._heap_sizeself._heap_size 1 max_heapify(self._heap, 1, self._heap_size) return (maxitem._key, maxitem._value) def add(self, k, v): \"\"\"Insert an item with value \'key into the queue. Ref: MAX-HEAP-INSERT newitem- self-Item(k, v) self._heap_sizeself._heap_size 1 self._heap.append (self._Item(-math.inf, None)) self._heap_increase_key (self._heap, self._heap_size, newitem) def _find_max(self): \"\" \"Return the index of the maximum item. \"\" \" return 1 def _heap_increase_key (self, A, i, key): \"\" \"Implementation of HEAP-INCREASE-KEY procedure.\"\"\" assert key >= A[1], \"error: new key is smaller than current key.\" A[1] = key while i 1 and A[parent (i)] ALi]: A[i], A[parent(i)] -A[parent(i)], A[i] i = parent (i)

Solution

Implementation MinPriorityQueue ADT below.

This is written keeping in the view of given MaxPriorityQueue ADT

see below

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

import math
class PriorityQueue:
class _Item:
_slots_=\'_key\',\'_value\'

def _init_(self,k,v):
self._key=k
self._value=v

def _lt_(self,other):
return self._key<other._key
def _gt_(self,other):
return self._key>other._key
def _eq_(self,other):
return self._key==other._key
def _le_(self,other):
return self._key<=other._key
def _ge_(self,other):
return self._key>=other._key
def is_empty(self):
return len(self)==0
def parent(i):
return i//2
def left(i):
return 2*i
def right(i):
return 2*i+1
def min_heapify(A,i,heap_size):
l=left(i)
r=right(i)
if l<heap_size and A[l]<A[i]:
largest=l
else:
largest=i;
if r<heapsize and A[r]<A[largest]:
largest=r
if largest!=i:
A[i],A[largest]=A[largest],A[i]
min_heapify(A,i,heap_size)
def build_min_heap(A):
heap_size=len(A)-1
for i in range(math.floor(len(A)/2),0,-1):
min_hepify(A,i,heap_size)

class MinHeapPriorityQueue(PriorityQueue):
\"\"\" A min prioitiy queuw implemented with a min heap data structure\"\"\"

\"\"\" create a new empty heap based priotity queue \"\"\"
def _init_(self):
self._heap_size=0
self._heap=[self._Item(-math.inf,None)]

\"\"\" return number of items in priorityQueue \"\"\"
def _len_(self):
return self._heap_size
\"\"\" return (key,value) with minimumkey \"\"\"
def min(self):
minitem=self._heap[self._find_min()]
return (minitem._key,minitem._value)

\"\"\" remove and return (key,value) with minimumkey \"\"\"
def delmin(self):
assert self._heap_size <=1, \"error:heap underflow\"
minitem=self._heap[self._find_min()]
self._heap[1]=self._heap[self._heap_size]
self._heap_size=self._heap_size-1
min_heapify(self._heap,1,self._heap_size)
return (minitem._key,minitem._value)

\"\"\" Inserts an item with \'key\' into minpriority queue \"\"\"
def add(self,k,v):
newitem=self._Item(k,v)
self._heap_size=self._heap_size+1
self._heap_append(self._Item(math.inf,None))
self._heap_decrease_key(self._heap_,self._heap_size,newitem)
\"\"\" return the index of minimum item. \"\"\"
def find_min(self):
return 1
\"\"\" implementation of decrease_key procedure \"\"\"
def _heap_decrease_key(self,A,i,key):
assert key <=A[i], \"error: new key is larger that current.\"
A[i]=key;
while i>1 and A[parent] > A[i]:
A[i],A[parent(i)]=A[parent(i)],A[i]
i=parent(i)