Go implements large/small root heaps to solve the TopK problem

The TopK problem: In an array, find the first K largest or smallest numbers. The simple common solutions are sort, local sort, and you can also use large/small root heaps. The large root heap is used to solve the problem of the first big K, and the small root heap is used to solve the problem of the first big K.

The idea of solving the TopK problem is to build the first K elements of an array into a heap and then scan from the K+1 element to the end. For the top K problems, a small root heap is used. During the scan, if the element is larger than the top heap element, the top heap element is popped out and a new element is inserted. The first K small problem is the opposite, using a large root heap, the element is smaller than the top of the heap pop the top of the heap and insert new elements.

For heaps, there are two main operations: Push() inserts a new element, Pop() pops the top element, and if it’s a large root heap, Pop the largest element, and vice versa for small root heaps. There is no built-in heap container in Go that can be called directly, and you need to implement some interfaces to use it.

Referencing the definitions in “container/heap”, you will need to implement the methods in sort.interface (i.e., Less(), Len(), Swap()), and Push() and Pop() methods. Before we can create a heap.

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

Refer to go small root pile of sample source directory/usr/local/go/SRC/container/heap/example_intheap_test. Go. Heap used for slice storage. You can see that the user-defined Pop() method only needs to return the end of the slice and shorten it by one space, and the Push() method only needs to add a new element to the slice used in the heap. The heap is created and sorted by other methods in the “container/heap” package. See the source code for details on how they are implemented.

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 interface{}) { // 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() interface{} { 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}

If you want to find the smallest number of k numbers, you need to use a large root heap. In the example above we have seen how to implement the small root heap, what about the large root heap. Mainly different from the Less() method, we can simply define the Less() method as, if element I is larger than element j, then element I is considered to be smaller than element j, and reverse sorting is implemented. If you want to reuse the heap more easily, you can add a field to the structure of the heap to determine whether it is a large or small root heap. The Less() method uses that field to determine how to return the heap. Scan through the incoming array, initialize the first k elements into the large root heap, and scan from the k+1 element, which is larger than the top of the heap, pop out the top of the heap and insert new elements. The top element of the heap can be obtained simply by H [0].

Import "container/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]} 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 getLeastNumbers(arr []int, arr []int, k int) []int { h := make(IntHeap,k) hp:=&h copy(h ,IntHeap(arr[:k+1])) heap.Init(hp) for i:=k; i<len(arr); i++{ if arr[i]<h[0]{ heap.Pop(hp) heap.Push(hp,arr[i]) } } return h }