On python please! # In this exercise, code the four functions # parent, leftChil

Question

On python please!

# In this exercise, code the four functions
# parent, leftChild, rightChild, and insert
#
# - Don't change the function names

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

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(self, index):
# index is between 1 and self.size
# It returns the value of the parent of heap[index]
if index <= 1:
return None #Root node has no parent
return self.heap[index // 2 - 1]
#---- code ------

def leftChild(self, index):
# It returns the value of the left child
if index * 2 > self.size: #Check if it is not a leaf node
return None #It is a leaf node
return self.heap[index * 2 - 1]
#---- code -----
def rightChild(self, index):
# It returns the value of the left child
if index * 2 + 1 > self.size: #Check if it is not a leaf node
return None
return self.heap[index * 2]
#---- code -----

def insert(self, x):
# x is an integer, and the funciton just inserts
# into self.heap, satisfying the heap property
# It returns nothing just chaning the heap
self.heap.append(x)
self.size = self.size + 1
i = self.size

# Going up the tree
# Doing min heapify
while i // 2 > 0:
if self.heap[i - 1] < self.heap[i // 2 - 1]:
tmp = self.heap[i // 2 - 1]
self.heap[i // 2 - 1] = self.heap[i - 1]
self.heap[i - 1] = tmp
i = i // 2

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

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

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