CODEWITHSUNDEEP
pythondata-structuresheap
TLado
TLado

Reputation: 48

Heap data structure in python

I have implemented min-heap in python, but after some tests I realized that sometimes approximately after every 10th insert it puts it in the wrong position(the parent is larger than child). The code:

class minHeap():
    def __init__(self):
        self.heap = [] # main array
        
    def get_parent(self, i):
        return i//2

    def bubble_up(self):
        i = len(self.heap)-1
        p = self.get_parent(i)
        while self.heap[p] > self.heap[i]:
            self.heap[i], self.heap[p] = self.heap[p], self.heap[i] # swapping parent and child
            i = p
            p = self.get_parent(i)

    def insert(self, k):
        self.heap.append(k)
        self.bubble_up()

My last 2 hours has been spent searching for the bug, so I would really appreciate if someone would help me.

Upvotes: 1

Views: 453

Answers (1)

Yash Shah
Yash Shah

Reputation: 1654

Solution

You should change this function from

def get_parent(self, i):
    return i//2

To:

def get_parent(self, i):
    return (i-1)//2

Explanation

You are using a list in python to initialize which is 0-indexed.

self.heap = [] # main array

Now, Let's say you have added 2 elements 1 and 5.

self.heap = [1,5]

Now. If you add one more element which is 3.

self.heap = [1,5,3]

Now, index of 3 is 2. It's parent should be 1(index = 0). But i//2 will give you 5(index = 1) as 2//2 = 1.

So, you should use (i-1)//2 which will give you 0.

(2-1)//2 = 0

Hoping that you have understood my solution🔑.

Upvotes: 2

Related Questions