How to build heap upon custom type

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

How to build heap upon custom type

问题

我有一个名为KeyValue的类型，看起来像这样：

  1. type KeyValue struct {
  2. 	Key   string
  3. 	Value string
  4. }

由于我想在其上构建一个堆，所以我定义了一个ByKey类型，并实现了heap.Interface接口：

  1. type ByKey []KeyValue
  3. func (a ByKey) Len() int           { return len(a) }
  4. func (a ByKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
  5. func (a ByKey) Less(i, j int) bool { return a[i].Key < a[j].Key }
  6. func (a *ByKey) Push(x interface{}) {
  7. 	*a = append(*a, x.(KeyValue))
  8. }
  9. func (a *ByKey) Pop() interface{} {
  10. 	old := *a
  11. 	n := len(old)
  12. 	x := old[n-1]
  13. 	*a = old[0 : n-1]
  14. 	return x
  15. }

但是当我运行测试时，容器/堆并没有起作用。我的测试代码如下：

  1. dic := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
  2. generate := func(min, max int) *ByKey {
  3. 	n := rand.Intn(max - min) + min
  4. 	kvs := make(ByKey, 0)
  5. 	for i := 0; i < n; i++ {
  6. 		idx := rand.Intn(len(dic))
  7. 		kvs = append(kvs, KeyValue{
  8. 			Key:   dic[idx],
  9. 			Value: "1",
  10. 		})
  11. 	}
  12. 	return &kvs
  13. }
  14. 	
  15. kv1 := generate(10, 15)
  16. fmt.Printf("before heapify kv1: %v\n", *kv1)
  18. heap.Init(kv1)
  19. fmt.Printf("after heapify kv1: %v\n", *kv1)

输出结果为：

  1. before heapify kv1: [{7 1} {3 1} {3 1} {5 1} {7 1} {8 1} {9 1} {5 1} {7 1} {6 1} {8 1}]
  2. after heapify kv1: [{3 1} {5 1} {3 1} {5 1} {6 1} {8 1} {9 1} {7 1} {7 1} {7 1} {8 1}]

不幸的是，kv1 没有按照键值排序。我认为在Swap()、Push() 或 Pop()等函数中可能有问题。感谢任何帮助。

英文:

I have a KeyValue type which looks like here:

  1. type KeyValue struct {
  2. 	Key   string
  3. 	Value string
  4. }

Since I want to build a heap over it, I defined a ByKey type and implements the heap.Interface interface

  1. type ByKey []KeyValue
  3. func (a ByKey) Len() int           { return len(a) }
  4. func (a ByKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
  5. func (a ByKey) Less(i, j int) bool { return a[i].Key &lt; a[j].Key }
  6. func (a *ByKey) Push(x interface{}) {
  7. 	*a = append(*a, x.(KeyValue))
  8. }
  9. func (a *ByKey) Pop() interface{} {
  10. 	old := *a
  11. 	n := len(old)
  12. 	x := old[n-1]
  13. 	*a = old[0 : n-1]
  14. 	return x
  15. }

But when I run a test, the container/heap does not work. My test code is here:

  1. dic := []string{&quot;1&quot;, &quot;2&quot;, &quot;3&quot;, &quot;4&quot;, &quot;5&quot;, &quot;6&quot;, &quot;7&quot;, &quot;8&quot;, &quot;9&quot;}
  2. generate := func(min, max int) *ByKey {
  3. 	n := rand.Intn(max - min) + min
  4. 	kvs := make(ByKey, 0)
  5. 	for i := 0; i &lt; n; i++ {
  6. 		idx := rand.Intn(len(dic))
  7. 		kvs = append(kvs, KeyValue{
  8. 			Key:   dic[idx],
  9. 			Value: &quot;1&quot;,
  10. 		})
  11. 	}
  12. 	return &amp;kvs
  13. }
  14. 	
  15. kv1 := generate(10, 15)
  16. fmt.Printf(&quot;before heapify kv1: %v\n&quot;, *kv1)
  18. heap.Init(kv1)
  19. fmt.Printf(&quot;after heapify kv1: %v\n&quot;, *kv1)

And the output is:

  1. before heapify kv1: [{7 1} {3 1} {3 1} {5 1} {7 1} {8 1} {9 1} {5 1} {7 1} {6 1} {8 1}]
  2. after heapify kv1: [{3 1} {5 1} {3 1} {5 1} {6 1} {8 1} {9 1} {7 1} {7 1} {7 1} {8 1}]

Unfortunately the kv1 is not sorted by key. I think there should be something wrong in functions like Swap(), Push() or Pop(). Any help is appreciated.

答案1

得分: 1

根据文档：

堆是实现优先队列的常见方式。要构建一个优先队列，可以使用（负的）优先级作为Less方法的排序方式来实现Heap接口，因此Push操作会向队列中添加项，而Pop操作会移除队列中优先级最高的项。示例中包含了这样的实现；文件example_pq_test.go包含了完整的源代码。

尝试使用heap.Pop弹出一个值：

  1. for kv1.Len() > 0 {
  2.     fmt.Printf("%d ", heap.Pop(kv1))
  3. }

输出结果为：

  1. {3 1}
  2. {3 1}
  3. {5 1}
  4. {5 1}
  5. {6 1}
  6. {7 1}
  7. {7 1}
  8. {7 1}
  9. {8 1}
  10. {8 1}
  11. {9 1}

PLAYGROUND

英文:

According to the docs:
> A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.

Try to heap.Pop a value:

  1. for kv1.Len() &gt; 0 {
  2.     fmt.Printf(&quot;%d &quot;, heap.Pop(kv1))
  3. }
  1. {3 1}
  2. {3 1}
  3. {5 1}
  4. {5 1}
  5. {6 1}
  6. {7 1}
  7. {7 1}
  8. {7 1}
  9. {8 1}
  10. {8 1}
  11. {9 1}

<kbd>PLAYGROUND</kbd>

huangapple
  • 本文由 发表于 2021年6月8日 23:18:04
  • 转载请务必保留本文链接：https://go.coder-hub.com/67889888.html
  • containers
  • data-structures
  • go
  • heap
匿名

发表评论

匿名网友

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

确定