堆

1. 最小堆算法

以前也写过最小堆算法, 但是没什么印象了, 周末想重写下看看. 还是直接看代码吧.

package main

import "fmt"

type MinHeap struct {
    arrs []int
}

// 构建最小堆的时间复杂度为O(n)
func NewMinHeap(arrs []int) *MinHeap {
    mh := &MinHeap{}
    mh.arrs = make([]int, len(arrs))
    copy(mh.arrs, arrs)

    for i := len(mh.arrs)/2 - 1; i >= 0; i-- {
        mh.heapify(i)
    }
    return mh
}

func (mh *MinHeap) heapify(index int) {
    left := 2*index + 1
    right := 2*index + 2

    minIndex := index
    if left < len(mh.arrs) && mh.arrs[left] < mh.arrs[minIndex] {
        minIndex = left
    }

    if right < len(mh.arrs) && mh.arrs[right] < mh.arrs[minIndex] {
        minIndex = right
    }

    if minIndex != index {
        mh.arrs[minIndex], mh.arrs[index] = mh.arrs[index], mh.arrs[minIndex]
        mh.heapify(minIndex)
    }
}

func (mh *MinHeap) Insert(value int) {
    if mh.arrs == nil {
        mh.arrs = []int{}
    }

    mh.arrs = append(mh.arrs, value)
    i := len(mh.arrs) - 1

    for {
        parent := (i - 1) / 2
        if parent >= 0 && mh.arrs[i] < mh.arrs[parent] {
            mh.arrs[i], mh.arrs[parent] = mh.arrs[parent], mh.arrs[i]
            i = parent
        } else {
            break
        }
    }
}

// 注意sort 之后arrs元素为空. 时间复杂度为nlg(n), 这里总觉得时间复杂度为O(n), 推导类似算法导论里面的最小堆构建, 只是相比较而言会比构建多一些步骤(排序包含了构建)
func (mh *MinHeap) Sort() []int {
    ret := mh.arrs

    for len(mh.arrs) > 1 {
        mh.arrs[0], mh.arrs[len(mh.arrs)-1] = mh.arrs[len(mh.arrs)-1], mh.arrs[0]
        mh.arrs = mh.arrs[0 : len(mh.arrs)-1]
        fmt.Printf("test %#v\n", mh.arrs)
        mh.heapify(0)
    }

    mh.arrs = nil

    return ret
}

func (mh *MinHeap) ExtractMin() (int, bool) {
    if mh.arrs == nil || len(mh.arrs) == 0 {
        return 0, false
    }

    if len(mh.arrs) == 1 {
        ret := mh.arrs[0]
        mh.arrs = nil
        return ret, true
    }

    ret := mh.arrs[0]
    mh.arrs[0] = mh.arrs[len(mh.arrs)-1]
    mh.arrs = mh.arrs[0 : len(mh.arrs)-1]
    mh.heapify(0)
    return ret, true
}

func main() {
    mp := NewMinHeap([]int{100, 30, 200, 29, 70})
    mp.Insert(-3)
    mp.Insert(1000)
    /*
        for {
            value, ok := mp.ExtractMin()
            if !ok {
                break
            }
            fmt.Println(value)
        }
    */

    fmt.Println()
    ret := mp.Sort()
    fmt.Println(ret)
}

• 构建堆说明: 在构建堆的时候, 根据完全二叉树的性质, 由于叶节点没有子节点, 所以天然的满足堆的性质, 调整最小堆从len(mh.arrs)/2 - 1的位置开始.
• 时间复杂度说明: 构建堆为O(n)的时间复杂度. 堆排序为nlgn的时间复杂度.

2 堆的应用例子

2.1 维护流式数据的前K大元素.

流式数据也就是数据会源源不断的送来, 始终维护前K大的元素. 当元素数量小于K个时候,那么目前为止肯定是前K大的. 当第K+1的个元素来的时候就要判断这个新来的元素和前K的元素的大小关系了. 如果是小于所有元素就可以忽略这个元素, 如果大于前K中最小的元素, 就需要替换这个最小元素. 由这种朴素的思路可以判断我们需要维护前K元素的一个最小元素, 那么最小堆是比较合适的.

2.2 定时器

定时器可以通过最小堆维护一系列定时触发事件, 可以通过堆顶来判断有没事件触发, 如果堆顶元素都没到期, 则其它事件就不用判断了. 堆的删除和添加都在lgn时间复杂度, 效率也比较高.

2.3 排序

在上面代码里面有堆排序的例子. 相比快排来说, 我认为堆在时间复杂度上更低一些, 因为随着堆排序的进行, 树的高度是不断减小的, 所以时间上是在O(n)和O(nlgn)之间.