Golang中heap包源码分析

我就是我 2022-05-11 11:08 254阅读 0赞

heap的实现使用到了小根堆，下面先对堆做个简单说明

1. 堆概念

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。

最大堆和最小堆是[二叉堆][Link 1]的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者。

最小堆：根结点的键值是所有堆结点键值中最小者。

2. heap

树的最小元素在根部，为index 0.

heap包对任意实现了heap接口的类型提供堆操作。

heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。

heap需要实现的接口

// Any type that implements heap.Interface may be used as a
    // min-heap with the following invariants (established after
    // Init has been called or if the data is empty or sorted):
    //
    //	!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
    //
    // Note that Push and Pop in this interface are for package heap's
    // implementation to call. To add and remove things from the heap,
    // use heap.Push and heap.Pop.
    type Interface interface {
    	sort.Interface
    	Push(x interface{}) // add x as element Len()
    	Pop() interface{}   // remove and return element Len() - 1.
    }

// A type, typically a collection, that satisfies sort.Interface can be
    // sorted by the routines in this package. The methods require that the
    // elements of the collection be enumerated by an integer index.
    type Interface interface {
       // Len is the number of elements in the collection.
       Len() int
       // Less reports whether the element with
       // index i should sort before the element with index j.
       Less(i, j int) bool
       // Swap swaps the elements with indexes i and j.
       Swap(i, j int)
    }

其中sort.Interface用于排序，heap.Interface中Push和Pop方法分别用于插入和取出元素的操作

heap中的方法

func Fix(h Interface, i int)  　　　　　　 　　 //在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。复杂度O(log(n))，其中n等于h.Len()。
    func Init(h Interface)  　　　　　　　　　　　　 //初始化一个堆。一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n)，其中n等于h.Len()。
    func Pop(h Interface) interface{}  　　  　　 //删除并返回堆h中的最小元素（不影响约束性）。复杂度O(log(n))，其中n等于h.Len()。该函数等价于Remove(h, 0)。
    func Push(h Interface, x interface{})  　　　 //向堆h中插入元素x，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。
    func Remove(h Interface, i int) interface{}  //删除堆中的第i个元素，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。

4.示例

(1) 存储int类型元素的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{}) {
    	if v,ok := x.(int); ok {
    		*h = append(*h,v)
    	}
    }
    
    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{5,7,9,2}
    	heap.Init(h)
    	heap.Push(h,3)
    	fmt.Println((*h)[0])
    	for h.Len() > 0 {
    		fmt.Printf("%d ", heap.Pop(h))
    	}
    }
    
    运行结果：（取出的元素是从小到大）
    2
    2 3 5 7 9

(2) 实现heap的优先队列（以下代码摘自nsq）

type Item struct {
    	Value    interface{}
    	Priority int64   //优先级
    	Index    int
    }
    
    // this is a priority queue as implemented by a min heap
    // ie. the 0th element is the *lowest* value
    //PriorityQueue实现了heap接口
    type PriorityQueue []*Item
    
    func New(capacity int) PriorityQueue {
    	return make(PriorityQueue, 0, capacity)
    }
    
    /*
    Len(),Less()和Swap用于按Priority排序
    */
    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 interface{}) {
    	n := len(*pq)
    	c := cap(*pq)
    	if n+1 > c { //扩容
    		npq := make(PriorityQueue, n, c*2)
    		copy(npq, *pq)
    		*pq = npq
    	}
    
    	*pq = (*pq)[0 : n+1]
    	item := x.(*Item)
    	item.Index = n
    	(*pq)[n] = item
    }
    
    func (pq *PriorityQueue) Pop() interface{} {
    	n := len(*pq)
    	c := cap(*pq)
    	if n < (c/2) && c > 25 {//缩容
    		npq := make(PriorityQueue, n, c/2)
    		copy(npq, *pq)
    		*pq = npq
    	}
    	item := (*pq)[n-1]
    	item.Index = -1
    	*pq = (*pq)[0 : n-1]
    	return item
    }
    
    
    func main() {
    
    
    	item1 := &Item{
    		Value  : "aaaa",
    		Priority : 5,
    	}
    
    	item2 := &Item{
    		Value  : "bbbb",
    		Priority : 2,
    	}
    
    	item3 := &Item{
    		Value  : "cccc",
    		Priority : 10,
    	}
    
    	item4 := &Item{
    		Value  : "dddd",
    		Priority : 1,
    	}
    
    	pq := New(100)
    	heap.Push(&pq,item1)
    	heap.Push(&pq,item2)
    	heap.Push(&pq,item3)
    	heap.Push(&pq,item4)
    
    
    	for pq.Len() > 0 {
    		fmt.Println(heap.Pop(&pq))
    	}
    
    }
    
    
    运行结果：
    &{dddd 1 -1}
    &{bbbb 2 -1}
    &{aaaa 5 -1}
    &{cccc 10 -1}

参考地址：[https://www.cnblogs.com/davygeek/p/5916230.html][https_www.cnblogs.com_davygeek_p_5916230.html]

[Link 1]: http://baike.baidu.com/view/668854.htm
[https_www.cnblogs.com_davygeek_p_5916230.html]: https://www.cnblogs.com/davygeek/p/5916230.html