golang实现大顶堆只看这篇文章就够了_golang 实现堆__kirakira_的博客-CSDN博客
思路
实现一个优先队列相当于维护一个小根堆,每次 pop 操作均将堆顶元素交换到堆底并返回。
Less(i, j int)如果下标 i 的元素“小于”下标 j 的元素,则返回 true,否则返回 false。返回 true 则表明 i 不会在 j 的下方。通过控制 Less 函数的返回可以实现大顶堆或者小顶堆
Push(x any)函数往IntHeap的末尾插入元素
Pop()函数取出IntHeap末尾的元素
Pop之所以这样实现,是因为在heap包的源码中,Pop在调用IntHeap的Pop之前进行了一些操作:
heap.Push函数会往堆尾插入元素,如何对这个元素进行上浮(up)操作
heap.Pop函数会先交换堆首和堆尾元素,然后再对堆首元素进行下沉(down)操作,所以我们的IntHeap类型是往堆尾插入的。
代码
堆排序
参考:堆排序