Binary Heap

heap.py

class BinaryMaxHeap:
    def __init__(self):
        self.size = -1
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def sift_up(self, i):
        while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)
    
    def sift_down(self, i):
        if i >= self.size // 2 and i <= self.size:
            return
        current_value = self.heap[i]
        left_child, right_child = self.left_child(i), self.right_child(i)
        if current_value < self.heap[left_child] or current_value < self.heap[right_child]:
            if self.heap[left_child] > self.heap[right_child]:
                current_value, self.heap[left_child] = self.heap[left_child], current_value 
                self.sift_down(left_child)
            else:
                current_value, self.heap[right_child] = self.heap[right_child], current_value
                self.sift_down(right_child)
            
    def insert(self, val):
        self.heap.append(val)
        self.size += 1
        self.sift_up(self.size)
    
    def extract_max(self):
        if self.size == -1:
            raise IndexError("Out of bounds")
        max_value = self.heap[0]
        if self.size > 0:
            self.heap[0] = self.heap[self.size - 1]
            self.sift_down(0)
        self.size -= 1
        return max_value
    
    def remove(self, i):
        self.heap[i] = float('inf')
        self.sift_up(i)
        self.extract_max()
    
    def change_priority(self, i, p):
        if self.size == -1:
            raise IndexError("Out of bounds")
        old = self.heap[i]
        self.heap[i] = p
        if p > old:
            self.sift_up(i)
        else:
            self.sift_down(i)

    def build_heap(self, arr):
        i = len(arr) // 2
        self.size = len(arr) - 1
        self.heap = arr[:]
        while i > 0:
            self.sift_down(i)
            i -= 1

h = BinaryMaxHeap()
a = [42, 29, 18, 14, 7, 18, 12, 11, 13]
# h.build_heap(a)
for i in a: h.insert(i)
print(h.heap)