Heap

func buildHeap(nums []int) {
	size := len(nums)

	// k, 2k+1, 2k+2;  k = (i-1)/2
	for i := size/2 - 1; i >= 0; i++ {
		siftDown(nums, i)
	}
}

func pop(heap []int) int {
	// switch to end and sift down
	item := heap[0]

	heap[0] = heap[len(heap)-1]
	heap = heap[:len(heap)-1]
	siftDown(heap, 0)

	return item
}

func push(heap []int, item int) []int {
	// append to end and sift up
	heap = append(heap, item)
	siftUp(heap, len(heap)-1)

	// here we created new slice and return it
	return heap
}

func siftUp(nums []int, i int) {
	if i <= 0 {
		return
	}

	parent := (i - 1) / 2
	if nums[parent] > nums[i] {
		nums[i], nums[parent] = nums[parent], nums[i]
		siftUp(nums, parent)
	}
}

func siftDown(nums []int, i int) {
	size := len(nums)

	smallest := i
	l, r := 2*i+1, 2*i+2
	if l < size && nums[l] < nums[smallest] {
		smallest = l
	}
	if r < size && nums[r] < nums[smallest] {
		smallest = r
	}

	if smallest != i {
		nums[i], nums[smallest] = nums[smallest], nums[i]
		siftDown(nums, smallest)
	}
}

type Interface interface {
	sort.Interface // Len() int; Less(i, j int) bool; Swap(i, j int)
	Push(x any)    // 向末尾追加一个元素
	Pop() any      // 取出并返回末尾元素（下标 Len()-1）
}

// 最小堆：height 小的优先
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].height < pq[j].height }

// 最大堆：height 大的优先（把 < 改成 > 即可）
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].height > pq[j].height }

import (
	"container/heap"
	"fmt"
)

type Cell struct {
	dx     int
	dy     int
	height int
}

type PriorityQueue []Cell

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].height < pq[j].height
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
	item := x.(Cell)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	n := len(*pq)
	item := (*pq)[n-1]
	*pq = (*pq)[0 : n-1]
	return item
}

func main() {
	cells := [][3]int{
		{0, 0, 7},
		{0, 1, 2},
		{0, 2, 5},
	}

	pq := make(PriorityQueue, 3)
	for i := 0; i < 3; i++ {
		pq[i] = Cell{cells[i][0], cells[i][1], cells[i][2]}
	}
	heap.Init(&pq)

	for pq.Len() > 0 {
		val := heap.Pop(&pq)
		fmt.Println(val)
	}

}

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 默认 = 最小堆
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
minHeap.peek(); // 1，堆顶最小

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.peek(); // 5，堆顶最大

class Cell {
    int dx, dy, height;
    Cell(int dx, int dy, int height) {
        this.dx = dx;
        this.dy = dy;
        this.height = height;
    }
}

// 按 height 升序 → 最小堆
// 等价于 Go 的 pq[i].height < pq[j].height
PriorityQueue<Cell> minByHeight =
        new PriorityQueue<>(Comparator.comparingInt(c -> c.height));

// 按 height 降序 → 最大堆
// 等价于 Go 的 pq[i].height > pq[j].height
PriorityQueue<Cell> maxByHeight =
        new PriorityQueue<>((a, b) -> b.height - a.height);

type MaxHeap []int
func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i] > h[j] } // 大顶堆
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MinHeap []int
func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i] < h[j] } // 小顶堆
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)         { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MedianFinder struct {
	lo *MaxHeap // 较小的一半（大顶堆）
	hi *MinHeap // 较大的一半（小顶堆）
}

func Constructor() MedianFinder {
	return MedianFinder{lo: &MaxHeap{}, hi: &MinHeap{}}
}

func (mf *MedianFinder) AddNum(num int) {
	// 先放进较小的一半，再把最大值移到较大的一半，保证 lo <= hi
	heap.Push(mf.lo, num)
	heap.Push(mf.hi, heap.Pop(mf.lo).(int))
	// 平衡：保持 lo 不比 hi 小（大小相等或 lo 多一个）
	if mf.lo.Len() < mf.hi.Len() {
		heap.Push(mf.lo, heap.Pop(mf.hi).(int))
	}
}

func (mf *MedianFinder) FindMedian() float64 {
	if mf.lo.Len() > mf.hi.Len() {
		return float64((*mf.lo)[0])
	}
	return (float64((*mf.lo)[0]) + float64((*mf.hi)[0])) / 2
}

class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>((a, b) -> b - a); // 大顶堆
    PriorityQueue<Integer> hi = new PriorityQueue<>();                // 小顶堆

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (lo.size() < hi.size()) lo.offer(hi.poll());
    }

    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}