Golang的堆

var a1=new java.util.PriorityQueue[Int]()
var a2=new java.util.TreeMap[Int,Int]()
var a3=new java.util.TreeSet[Int]()
var b1=scala.collection.mutable.PriorityQueue[Int]()
var b2=scala.collection.mutable.TreeMap[Int,Int]()
var b3=scala.collection.mutable.TreeSet[Int]()
var b4=scala.collection.mutable.SortedSet[Int]()
var b5=scala.collection.mutable.SortedMap[Int,Int]()

// This example demonstrates an integer heap built using the heap interface.
package heap_test

import (
	"container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func Example_intHeap() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
	// Output:
	// minimum: 1
	// 1 2 3 5
}

type Heap struct {
	ans []int
}

func (h *Heap) Len() int {
}

func (h *Heap) Less(i, j int) bool {
}

func (h *Heap) Swap(i, j int) {
}

func (h *Heap) Push(x any)  {
	
}
func (h *Heap) Pop()any{
	
}

type Heap struct {
	ans []int
}

func (h Heap) Len() int {
}

func (h Heap) Less(i, j int) bool {
}

func (h Heap) Swap(i, j int) {
}

func (h *Heap) Push(x any) {

}
func (h *Heap) Pop() any {

}

package main

import (
	"bufio"
	"container/heap"
	. "fmt"
	"io"
	"os"
	"runtime/debug"
)

type Heap struct {
	ans []int
}

func NewHeap() *Heap {
	return &Heap{}
}

func (h *Heap) Len() int {
	return len(h.ans)
}

func (h *Heap) Less(i, j int) bool {
	return h.ans[i] < h.ans[j]
}

func (h *Heap) Swap(i, j int) {
	h.ans[i], h.ans[j] = h.ans[j], h.ans[i]
}

func (h *Heap) Push(x any) {
	h.ans = append(h.ans, x.(int))
}
func (h *Heap) Pop() any {
	old := h.ans
	n := len(old)
	top := old[n-1]
	h.ans = old[0 : n-1]
	return top
}
func Solve(_r io.Reader, _w io.Writer) {
	//in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()
	//-----------------------------------------------------
	var a = NewHeap() //这是一个IntMinHeap,更改Less即可变为最大堆
	heap.Push(a, 12)  //肿么这么像python
	heap.Push(a, 87879)
	heap.Push(a, -8989)
	heap.Push(a, -889)
	heap.Push(a, -89)
	heap.Push(a, 97789) //随心所欲造数据
	for a.Len() > 0 {
		Fprintln(out, heap.Pop(a)) //呜~好像和python一样的
	}
}
func main() {
	debug.SetGCPercent(-1)
	Solve(os.Stdin, os.Stdout)
}

type Heap struct {
	ans sort.IntSlice
}

func NewHeap() *Heap {
	return &Heap{}
}

func (h *Heap) Len() int {
	return h.Len()
}

func (h *Heap) Less(i, j int) bool {
	return h.Less(i,j)
}

func (h *Heap) Swap(i, j int) {
	h.Swap(i,j)
}

func (h *Heap) Push(x any) {
	h.ans = append(h.ans, x.(int))
}
func (h *Heap) Pop() any {
	old := h.ans
	n := len(old)
	top := old[n-1]
	h.ans = old[0 : n-1]
	return top
}

package cmp

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 |
		~string
}
func Less[T Ordered](x, y T) bool {
	return (isNaN(x) && !isNaN(y)) || x < y
}

func Compare[T Ordered](x, y T) int {
	xNaN := isNaN(x)
	yNaN := isNaN(y)
	if xNaN && yNaN {
		return 0
	}
	if xNaN || x < y {
		return -1
	}
	if yNaN || x > y {
		return +1
	}
	return 0
}

func isNaN[T Ordered](x T) bool {
	return x != x
}

type Cmp[T any] interface {
	Less(T) bool
}

type Heap[T Cmp[T]] struct {
	ans []T
}

func (curr *Heap[T]) Len() int {
	return len(curr.ans)
}
func (curr *Heap[T]) Swap(x int, y int) {
	curr.ans[x], curr.ans[y] = curr.ans[y], curr.ans[x]
}
func (curr *Heap[T]) Less(i, j int) bool {
	return curr.ans[i].Less(curr.ans[j])
}
func (curr *Heap[T]) Push(x any) {
	curr.ans = append(curr.ans, x.(T))
}

func (curr *Heap[T]) Pop() any {
	old := curr.ans
	n := len(old)
	x := old[n-1]
	curr.ans = old[0 : n-1]
	return x
}
func NewHeap[T Cmp[T]]() *Heap[T] {
	return &Heap[T]{}
}

type Pair[T cmp.Ordered] struct {
	x, y T
}

func NewPair[T cmp.Ordered](x T, y T) Pair[T] {
	return Pair[T]{x, y}
}
func (curr Pair[T]) Less(other Pair[T]) bool {
	if curr.x == other.x {
		return curr.y < other.y
	}
	return curr.x < other.x
}

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"io"
	"os"
	"runtime/debug"
)

type Cmp[T any] interface {
	Less(T) bool
}
type Heap[T Cmp[T]] struct {
	ans []T
}

