Go -- maximum heap and minimum heap

The biggest pile （ Big pile top ）： The heap top element remains at its maximum

The smallest pile （ Small cap pile ）： The heap top elements are kept to a minimum

 

1、 The structure of the pile

   A heap is a complete binary tree （ A complete binary tree is part of a full binary tree ）, According to the structure of the tree, it can be represented by an array , As shown in the following figure, the complete binary tree can be represented as an array on the right

As a large top pile , The following features also need to be observed ：

1. The root node is the maximum value of the whole heap
2. The value of each node is not less than its child nodes

Corresponding to the array ：

1. a[1] Is the maximum

2. The node is i, Then the child node is 2i and 2i+1, namely a[i]>=a[2i] && a[i]>=a[2i+1]

3. The node is i, Then the parent node is i/2

2、 Insert elements into the heap

When you insert a new element , You need to find its position in the array

//less() Compare element sizes ,exch() Swap two element positions 
func push(k int, datas *[]int){
    
   for i>1 && less((*datas)[i/2],(*datas)[i]){
       // Compare i/2 and i The size of the position element , Exit when comparing to the root node 
       exch(&(*datas)[i/2], &(*datas)[i])   // i/2 The location element is less than i Location elements , The parent node element is smaller than the child node , Need to swap 
       i = i/2
   }
}

func less(a int,b int) bool{
    
	return a < b
}

 

3、 Pop up the elements in the heap

Pop up the largest element , Swap the last element with the largest element , Then adjust the position of the last element to the correct position

func pop(i int, datas []int){
    
    length:=len(datas)-2
    for 2*i<=length{
    
        max:=0
        if 2*i<length && less(datas[2*i], datas[2*i+1]){
      // Find two child nodes 2i and 2i+1 Maximum of 
            max=2*i+1
        }
        if !less(datas[i], datas[max]){
      //  The parent node is larger than the child node , The exchange is over 
            break
        }
        //  Child is greater than parent , In exchange for 
        exch(&datas[i], &datas[max])
        i = max
    }
}

 

4、go Heap in

go Provided in container/heap To implement heap , The types of elements in the heap need to implement heap.Interface This interface .

The following is an example of the maximum heap ：

type IntHeap []int

func (h IntHeap) Len() int           {
     return len(h) }
func (h IntHeap) Less(i, j int) bool {
     return h[i] > h[j] }
// The smallest pile 
//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 interface{
    }) {
    
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{
    } {
    
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}


func main()  {
    
	h := &IntHeap{
    3, 1, 2, 5}
	heap.Init(h)
  heap.Push(h, 4)
	for h.Len() > 0 {
    
		fmt.Printf("%d ", heap.Pop(h))
	}
}

 
If there is any wrong , Please point out ~