Priority Queue In Python please! Thank you so much! ### EX7_3 # Implement the cl
ID: 3854495 • Letter: P
Question
Priority Queue In Python please! Thank you so much!
### EX7_3
# Implement the class priorityQueue as discussed in class
# In this exercise, code the four functions
# parent, leftChild, rightChild, and insert
#
# Submission
# - Don't change the function names
# - File name EX7_3.py
class priorityQueue:
#The ADT PriorityQueue is implemented as a heap.
#Need insert and deletemax as the supported functions
def __init__(self):
self.heap=[]
# As discussed in class,
# heap[1:n] is the body of the heap.
# It's an ARRAY of integers
# whose index range is 1:n, NOT 0:n-1
self.size = 0
def __len__(self):
return self.size
def parent(index):
# index is between 1 and self.size
# It returns the value of the parent of heap[index]
# If index<=1, it reutnrs None
#---- code ------
def leftChild(index):
# It returns the value of the left child
#---- code -----
def rightChild(index):
# It returns the value of the left child
#---- code -----
def insert(x):
# x is an integer, and the funciton just inserts
# into self.heap, satisfying the heap property
# It returns nothing just chaning the heap
# --- code -----
#Test code
h = priorityQueue()
h.insert(10)
h.insert(5)
h.insert(14)
h.insert(9)
h.insert(2)
h.insert(11)
h.insert(6)
print(h.heap)
Explanation / Answer
// Use the below code.
class priorityQueue:
def __init__(self):
self.heap = [0]
self.size = 0
def parent(self,i):
if i>0 and i<self.size:
return self.heap[i]
def leftChild(self,i):
if i>0 and i*2<=self.size:
return self.heap[i*2]
def rightChile(self,i):
if i>0 and i*2+1<=self.size:
return self.heap[i*2+1]
def insert(self,k):
self.heap.append(k)
self.size = self.size + 1
i=self.size
while i // 2 > 0:
if self.heap[i] > self.heap[i // 2]:
tmp = self.heap[i // 2]
self.heap[i // 2] = self.heap[i]
self.heap[i] = tmp
i = i // 2
def maxChild(self,i):
if i * 2 + 1 > self.size:
return i * 2
else:
if self.heap[i*2] > self.heap[i*2+1]:
return i * 2
else:
return i * 2 + 1
def delMax(self):
retval = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size = self.size - 1
self.heap.pop()
i=1
while (i * 2) <= self.size:
mc = self.maxChild(i)
if self.heap[i] < self.heap[mc]:
tmp = self.heap[i]
self.heap[i] = self.heap[mc]
self.heap[mc] = tmp
i = mc
return retval
h = priorityQueue()
h.insert(10)
h.insert(5)
h.insert(14)
h.insert(9)
h.insert(2)
h.insert(11)
h.insert(6)
print(h.heap)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.