# In this PYTHON exercise, code the four functions # parent, leftChild, rightChi

Question

# In this PYTHON exercise, code the four functions
# parent, leftChild, rightChild, and insert
#
# Submission
# - Don't change the function names
# - File name = EX7_3.py and upload it to Vocareum
#   

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, it reutnrs None
#---- code ------
#print(index, " is index in parent")

def leftChild(self,index):
# It returns the value of the left child
#---- code -----

def rightChild(self,index):
# It returns the value of the left child
#---- code -----

# You can use this utility function in insert
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):
# x is an integer, and the funciton just inserts
# into self.heap, satisfying the heap property
# It returns nothing just changing the heap
# --- code -----

#Test code
h = priorityQueue()
h.insert(10)
print(h.heap)
h.insert(5)
print(h.heap)
h.insert(14)
print(h.heap)
h.insert(9)
print(h.heap)
h.insert(2)
print(h.heap)
h.insert(11)
print(h.heap)
h.insert(6)
print(h.heap)
### This should print out
#[10]
#[10, 5]
#[14, 5, 10]
#[14, 9, 10, 5]
#[14, 9, 10, 5, 2]
#[14, 9, 11, 5, 2, 10]
#[14, 9, 11, 5, 2, 10, 6]
#
### Draw the heap in the last line on a sheet of paper
# to see the heap property true
# Each insertion is done in O(log n) time!

Explanation / Answer

Solution: See the updated code below:

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

#   In this PYTHON exercise, code the four functions
#       parent, leftChild, rightChild, and insert
#
#           Submission
#   - Don't change the function names
#   - File name = EX7_3.py and upload it to Vocareum
#
import math

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, it reutnrs None
        if index > 1:
            return int(math.ceil((index-1)/2))
      
        #print(index, " is index in parent")

    def leftChild(self,index):
        # It returns the value of the left child
        return self.heap[2*index]

    def rightChild(self,index):
        # It returns the value of the left child
        return self.heap[2*index+1]

    # You can use this utility function in insert
    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):
        # x is an integer, and the funciton just inserts
        #   into self.heap, satisfying the heap property
        # It returns nothing just changing the heap
        self.heap.append(x)
        self.size=self.size+1      
        index=self.size
        while index != 1 and x > self.heap[self.parent(index)]:
            self.swap(index,self.parent(index))
            index=self.parent(index)

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

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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