Building a Python implementation of min heap

Question

What is wrong with the below code to buld a min heap? The bubble_up method doesn't work it gets an index out of range error.

 def __init__(self):
    self.heap = []
    self.heap_size = 0

 def bubble_up(self, i):
    print(self.heap)
    while i // 2 > 0:
        if self.heap[i] < self.heap[i // 2]:
            tmp = self.heap[i // 2 - 1]
            self.heap[i] = self.heap[i // 2]
            self.heap[i // 2] = tmp
        print(self.heap)
        i = i // 2


def insert(self, data):
    self.heap.append(data)
    self.heap_size = self.heap_size + 1
    self.bubble_up(self.heap_size)

if __name__ == "__main__":
    min_heap = MinHeap()
    min_heap.insert(5)
    min_heap.insert(4)
    min_heap.insert(3)
    min_heap.insert(2)
    min_heap.insert(6)

Might I inquire as to what's wrong with the heap that comes with python? — hd1
– hd1, Commented Apr 20, 2015 at 18:44
Index error and I'm attempting to build my own nothing's wrong with pythons... — user4746908
– user4746908, Commented Apr 20, 2015 at 18:45
Your debugging isn't telling you that you have an index error, your program is telling you that. Debugging is the act of ascertaining why a program is doing what it is doing (or at least what is happening while it is running). Writing a program and then asking SO to debug for you will not happen. Writing a program, debugging it and asking for help with the debug output/information has a chance of happening. — KevinDTimm
– KevinDTimm, Commented Apr 20, 2015 at 18:48
It's something wrong with my indexing methods that I'm failing to see. I fail to see what further debugging I could do past looking at my indexing methods which I have already done and still don't user stand the error or why it's happening — user4746908
– user4746908, Commented Apr 20, 2015 at 19:01

IVlad · Accepted Answer · 2015-04-20 19:27:51Z

2

def insert(self, data):
    self.heap.append(data)
    self.heap_size = self.heap_size + 1
    self.bubble_up(self.heap_size)

You append your data, increase heap_size and then call your bubble_up with the new (increased) heap size.

In there, you check:

 if self.heap[i] < self.heap[i // 2]:

where i is the heap size. You cannot do that, if you have 3 elements in your heap, you cannot access heap[3]. It won't exist, your only valid indexes are 0, 1, 2.

Possible fix (untested): call bubble_up with heap_size - 1.

Note that the code in your if doesn't really look right:

tmp = self.heap[i // 2 - 1]        # why -1 here? shouldn't this be heap[i]?
self.heap[i] = self.heap[i // 2]   # shouldn't this be the other way around? why no -1 here?
self.heap[i // 2] = tmp            # why no -1 here? shouldn't this be heap[i]?

Also, you can put i // 2 in this conditional and break out of the loop if the condition is false.

edited Apr 20, 2015 at 19:27

answered Apr 20, 2015 at 19:14

IVlad

43.6k13 gold badges115 silver badges185 bronze badges

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

1 Comment

smac89 Over a year ago

Or do bubble_up before increasing the heap size, and as for swapping use the tuple swapping self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]. This way, no messy temporaries lying around

elllot · Accepted Answer · 2017-12-24 07:50:46Z

The current answer posted accurately portrays why you're getting an outofbounds error, but if you just call bubble_up() with heap_size-1, it will not maintain the heap correctly. Note the following part of your code in bubble_up():

while i // 2 > 0:

Your current while loop statement will not compare immediate childs of the root of the heap to the root. Let's say you insert 3 then 1. When you insert 1, bubble_up() will not correctly swap the inserted 1 with 3 because it won't run the swap routine within your while statement due to i//2 == 0 since i == 1 which is the position 1 was inserted into. I'd switch this block to the following:

while i > 0:
    parent = i // 2
    <put your comparison & swap method here>
    i = parent

Collectives™ on Stack Overflow

Building a Python implementation of min heap

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related