On python please class priorityQueue: def __init__(self): self.heap=[] self.size
ID: 3856462 • Letter: O
Question
On python please
class priorityQueue:
def __init__(self):
self.heap=[]
self.size = 0
def __len__(self):
return self.size
def parent(self,index):
if index>self.size or index<=1:
return None
else:
return self.heap[index // 2 -1]
def leftChild(self,index):
if index<1 or 2*index>self.size:
return None
else:
return self.heap[2*index - 1]
def rightChild(self,index):
if index<1 or 2*index+1>self.size:
return None
else:
return self.heap[2*index]
def swap(self, index1, index2):
self.heap[index1-1], self.heap[index2-1] = self.heap[index2-1], self.heap[index1-1]
def insert(self,x):
self.size += 1
self.heap.append(x)
index = self.size
while index>1 and self.parent(index)<self.heap[index-1]:
parentIndex = index // 2
self.swap(index, parentIndex)
index = parentIndex
def deleteMax(self):
# The function returns the largest integer in self.heap if exists,
# otherwise None
# After the maximum is deleted from self.heap,
# it must satisfy the heap property.
if self.size<=0:
return None
elif self.size==1:
self.size=0
return self.heap[0]
#--- code the remaining -----
#--- Read the lecture nodes II-5 carefully ----
def heapSort(intList):
#intList is a list of integers.
#Sort and return it.
#You CANNOT USE the list.sort() method.
out = []
h = priorityQueue()
#Insert all in intList to h
#Do deleteMax n times to add to out, then return it
#---- code -----
#---- until here ---
return out
#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[0:h.size])
x = h.deleteMax()
print(h.heap[0:h.size])
x = h.deleteMax()
print(h.heap[0:h.size])
x = h.deleteMax()
print(h.heap[0:h.size])
### This should print out
#[14, 9, 11, 5, 2, 10, 6]
#[11, 9, 10, 5, 2, 6]
#[10, 9, 6, 5, 2]
#[9, 5, 6, 2]
print(heapSort([13, 4, 15, 9, 17, 6, 1, 8, 16, 3, 7]))
### The output should be
# [1, 4, 3, 6, 7, 8, 9, 13, 15, 16, 17]
Explanation / Answer
class priorityQueue:
def __init__(self):
self.heap=[]
self.size = 0
def __len__(self):
return self.size
def parent(self,index):
if index>self.size or index<=1:
return None
else:
return self.heap[index // 2 -1]
def leftChild(self,index):
if index<1 or 2*index>self.size:
return None
else:
return self.heap[2*index - 1]
def rightChild(self,index):
if index<1 or 2*index+1>self.size:
return None
else:
return self.heap[2*index]
def swap(self, index1, index2):
self.heap[index1-1], self.heap[index2-1] = self.heap[index2-1], self.heap[index1-1]
def insert(self,x):
self.size += 1
self.heap.append(x)
index = self.size
while index>1 and self.parent(index)<self.heap[index-1]:
parentIndex = index // 2
self.swap(index, parentIndex)
index = parentIndex
def deleteMax(self):
# The function returns the largest integer in self.heap if exists,
# otherwise None
# After the maximum is deleted from self.heap,
# it must satisfy the heap property.
if self.size<=0:
return None
elif self.size==1:
self.size=0
return self.heap[0]
#--- code the remaining -----
#--- Read the lecture nodes II-5 carefully ----
def heapSort(intList):
#intList is a list of integers.
#Sort and return it.
#You CANNOT USE the list.sort() method.
out = []
h = priorityQueue()
#Insert all in intList to h
#Do deleteMax n times to add to out, then return it
#---- code -----
#---- until here ---
return out
#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[0:h.size])
x = h.deleteMax()
print(h.heap[0:h.size])
x = h.deleteMax()
print(h.heap[0:h.size])
x = h.deleteMax()
print(h.heap[0:h.size])
### This should print out
#[14, 9, 11, 5, 2, 10, 6]
#[11, 9, 10, 5, 2, 6]
#[10, 9, 6, 5, 2]
#[9, 5, 6, 2]
print(heapSort([13, 4, 15, 9, 17, 6, 1, 8, 16, 3, 7]))
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.