Question

Implement the class MaxHeapPriorityQueue as a heap with the following operations using python:

- MaxHeapPriorityQueue() creates a new heap that is empty. It needs no parameters and returns nothing.

- parent(index) returns the value of the parent of heap[index]. index is between 1 and the size of the heap. If index<=1 or index>size of the heap, it returns None

- leftChild(index) returns the value of the left child of heap[index], returns None if there is no value

- rightChild(index) returns the value of the right child of heap[index], return None if there is no value

- len(heap_object) returns the number of items in the heap. It needs no parameters and returns an integer.

- insert(item) adds the item into the heap satisfying the max heap property. It modifies self.heap and returns nothing. You can use the swap function provided in the starter code

- deleteMax() removes the max element of the heap (the root node). It needs no parameters and returns the value removed from the heap. The heap satisfies the max heap property after deletion. (If you think on a recursive approach, you are allowed to create another method to help this method restore the max heap property)

Provided methods:

def swap(self, index1, index2):
self.heap[index1-1], self.heap[index2-1] = self.heap[index2-1], self.heap[index1-1]

def deleteMax(self):

if self.size<=0:
return None
elif self.size==1:
self.size=0
return self.heap[0]

Answer 1

# class that represents a minHeap
class MaxHeapPriorityQueue:

        # algorithm:
        # we will store the nodes of the heap in a list
        # starting from 1st index.
        # a node at index i, will have its children at index 2*i + 1 
        # and 2*i + 2 indices.
        
        # constructor
        def __init__(self):
                self.heap = [0]
                self.currentSize = 0

        def parent(self, index):
                if index <= 1 or index > self.currentSize:
                        return None
                return self.heap[index // 2]

        def leftChild(self, index):
                l = index * 2
                if l <= 1 or l >= self.currentSize:
                        return None
                return self.heap[l]


        def rightChild(self, index):
                r = 1 + index * 2
                if r <= 1 or r >= self.currentSize:
                        return None
                return self.heap[r]

        def __len__(self):
                return self.currentSize

        def swap(self, index1, index2):
                self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

        def deleteMax(self):
                if self.currentSize<=0:
                        return None
                else:
                        # remove the root node.
                        retval = self.heap[1]
                        self.heap[1] = self.heap[self.currentSize]
                        self.currentSize = self.currentSize - 1
                        self.heap.pop()
                        self.percDown(1)
                        return retval
        
        # this method bubblesUp the heap starting from a index till root
        def percUp(self, i):
                while self.parent(i) is not None:
                        if self.heap[i] > self.heap[i // 2]:
                                self.swap(i//2, i)
                        else:
                                break
                        i = i // 2

        # add a new entry to the heap
        def insert(self, k):
                self.heap.append(k)
                self.currentSize = self.currentSize + 1
                self.percUp(self.currentSize)
        
        # this method bubblesDown the heap starting from a index till leaf
        def percDown(self, i):
                while (i * 2) <= self.currentSize:
                        mc = self.maxChildIdx(i)
                        if self.heap[i] < self.heap[mc]:
                                self.swap(mc, i)
                        else:
                                break
                        i = mc

        # this method finds the index of the child having more values.
        def maxChildIdx(self, i):
                if self.rightChild(i) is None:
                        return i * 2
                else:
                        if self.leftChild(i) > self.rightChild(i):
                                return i * 2
                        else:
                                return i * 2 + 1

        # return number of entries in heap
        def len(self):
                return self.currentSize


hp = MaxHeapPriorityQueue()

for x in [10,7,12,6,3,8,17]:
        hp.insert(x)


while len(hp) != 0:
        print(hp.deleteMax())

Fles saved main.py 73 74 75 76 https://WhitesmokeDualAc else: D main.py break Python 3.6.1 (default, [GCC 4.8.2] on linux 17 12 10 =mc # this method finds the index of the child having more values def maxChildIdx(self, i): 78 79 80 81 82 83 84 85 86 87 if self.rightChild(i) is None: return i* 2 else: if self.leftChild(i) > self.rightChild(i): return i* 2 else: return i2 1 # return number of entries in heap def len(self): 89 90 91 92 hpMaxHeapPriorityQueue() 93 94 for x in [10,7,12,6,3,8,17]: 95 96 97 98 while len(hp)!= 0: return self.currentSize hp.insert(x) print(hp.deleteMax())

Please upvote, as i have given the exact answer as asked in question. Still in case of any concerns in code, let me know in comments. Thanks!