1
\$\begingroup\$

I have to implement a priority queue using a heap without any library / package for priority queue or heap. I made a BinHeap class which is a min heap, and I made a priority queue class with enqueque, dequeque methods that uses it. The priority queue class works fine but i'm not sure if the code its correct. Can you please help me? Thanks

#class Min Heap
class BinHeap:
    #constructor 
    def __init__(self):
        self.heapList = [0]     #heap can be represented as a list, initialize list [] = 0
        self.currentSize = 0    #initialize size = 0

    #swap last appended element with the parent or right child if needed, until (min) heap structure is mantained
    def percUp(self,currentSize):
        while currentSize // 2 > 0:
          if self.heapList[currentSize] < self.heapList[currentSize // 2]:                                                                      #if last appended elem < parent
             self.heapList[currentSize // 2], self.heapList[currentSize] = self.heapList[currentSize], self.heapList[currentSize // 2]          #swap them

          if self.heapList[currentSize] < self.heapList[currentSize-1]:                                                                         #if right child < left child
              self.heapList[currentSize], self.heapList[currentSize-1] = self.heapList[currentSize-1], self.heapList[currentSize]               #swap them

          currentSize = currentSize // 2                                                                                                        #continue to check until the root

    #insert node in the right place, if needed, swap with parent
    def insert(self,k):
      self.heapList.append(k)
      self.currentSize = self.currentSize + 1
      self.percUp(self.currentSize)

    #delete greater node
    def delMax(self):
        return self.heapList.pop()


#priority queque class
class priority_queque():
    def __init__(self):
        self.heap = BinHeap()

    def enqueque(self, val):
        self.heap.insert(val)

    def dequeque(self):
        self.heap.delMax()

    #print all pqueque
    def print(self):
        print(self.heap.heapList)


ci = priority_queque()
ci.enqueque(9)
ci.enqueque(5)
ci.enqueque(6)
ci.enqueque(2)
ci.enqueque(3)
ci.print()
ci.dequeque()
ci.print()

#output
#[0, 2, 3, 6, 5, 9]
#[0, 2, 3, 6, 5]
\$\endgroup\$
  • 1
    \$\begingroup\$ delMax seems to be wrong. There is no guarantee that the max element is the last, as you can see from your second output. \$\endgroup\$ – vnp Apr 3 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.