Use container/heap package in golang

Package heap provides heap operations for all types implemented. A heap is a tree. The value of each node of this tree is smaller than the value of its child nodes. The smallest value of the entire tree is located at the root, that is, the position of index 0.

Package heap sampling interface form to satisfy different types of comparisons.

type Interface interface {
	
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}
// 
type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

Therefore, the object you want to compare must be implemented first

Simple sorting

type myHeap []int

func (h *myHeap) Less(i, j int) bool {
	return (*h)[i] &lt; (*h)[j]
}

func (h *myHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func (h *myHeap) Len() int {
	return len(*h)
}

// Pop up the last one, because the minimum value has been switched to the last onefunc (h *myHeap) Pop() (v any) {
	*h, v = (*h)[:()-1], (*h)[()-1]
	return
}

func (h *myHeap) Push(v any) {
	*h = append(*h, v.(int))
}

//Sorting from small to largefunc HeapSort(data []int) []int {
	hp := &amp;myHeap{}
	for _, v := range data {
		(hp, v)
	}
	(hp)
	res := make([]int, ())
	for i := 0; () &gt; 0; i++ {
		res[i] = (hp).(int)
	}

	return res
}

// data = 6, 0, 1, 7, 9, 4, 3, 8, 2, 5
// What is stored in hp is 0, 2, 1, 6, 5, 4, 3, 8, 7, 9

Priority queue

Use a priority field to represent the priority size and an index field to represent the index.

type Item struct {
	value    string
	priority int
	index    int
}
type PriorityQueue []*Item

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

func (pq PriorityQueue) Less(i, j int) bool {
	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)
	 = 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
	 = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	 = value
	 = priority
	(pq, )
}

func PriorityQueueTest() {
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	(&pq)

	item := &Item{
		value:    "orange",
		priority: 1,
	}
	(&pq, item)
	(item, , 5)

	for () > 0 {
		item := (&pq).(*Item)
		("%.2d:%s ", , )
	}
}

Sort by time

type TimeSortedQueueItem struct {
	Time  int64
	Value interface{}
}

type TimeSortedQueue []*TimeSortedQueueItem

func (q TimeSortedQueue) Len() int           { return len(q) }
func (q TimeSortedQueue) Less(i, j int) bool { return q[i].Time < q[j].Time }
func (q TimeSortedQueue) Swap(i, j int)      { q[i], q[j] = q[j], q[i] }

func (q *TimeSortedQueue) Push(v interface{}) {
	*q = append(*q, v.(*TimeSortedQueueItem))
}

func (q *TimeSortedQueue) Pop() interface{} {
	n := len(*q)
	item := (*q)[n-1]
	*q = (*q)[0 : n-1]
	return item
}

func NewTimeSortedQueue(items ...*TimeSortedQueueItem) *TimeSortedQueue {
	q := make(TimeSortedQueue, len(items))
	for i, item := range items {
		q[i] = item
	}
	(&q)
	return &q
}

func (q *TimeSortedQueue) PushItem(time int64, value interface{}) {
	(q, &TimeSortedQueueItem{
		Time:  time,
		Value: value,
	})
}

func (q *TimeSortedQueue) PopItem() interface{} {
	if () == 0 {
		return nil
	}

	return (q).(*TimeSortedQueueItem).Value
}

This is the end of this article about the use of container/heap packages in golang. For more related contents of golang container/heap packages, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!