// 第 15 周 – 用数组（下标从 1 开始）实现的大顶堆，以及 container/heap 包
// 运行：go run ./w15/maxheap
package main

import (
	"container/heap"
	"fmt"
)

type MaxHeap struct {
	a []int // 不使用 a[0]
}

func NewMaxHeap() *MaxHeap { return &MaxHeap{a: []int{0}} }

func (h *MaxHeap) Len() int { return len(h.a) - 1 }

// Insert：放到末尾，然后上浮 – O(log n)
func (h *MaxHeap) Insert(x int) {
	h.a = append(h.a, x)
	i := h.Len()
	for i > 1 && h.a[i/2] < h.a[i] {
		h.a[i], h.a[i/2] = h.a[i/2], h.a[i]
		i /= 2
	}
}

// RemoveMax：把最后一个元素放到根上，然后下沉 – O(log n)
func (h *MaxHeap) RemoveMax() int {
	n := h.Len()
	top := h.a[1]
	h.a[1] = h.a[n]
	h.a = h.a[:n]
	n--
	i := 1
	for 2*i <= n {
		c := 2 * i
		if c+1 <= n && h.a[c+1] > h.a[c] {
			c++
		}
		if h.a[i] >= h.a[c] {
			break
		}
		h.a[i], h.a[c] = h.a[c], h.a[i]
		i = c
	}
	return top
}

// IntMaxHeap:container/heap.Interface 的实现
type IntMaxHeap []int

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

func main() {
	h := NewMaxHeap()
	for _, x := range []int{40, 70, 20, 90, 50, 80, 60} {
		h.Insert(x)
		fmt.Printf("Insert(%d): %v\n", x, h.a[1:])
	}
	h.Insert(85)
	fmt.Println("Insert(85):", h.a[1:])
	fmt.Print("RemoveMax sequence: ")
	for h.Len() > 0 {
		fmt.Print(h.RemoveMax(), " ")
	}
	fmt.Println()

	ih := &IntMaxHeap{40, 70, 20, 90}
	heap.Init(ih)
	fmt.Println("container/heap: Pop =", heap.Pop(ih), ", the next max =", (*ih)[0])
}