在1,000,000個(gè)數(shù)字中,選出前100個(gè)最大的數(shù)字
// 在n個(gè)元素中選出前m個(gè)元素
// 如果用排序算法,最快時(shí)間 NlogN
// 用最小二叉堆形式實(shí)現(xiàn)的優(yōu)先隊(duì)列,最快時(shí)間是 NlogM

算法思路：
（1）最小堆中每次取出來的值都是堆中的最小值，利用這個(gè)性質(zhì)維護(hù)一個(gè)m個(gè)節(jié)點(diǎn)最小堆；
（2）遍歷一篇數(shù)組，每次取出來的值和最小堆中的最小值做對(duì)比，如果大于最小堆中的最小值，則和該最小值做替換；
（3）重新獲取一次堆中最小值，重復(fù)第（2）步，直到遍歷數(shù)組結(jié)束，之后堆中就是前m個(gè)最大值；

最小堆的定義和實(shí)現(xiàn)
type minHeap struct {
    size int
    nums []int
}

func NewMinHeap() *minHeap {
    return &minHeap{}
}

func Parent(i int) int {
    if i == 0 {
        return 0
    }
    return (i - 1) / 2
}

func LeftChild(i int) int {
    return 2*i + 1
}

func (heap *minHeap) IsEmpty() bool {
    return heap.size == 0
}

func (heap *minHeap) GetSize() int {
    return heap.size
}

func (heap *minHeap) GetMinVal() (int, error) {
    if heap.IsEmpty() {
        return 0, errors.New(
            "failed to geiMinVal,minHeap is empty.")
    }
    return heap.nums[0], nil
}

func siftDown(heap *minHeap, parI int) {
    var minI int
    for {
        leftI := LeftChild(parI)
        switch {
        case leftI+1 > heap.size:
            return
        case leftI+2 > heap.size:
            if heap.nums[parI] > heap.nums[leftI] {
                heap.nums[parI], heap.nums[leftI] = heap.nums[leftI],
                    heap.nums[parI]
            }
            return
        case heap.nums[leftI] <= heap.nums[leftI+1]:
            minI = leftI
        case heap.nums[leftI] > heap.nums[leftI+1]:
            minI = leftI + 1
        }

        if heap.nums[parI] > heap.nums[minI] {
            heap.nums[parI], heap.nums[minI] = heap.nums[minI],
                heap.nums[parI]
        }
        parI = minI
    }
}

func (heap *minHeap) SiftUp(i int) {
    heap.nums = append(heap.nums, i)
    parI := Parent(heap.size)
    childI := heap.size

    for heap.nums[parI] > heap.nums[childI] {
        heap.nums[parI], heap.nums[childI] = heap.nums[childI],
            heap.nums[parI]
        childI = parI
        parI = Parent(parI)
    }
    heap.size++
}

func (heap *minHeap) SiftDown() (int, error) {
    minVal, err := heap.GetMinVal()
    if err != nil {
        return minVal, err
    }

    heap.size--
    heap.nums[0], heap.nums[heap.size] = heap.nums[heap.size], 0

    siftDown(heap, 0)
    return minVal, nil
}

func (heap *minHeap) Replace(i int) (int, error) {
    minVal, err := heap.GetMinVal()
    if err != nil {
        return minVal, err
    }
    heap.nums[0] = i

    siftDown(heap, 0)
    return minVal, nil
}

求前m個(gè)最大值的行數(shù)定義
func maxNums(nums []int, m int) (resp []int) {
    h := minheap1.NewMinHeap()

    for i := 0; i < m; i++ {
        h.SiftUp(nums[i])
    }

    minVal, _ := h.GetMinVal()
    for _, v := range nums[m:] {
        if v > minVal {
            h.Replace(v)
            minVal, _ = h.GetMinVal()
        }
    }
    for i := 0; i < m; i++ {
        v, _ := h.SiftDown()
        resp = append(resp, v)
    }
    return
}

測(cè)試邏輯
func main() {
    buf := []int{}
    for i := 0; i < 1000000; i++ {
        buf = append(buf, 50+rand.Intn(2000000))
    }

    resp := maxNums(buf, 10)
    fmt.Println("最小堆排序出前m個(gè)最大值:")
    fmt.Println(resp)

    fmt.Println("----")
    sort.Ints(buf)
    fmt.Println("go自帶排序接口排序結(jié)果:")
    fmt.Println(buf[len(buf)-10 : len(buf)])
}

測(cè)試結(jié)果
最小堆排序出前m個(gè)最大值:
[2000039 2000039 2000040 2000041 2000041 2000043 2000044 2000048 2000048 2000049]
----
go自帶排序接口排序結(jié)果:
[2000039 2000039 2000040 2000041 2000041 2000043 2000044 2000048 2000048 2000049]

相關(guān)問題：
求n個(gè)數(shù)字中前m個(gè)高頻數(shù)字：http://www.itdecent.cn/p/57918b843a2d

有bug歡迎指出