creating a binary heap implementation giving wrong result

Question

I am implementing the binary heap following an online course and I have done the following:

from __future__ import division

class BinaryHeap(object):
    def __init__(self, arr=None):
        self.heap = []

    def insert(self, item):
        self.heap.append(item)
        self.__swim(len(self.heap) - 1)

    def __swim(self, index):
        parent_index = (index - 1) // 2
        while index > 0 and self.heap[parent_index] < self.heap[index]:
            self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
            index = parent_index

Now, I use it as:

s = 'SORTEXAMPLE'
a = BinaryHeap()

for c in s:
    a.insert(c)

Now, after this the heap is ordered as:

['S', 'T', 'X', 'P', 'L', 'R', 'A', 'M', 'O', 'E', 'E']

rather than

['X', 'T', 'S', 'P', 'L', 'R', 'A', 'M', 'O', 'E', 'E']

So, it seems one of the last exchanges did not happen and I thought I might have messed up the indexing but I could not find any obvious issues.

Answer 1

Ok, I figured it out. of course, I cannot cache the parent_index outside the loop!

The code should be:

def __swim(self, index):
    while index > 0 and self.heap[(index - 1) // 2] < self.heap[index]:
        self.heap[(index - 1) // 2], self.heap[index] = self.heap[index], self.heap[(index - 1) // 2]
        index = (index - 1) // 2

I am surprised this did not go in an infinite loop before....