go笔记--容器heap包简单使用

心已赠人 2021-12-14 03:11 371阅读 0赞

golang 容器heap接口

type Interface
    type Interface interface {
        
        sort.Interface
        Push(x interface{
        }) // 向末尾添加元素
        Pop() interface{
        }   // 从末尾删除元素
    }

任何实现了该接口的类型都可以用于构建最小堆。最小堆可以通过heap.Init建立，数据是递增顺序或者空的话也是最小堆。  
注意接口的Push和Pop方法是供heap包调用的，需使用heap.Push和heap.Pop来向一个堆添加或者删除元素。

func Init
    func Init(h Interface)

一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n)，其中n等于h.Len()。

整型堆 :

package main
    
    
    import(
    	"container/heap"
    	"fmt"
    )
    
    type IntHeap []int
    
    //Heap Interface
    //type Interface interface {
        
    //    sort.Interface
    //    Push(x interface{}) // 向末尾添加元素
    //    Pop() interface{}   // 从末尾删除元素
    //}
    
    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
    }
    
    // Sort Interface
    //type Interface interface {
        
    //    // Len方法返回集合中的元素个数
    //    Len() int
    //    // Less方法报告索引i的元素是否比索引j的元素小
    //    Less(i, j int) bool
    //   // Swap方法交换索引i和j的两个元素
    //    Swap(i, j 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 main() {
        
    	h := &IntHeap{
        5,8,1,3,4}
    	heap.Init(h)
    	heap.Push(h, 6)
    	
        fmt.Printf("minimum: %d\n", (*h)[0])
        for h.Len() > 0 {
        
            fmt.Printf("%d ", heap.Pop(h))
    	}
    	fmt.Println("")
    	//output :
    	//minimum: 1
    	//1 3 4 5 6 8 
    }