func (curr *Heap[T]) Len() int {
	return len(curr.ans)
}
func (curr *Heap[T]) Swap(x int, y int) {
	curr.ans[x], curr.ans[y] = curr.ans[y], curr.ans[x]
}
func (curr *Heap[T]) Less(i, j int) bool {
	return curr.ans[i].Less(curr.ans[j])
}
func (curr *Heap[T]) Push(x any) {
	curr.ans = append(curr.ans, x.(T))
}

func (curr *Heap[T]) Pop() any {
	old := curr.ans
	n := len(old)
	x := old[n-1]
	curr.ans = old[0 : n-1]
	return x
}
func NewHeap[T Cmp[T]]() *Heap[T] {
	return &Heap[T]{}
}

type Pair struct {
	x, y int
}

func NewPair(x int, y int) Pair {
	return Pair{x, y}
}
func (curr Pair) Less(other Pair) bool {
	if curr.x == other.x {
		return curr.y < other.y
	}
	return curr.x < other.x
}
func Solve(_r io.Reader, _w io.Writer) {
	//in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()
	//-----------------------------------------------------
	var a = NewHeap[Pair]()
	heap.Push(a, NewPair(154, 21))
	heap.Push(a, NewPair(154, 31))
	heap.Push(a, NewPair(28, 29))
	heap.Push(a, NewPair(456, 2321))
	heap.Push(a, NewPair(456, 232))
	for a.Len() > 0 {
		var a = heap.Pop(a).(Pair)
		fmt.Println(a.x, a.y)
	}
}
func main() {
	debug.SetGCPercent(-1)
	Solve(os.Stdin, os.Stdout)
}

type M int

func (curr M) Less(other M) bool {
	return curr < other
}

package main

import (
	"bufio"
	"cmp"
	"container/heap"
	"fmt"
	"io"
	"os"
	"runtime/debug"
)

type Cmp[T any] interface {
	Less(T) bool
}
type Heap[T Cmp[T]] struct {
	ans []T
}

func (curr *Heap[T]) Len() int {
	return len(curr.ans)
}
func (curr *Heap[T]) Swap(x int, y int) {
	curr.ans[x], curr.ans[y] = curr.ans[y], curr.ans[x]
}
func (curr *Heap[T]) Less(i, j int) bool {
	return curr.ans[i].Less(curr.ans[j])
}
func (curr *Heap[T]) Push(x any) {
	curr.ans = append(curr.ans, x.(T))
}

func (curr *Heap[T]) Pop() any {
	old := curr.ans
	n := len(old)
	x := old[n-1]
	curr.ans = old[0 : n-1]
	return x
}
func NewHeap[T Cmp[T]]() *Heap[T] {
	return &Heap[T]{}
}

type Pair[T cmp.Ordered] struct {
	x, y T
}

func NewPair[T cmp.Ordered](x T, y T) Pair[T] {
	return Pair[T]{x, y}
}
func (curr Pair[T]) Less(other Pair[T]) bool {
	if curr.x == other.x {
		return curr.y < other.y
	}
	return curr.x < other.x
}

type M int

func (curr M) Less(other M) bool {
	return curr < other
}

func Solve(_r io.Reader, _w io.Writer) {
	//in := bufio.NewReader(_r)
	out := bufio.NewWriter(_w)
	defer out.Flush()
	//-----------------------------------------------------
	var a = NewHeap[M]()
	heap.Push(a, M(454))
	heap.Push(a, M(456))
	heap.Push(a, M(487))
	heap.Push(a, M(787978))
	heap.Push(a, M(787798897))
	for a.Len() > 0 {
		fmt.Println(heap.Pop(a))
	}
}
func main() {
	debug.SetGCPercent(-1)
	Solve(os.Stdin, os.Stdout)
}

// The max built-in function returns the largest value of a fixed number of
// arguments of [cmp.Ordered] types. There must be at least one argument.
// If T is a floating-point type and any of the arguments are NaNs,
// max will return NaN.
func max[T cmp.Ordered](x T, y ...T) T

// The min built-in function returns the smallest value of a fixed number of
// arguments of [cmp.Ordered] types. There must be at least one argument.
// If T is a floating-point type and any of the arguments are NaNs,
// min will return NaN.
func min[T cmp.Ordered](x T, y ...T) T

// The print built-in function formats its arguments in an
// implementation-specific way and writes the result to standard error.
// Print is useful for bootstrapping and debugging; it is not guaranteed
// to stay in the language.
func print(args ...Type)

// The println built-in function formats its arguments in an
// implementation-specific way and writes the result to standard error.
// Spaces are always added between arguments and a newline is appended.
// Println is useful for bootstrapping and debugging; it is not guaranteed
// to stay in the language.
func println(args ...Type)

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This example demonstrates a priority queue built using the heap interface.
package heap_test

import (
	"container/heap"
	"fmt"
)

// An Item is something we manage in a priority queue.
type Item struct {
	value    string // The value of the item; arbitrary.
	priority int    // The priority of the item in the queue.
	// The index is needed by update and is maintained by the heap.Interface methods.
	index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

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

func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority > pq[j].priority
}

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

func (pq *PriorityQueue) Push(x any) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

// This example creates a PriorityQueue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func Example_priorityQueue() {
	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)

	// Insert a new item and then modify its priority.
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	heap.Push(&pq, item)
	pq.update(item, item.value, 5)

	// Take the items out; they arrive in decreasing priority order.
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
	// Output:
	// 05:orange 04:pear 03:banana 02:apple
}