在Go语言中,是否有一种更通用的方法来实现两种堆(最大堆和最小堆)?

huangapple go评论122阅读模式
英文:

Is there a more generic way to implement 2 kinds of Heap (Max and Min) in Go Lang

问题

目前,Go语言文档中的示例代码如下:

  1. type IntHeap []int
  2. func (h IntHeap) Len() int { return len(h) }
  3. func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
  4. func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
  5. func (h *IntHeap) Push(x interface{}) {
  6. // Push and Pop use pointer receivers because they modify the slice's length,
  7. // not just its contents.
  8. *h = append(*h, x.(int))
  9. }
  10. func (h *IntHeap) Pop() interface{} {
  11. old := *h
  12. n := len(old)
  13. x := old[n-1]
  14. *h = old[0 : n-1]
  15. return x
  16. }

我真的不想重复创建一组用于最小堆的方法和另一组用于最大堆的方法。有没有更好的方法?

英文:

Currently, the example on Go lang doc is like this:

  1. type IntHeap []int
  2. func (h IntHeap) Len() int { return len(h) }
  3. func (h IntHeap) Less(i, j int) bool { return h[i] &lt; h[j] }
  4. func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
  5. func (h *IntHeap) Push(x interface{}) {
  6. // Push and Pop use pointer receivers because they modify the slice&#39;s length,
  7. // not just its contents.
  8. *h = append(*h, x.(int))
  9. }
  10. func (h *IntHeap) Pop() interface{} {
  11. old := *h
  12. n := len(old)
  13. x := old[n-1]
  14. *h = old[0 : n-1]
  15. return x
  16. }

I really don't want to repeat myself creating a set of methods for Min Heap and another set of methods for Max Heap. Is there a better way?

答案1

得分: 18

你可以使用嵌入来从你的最小堆创建一个最大堆,代码如下:

  1. type MaxHeap struct {
  2. IntHeap
  3. }
  4. func (h MaxHeap) Less(i, j int) bool { return h.IntHeap[i] > h.IntHeap[j] }

你可以在这个playground链接中找到一个可运行的示例。

英文:

You can create a max heap from your min heap using embedding, like this

  1. type MaxHeap struct {
  2. IntHeap
  3. }
  4. func (h MaxHeap) Less(i, j int) bool { return h.IntHeap[i] &gt; h.IntHeap[j] }

See the playground for a working example.

huangapple
  • 本文由 发表于 2014年5月10日 19:09:52
  • 转载请务必保留本文链接:https://go.coder-hub.com/23580285.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定