I found an implementation of a MaxHeap in python. It performs as intended; however, I'm confused about array indexing--namely, because the max element is stored at index 0 and I had expected this to break left/right child indexing (reference the __bubbleDown method.)

class MaxHeap:
    def __init__(self, items=[]):
        self.heap = []
        for i in items:
            self.heap.append(i)
            self.__floatUp(len(self.heap) - 1)

    def push(self, data):
        self.heap.append(data)
        self.__floatUp(len(self.heap) - 1)

    def peek(self):
        if self.heap[0]:
            return self.heap[0]
        else:
            return False
            
    def pop(self):
        if len(self.heap) > 0:
            self.__swap(0, len(self.heap) - 1)
            max = self.heap.pop()
            self.__bubbleDown(0)
        elif len(self.heap) == 0:
            max = self.heap.pop()
        else: 
            max = False
        return max

    def __swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def __floatUp(self, index):
        parent = index//2

        if self.heap[index] > self.heap[parent]:
            self.__swap(index, parent)
            self.__floatUp(parent)

    def __bubbleDown(self, index):
        left = index * 2
        right = index * 2   1
        largest = index
        if len(self.heap) > left and self.heap[largest] < self.heap[left]:
            largest = left
        if len(self.heap) > right and self.heap[largest] < self.heap[right]:
            largest = right
        if largest != index:
            self.__swap(index, largest)
            self.__bubbleDown(largest)
     

# tests
m = MaxHeap([95, 3, 21])
m.push(10)
print(str(m.heap[0:len(m.heap)]))
print(str(m.pop()))

If the first element is at index 0, its left and right children should be computed as

left: 0 * 2 => 0,

right: 0 * 2 1 => 1

Why is this not an issue?

CodePudding user response：

First of all, you are right that this computation of left and right is not how it should be, but... it still works.

With this way of working we have a graph where the root's left child is actually a self-reference (a loop). Because the code never continues a __floatUp or __bubbleDown recursive call when the values of parent and child are equal, this loop in the graph will never be traversed.

So we have here a root node that has at the most only one real child (its right child). From that child onwards, things return to normal. Except for this strange root, all other nodes root a subtree that is a complete binary tree. This strange root makes the "heap" slightly less optimal, as often the tree will have one more level than absolutely necessary. But it will still give correct results.

Other remarks

Some other strange things in this code:

• peek will raise an error when the heap is empty.
• peek will give the wrong result when the root's value is a falsy value, like 0. Then it will return False. These two points should be fixed by applying the same len check as pop does.
• In pop the final else block can never execute, as the value of len() can never be anything else than > 0 or == 0. This makes no sense.
• pop will raise an error when the heap is empty, because then the middle case will execute, where the code tries to pop from an empty list

The video

You have not correctly represented what the video provides as code.

The video actual explains at 0:50 that the array should start at index 1, ignoring index 0.

At 3:45 and further, you can see that the presenter has indeed coded it that way. The code you present here is not the same as theirs. It seems you have tried to adapt it somehow, and thereby introduced more problems than the original code had.