Heap Cheat Sheet

Here’s a cheat sheet for working with heaps in Python, specifically focusing on the implementation of a binary heap:

Binary Heap Implementation

A binary heap is a complete binary tree where each node has a value less than or equal to its children (for a max heap) or greater than or equal to its children (for a min heap).

Max Heap:

class MaxHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        self.heap.append(value)
        self._heapify_up()

    def pop(self):
        if len(self.heap) == 0:
            return None

        self._swap(0, len(self.heap) - 1)
        max_value = self.heap.pop()
        self._heapify_down()

        return max_value

    def _heapify_up(self):
        index = len(self.heap) - 1
        while index > 0:
            parent_index = (index - 1) // 2
            if self.heap[index] > self.heap[parent_index]:
                self._swap(index, parent_index)
                index = parent_index
            else:
                break

    def _heapify_down(self):
        index = 0
        while True:
            left_child_index = 2 * index + 1
            right_child_index = 2 * index + 2
            largest = index

            if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest]:
                largest = left_child_index

            if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest]:
                largest = right_child_index

            if largest != index:
                self._swap(index, largest)
                index = largest
            else:
                break

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

Min Heap:

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, value):
        self.heap.append(value)
        self._heapify_up()

    def pop(self):
        if len(self.heap) == 0:
            return None

        self._swap(0, len(self.heap) - 1)
        min_value = self.heap.pop()
        self._heapify_down()

        return min_value

    def _heapify_up(self):
        index = len(self.heap) - 1
        while index > 0:
            parent_index = (index - 1) // 2
            if self.heap[index] < self.heap[parent_index]:
                self._swap(index, parent_index)
                index = parent_index
            else:
                break

    def _heapify_down(self):
        index = 0
        while True:
            left_child_index = 2 * index + 1
            right_child_index = 2 * index + 2
            smallest = index

            if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
                smallest = left_child_index

            if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
                smallest = right_child_index

            if smallest != index:
                self._swap(index, smallest)
                index = smallest
            else:
                break

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

Heap Operations

Building a Heap:

def build_heap(array):
    heap = MinHeap()
    for element in array:
        heap.push(element)
    return heap

Heap Sort:

def heap_sort(array):
    heap = build_heap(array)
    sorted_array = []
    while len(heap.heap) > 0:
        sorted_array.append(heap.pop())
    return sorted_array

These snippets cover basic operations and implementations of binary heaps. For more advanced heap algorithms and variations, refer to specialized resources and textbooks.