这里先贴一道题,最小的k个数,用大顶堆解决的一道题
go中的heap使用起来只需要实现几个方法,具体有以下几种:
type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
//sort.Interface
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
我们可以看到,我们只需要实现5个方法,Len() ,Less() ,Swap() ,Push() ,Pop(),
纯讲理论是很无聊的,先放一段示例代码(对应上面那道题):
type MyHeap []int
func (h MyHeap)Less(i,j int)bool{
return h[i]>h[j]
}
func (h MyHeap)Len()int{
return len(h)
}
func (h MyHeap)Swap(i,j int){
h[i],h[j]=h[j],h[i]
}
func (h *MyHeap)Push(x interface{}){
*h=append(*h,x.(int))
}
func (h *MyHeap)Pop()interface{}{
p:=(*h)[len(*h)-1]
*h=(*h)[:len(*h)-1]
return p
}
//非必要
func (h MyHeap)Peek()int{
return h[0]
}
Less()方法定义了一种比较模式,众所周知,堆有大顶堆和小顶堆两种,Less 方法接收两个参数,分别是 heap 中的两个元素的下标。如果第一个元素比第二个元素小,则返回 true,否则返回 false。(这种是小顶堆的构造模式,大顶堆则相反,和示例代码一致)
Push()方法和Pop()方法实现时需要通过指针调用,其实切片是一个引用类型,在方法中进行修改时,修改能有效的反馈到原来的切片中(如何这样考虑,我们并不需要通过指针来调用)。
但是我们需要考虑到一个问题,一旦切片增加元素或者删除元素时触发了切片的扩容或者缩容,这时切片的内存将会重新分配,原来的切片将不能感知到最新的变化,因为最新的变化产生在新分配的内存上。这时为了避免这种情况的发生,我们需要传入切片的指针,对指针进行解引用修改切片的内容。
至于剩下的方法,我们可以发现不涉及到内存的重新分配,当然就可以直接使用切片本身进行调用。