Heap data structure in python

Question

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.

If you really ant some help then please edit your code so it is a minimal reproducible example - include imports and some minimal data - so that anyone can paste the code into a file and without adding anything run your code to see the same problem. — DisappointedByUnaccountableMod
– DisappointedByUnaccountableMod, Commented Jun 5, 2021 at 9:18
Your code still isn’t a minimal reproducible example - you need to include some code to create an instance of the class/call your methods, with some data, and show how you know the allocation is ‘wrong’. Try it yourself as if you were reading this question - what do you need to add to the code in the question to see the same result as the person asking the question? Now add this additional code so anyone can run the code in your question without adding anything — DisappointedByUnaccountableMod
– DisappointedByUnaccountableMod, Commented Jun 5, 2021 at 10:18

Yash Shah · Accepted Answer · 2021-06-05 12:15:19Z

2

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🔑.

answered Jun 5, 2021 at 12:15

Yash Shah

1,6541 gold badge8 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Yash Shah Over a year ago

@TLado Could you accept my answer if you found that useful?

TLado Over a year ago

Thanks, you have helped me a lot. One problem I had to solve after was that sometimes I got -1 as the index of the parent, which would screw up the entire code. The problem there was that the root node doesn't have a parent, that is why I had to make a base case. After that, the heap worked perfectly.

Collectives™ on Stack Overflow

Heap data structure in python

1 Answer 1

Solution

Explanation

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Solution

Explanation

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related