# Generated from the published Markdown; run scripts/build_language_examples.py to refresh.
# Independent examples may reuse top-level names. Python remains the explanation language.


# topics/heaps/heap-insertion.md
def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] <= heap[i]:
            break
        heap[parent], heap[i] = heap[i], heap[parent]
        i = parent

def push_min(heap, priority):
    heap.append(priority)
    sift_up(heap, len(heap) - 1)

# topics/heaps/heap-removal.md
def peek_min(heap):
    if not heap:
        raise IndexError("peek at empty heap")
    return heap[0]

# topics/heaps/heap-removal.md
def sift_down(heap, i):
    n = len(heap)
    while 2 * i + 1 < n:
        child = 2 * i + 1
        right = child + 1
        if right < n and heap[right] < heap[child]:
            child = right
        if heap[i] <= heap[child]:
            break
        heap[i], heap[child] = heap[child], heap[i]
        i = child

# topics/heaps/heap-removal.md
def pop_min(heap):
    if not heap:
        raise IndexError("pop from empty heap")
    result = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        sift_down(heap, 0)
    return result

# topics/heaps/heap-construction.md
def build_min_heap(values):
    heap = list(values)
    for i in range(len(heap) // 2 - 1, -1, -1):
        sift_down(heap, i)
    return heap

# topics/heaps/heap-applications.md
import heapq

values = [9, 5, 6, 2, 3, 4]
heapq.heapify(values)
heapq.heappush(values, 1)
assert heapq.heappop(values) == 1
assert values[0] == 2

# topics/heaps/heap-applications.md
from itertools import count

class MinPriorityQueue:
    def __init__(self):
        self._heap = []
        self._sequence = count()

    def __len__(self):
        return len(self._heap)

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def extract_min(self):
        return self.remove_min()

    def insert(self, item, priority):
        entry = (priority, next(self._sequence), item)
        heapq.heappush(self._heap, entry)

    def peek_min(self):
        if not self._heap:
            raise IndexError("peek at empty priority queue")
        return self._heap[0][2]

    def remove_min(self):
        if not self._heap:
            raise IndexError("remove from empty priority queue")
        return heapq.heappop(self._heap)[2]

# topics/heaps/heap-applications.md
class MaxPriorityQueue:
    def __init__(self):
        self._queue = MinPriorityQueue()

    def __len__(self):
        return len(self._queue)

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def insert(self, item, priority):
        self._queue.insert(item, -priority)

    def peek_max(self):
        return self._queue.peek_min()

    def remove_max(self):
        return self._queue.remove_min()

    def extract_max(self):
        return self.remove_max()

# topics/heaps/heap-sorting-costs.md
def heapsort(a):
    def sift_down_max(i, end):
        while 2 * i + 1 < end:
            child = 2 * i + 1
            right = child + 1
            if right < end and a[right] > a[child]:
                child = right
            if a[i] >= a[child]:
                break
            a[i], a[child] = a[child], a[i]
            i = child

    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down_max(i, len(a))
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down_max(0, end)