## 最大堆、最小堆 實作

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

    @property
    def length(self):
        return len(self.heap)

    def insert(self, val: int):
        self.heap.append(val)
        self.swin(self.length - 1)

    def pop(self):
        value = self.heap[0]
        self.swap(0, self.length - 1)
        self.heap.pop()
        self.sink(0)
        return value

    def parent(self, k):
        return (k - 1) // 2

    def swap(self, m: int, n: int):
        self.heap[m], self.heap[n] = self.heap[n], self.heap[m]


class MaxHeap(Heap):
    def swin(self, k: int):
        while k > 0 and self.heap[self.parent(k)] < self.heap[k]:
            self.swap(self.parent(k), k)
            k = self.parent(k)

    def sink(self, k: int):
        while k * 2 + 1 < self.length:
            left, right = k * 2 + 1, k * 2 + 2
            target = left
            if right < self.length and self.heap[left] < self.heap[right]:
                target = right
            if self.heap[k] >= self.heap[target]:
                break
            self.swap(k, target)
            k = target


class MinHeap(Heap):
    def swin(self, k: int):
        while k > 0 and self.heap[self.parent(k)] > self.heap[k]:
            self.swap(self.parent(k), k)
            k = self.parent(k)

    def sink(self, k: int):
        while k * 2 + 1 < self.length:
            left, right = k * 2 + 1, k * 2 + 2
            target = left
            if right < self.length and self.heap[left] > self.heap[right]:
                target = right
            if self.heap[k] <= self.heap[target]:
                break
            self.swap(k, target)
            k = target