如何根据自定义类型构建堆

Question

我有一个 KeyValue 类型，如下所示：

type KeyValue struct {
    Key   string
    Value string
}

因为我想在它上面构建一个堆，所以我定义了一个 ByKey 类型并实现了 heap.Interface 接口

type ByKey []KeyValue

func (a ByKey) Len() int           { return len(a) }
func (a ByKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByKey) Less(i, j int) bool { return a[i].Key < a[j].Key }
func (a *ByKey) Push(x interface{}) {
    *a = append(*a, x.(KeyValue))
}
func (a *ByKey) Pop() interface{} {
    old := *a
    n := len(old)
    x := old[n-1]
    *a = old[0 : n-1]
    return x
}

但是当我运行进行测试时，container/heap不起作用。我的测试代码在这里：

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

heap.Init(kv1)
fmt.Printf("after heapify kv1: %v\n", *kv1)

输出为：

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}]
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() 等函数应该有问题。感谢任何帮助。

Answer 1

根据文档：

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.

尝试heap.Pop一个值：

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

{3 1}
{3 1}
{5 1}
{5 1}
{6 1}
{7 1}
{7 1}
{7 1}
{8 1}
{8 1}
{9 1}

PLAYGROUND

如何根据自定义类型构建堆

How to build heap upon custom type

heap

containers

go

data-structures