Go语言实现大顶堆

Go语言的OOP,接口,接口的组合,基础库的函数及接口如何抽象设计,

这些东西在Go的Heap源码及演示例子处理中,都有很好的展示.

在"container/heap"中,它的接口是如下定义的:

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

从堆中Pop()后,数据就被从heap中移除了

升降序由Less()来决定

自定义类也可以直接用Sort来排序,因为实现了相关接口.

下面是使用container/heap包实现的int类型的大顶堆

package main

import (
   "container/heap"
   "fmt"
)

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[:n-1]
   return x
}

func main() {
   h := &IntHeap{100,16,4,8,70,2,36,22,5,12}

   fmt.Println("\nHeap:")
   heap.Init(h)

   fmt.Printf("最大值: %d\n", (*h)[0])

   //for(Pop)依次输出最小值,则相当于执行了HeapSort
   fmt.Println("\nHeap sort:")
   for h.Len() > 0 {
      fmt.Printf("%d ", heap.Pop(h))
   }
}

我们可以看到一个类型使用内置的堆就要实现Len(),Less(),Swap(),Pop(),Push()这五个方法

通过此示例之后发现,container/heap  仅且只是封装了一个堆而已. 把那些不确定的,各种需要定制的东西,都交给了用户去实现.它仅仅只负责最核心的堆这部份的东西