如何在自定义类型上构建堆

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

}

但是当我运行测试时，容器/堆不起作用。我的测试代码在这里：

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}]

不幸的是，没有按键排序。我认为像 、 或 这样的函数中应该有问题。任何帮助是值得赞赏的。kv1Swap()Push()Pop()

Answer 1

根据文档：堆是实现优先级队列的常用方法。若要生成优先级队列，请实现 Heap 接口，其中（负）优先级作为 Less 方法的顺序，因此 Push 添加项目，而 Pop 从队列中删除优先级最高的项目。这些例子包括这样的实现;文件example_pq_test.go具有完整的源代码。尝试堆砌。弹出一个值：for kv1.Len() > 0 {&nbsp; &nbsp; 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}