[Python] [Heaps] Complete the implement basic procedures of a min-heap data stru

Question

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

Explanation / Answer

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)

  

  
  
  

  

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.