Go language uses heap to implement priority queues

package main

import (
	"container/heap"
	"fmt"
)

type Interface interface {
	
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

type IntHeap []int  // Define a type
func (h IntHeap) Len() int { return len(h) }  //Bind len method, return lengthfunc (h IntHeap) Less(i, j int) bool {  // Bind less method	return h[i] &lt; h[j]  // If h[i]<h[j] generates a small root heap, if h[i]>h[j] generates a large root heap}
func (h IntHeap) Swap(i, j int) {  // Bind swap method and swap two element positions	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Pop() interface{} {  // Bind the pop method, take out an element from the end and return	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *IntHeap) Push(x interface{}) {  // Bind push method and insert new element	*h = append(*h, x.(int))
}

func main() {
	h := &IntHeap{2, 1, 5, 6, 4, 3, 7, 9, 8, 0}  // Create slice	(h)  // Initialize heap	(*h)
	((h))  // Call pop	(h, 6)  // Call push	(*h)
	for len(*h) > 0 {
		("%d ", (h))
	}
}

h := &IntHeap{3, 8, 6}  // Create raw data of type IntHeapfunc Init(h Interface)  // Initialize the heap and generate a small root heap (or large root heap)func Push(h Interface, x interface{})  // Insert content into the pilefunc Pop(h Interface) interface{}  // pop content from the top of the pilefunc Remove(h Interface, i int) interface{}  // Delete data from the specified location and return the deleted datafunc Fix(h Interface, i int)  // fromiAfter the location data has changed，Rebalancing the heap，This method is used by the priority queue

// A heap must be initialized before any of the heap operations
// can be used. Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// Its complexity is O(n) where n = ().
//
func Init(h Interface) {
	// heapify
	n := ()  // Get the length of the data	for i := n/2 - 1; i >= 0; i-- {  // Starting from half of the length and until the 0th data, the down method is called in each position. The function implemented by the down method is to ensure that the heap is formed from the down position.		down(h, i, n)
	}
}

func down(h Interface, i0, n int) bool {
	i := i0  // The intermediate variable is stored for the first time. The node position that needs to be formed in the downward direction is to ensure the node position that needs to be formed in the heap.	for {  // A dead loop		j1 := 2*i + 1  // The left child of the i node		if j1 &gt;= n || j1 &lt; 0 { // j1 < 0 after int overflow // Ensure that the left child does not cross the line			break
		}
		j := j1 // left child // The intermediate variable j is assigned as the left child child first, and then j will be assigned as the position of the smallest (large) child among the left child child		if j2 := j1 + 1; j2 &lt; n &amp;&amp; !(j1, j2) {
			j = j2 // = 2*i + 2  // right child
		}  // After this, j is assigned as the position of the smallest (large) child of the two children (minimum or maximum is determined by the definition in Less)		if !(j, i) {
			break
		}  // If j is greater than (less than) i, ​​the loop is terminated		(i, j)  // Otherwise, exchange the values ​​of i and j positions		i = j  // Let i=j, continue the loop, and ensure that the sub-number at position j is the heap structure	}
	return i &gt; i0
}

func up(h Interface, j int) {
	for {  // A dead loop		i := (j - 1) / 2 // parent // parent of j node		if i == j || !(j, i) {  // If the boundary is exceeded, or the heap condition is met, the loop ends			break
		}
		(i, j)  // Otherwise, exchange the node with the parent node		j = i  // Continue to check the parent node until the root node	}
}

func Push(h Interface, x interface{}) {
	(x)  // Put the newly inserted node to the end	up(h, ()-1)  // Ensure that the newly inserted node can ensure the heap structure on the Internet}

func Pop(h Interface) interface{} {
	n := () - 1  // Exchange the last node with the first node, then re-ensure the heap structure from the root node, and finally throw out the last node data and return it	(0, n)
	down(h, 0, n)
	return ()
}

func Remove(h Interface, i int) interface{} {
	n := () - 1  poponlyremoveSpecial circumstances，removeYesiThe node of the location is exchanged with the last node，After that, guaranteediThe nodes are both down and up to ensure the heap structure，Finally throw out the data of the last node and return it
	if n != i {
		(i, n)
		down(h, i, n)
		up(h, i)
	}
	return ()
}

func Fix(h Interface, i int) {
	if !down(h, i, ()) {  // After the value of the i node changes, it is necessary to ensure the rebalancing of the heap. First call down to ensure the heap structure below the node. If there is position exchange, it is necessary to ensure the heap structure upwards of the node, otherwise there is no need to ensure the heap structure upwards, a small optimization		up(h, i)
	}
}

package main

import (
	"container/heap"
	"fmt"
)

type Item struct {
	value    string // The data in the priority queue can be of any type, using string here	priority int    // Priority of nodes in priority queue	index    int    // index is the location of the node in the heap}

// Priority queues need to implement heap's interfacetype PriorityQueue []*Item

// Bind Len methodfunc (pq PriorityQueue) Len() int {
	return len(pq)
}

//Bind the Less method, the less than sign is used here, and the small root heap is generatedfunc (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

// Bind swap methodfunc (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index, pq[j].index = i, j
}

// Bind the put method and set index to -1 to identify that the data has already had a priority queuefunc (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	 = -1
	return item
}

// Bind push methodfunc (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	 = n
	*pq = append(*pq, item)
}

// Update the position of the item with priority and value in the priority queuefunc (pq *PriorityQueue) update(item *Item, value string, priority int) {
	 = value
	 = priority
	(pq, )
}

func main() {
	// Create nodes and design their priorities	items := map[string]int{"Ermao": 5, "Zhang San": 3, "Dog egg": 9}
	i := 0
	pq := make(PriorityQueue, len(items)) // Create a priority queue and initialize it	for k, v := range items {             // Put nodes in priority queue		pq[i] = &Item{
			value:    k,
			priority: v,
			index:    i}
		i++
	}
	(&pq) // Initialize the heap	item := &Item{ // Create an item		value:    "Li Si",
		priority: 1,
	}
	(&pq, item)           // Enter the priority queue	(item, , 6) // Update item priority	for len(pq) > 0 {
		item := (&pq).(*Item)
		("%.2d:%s index:%.2d\n", , , )
	}
}