如何在 Go 中嵌入和覆盖结构

Question

我正在构造 min/max 堆整数以满足来自 container/heap 的接口。

最小堆运行良好，例如

type MinHeapInt []int

func (h MinHeapInt) Len() int {
    return len(h)
}

func (h MinHeapInt) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h MinHeapInt) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MinHeapInt) Peek() interface{} {
    return (*h)[0]
}

func (h *MinHeapInt) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeapInt) Pop() interface{} {
    length := len(*h)
    res := (*h)[length - 1]
    *h = (*h)[0 : length - 1]
    return res
}

现在我试图通过重写 Less 方法来开发最大堆。

第一个解决方案无效，因为它找不到数组

type MaxHeapInt struct {
    MinHeapInt
}

func (h MaxHeapInt) Less(i, j int) bool {
    return h[i] > h[j]
}

第二种方案只保留Less方法

type MaxHeapInt MinHeapInt

func (h MaxHeapInt) Less(i, j int) bool {
    return h[i] > h[j]
}

想知道是否有交通工具。谢谢！

Answer 1

您的第一个解决方案是尝试索引 MaxHeapInt 结构，而不是 MinHeapInt 切片。

type MaxHeapInt struct {
    MinHeapInt
}

func (h MaxHeapInt) Less(i, j int) bool {
    return h.MinHeapInt[i] > h.MinHeapInt[j]
}

如果您希望它们被相同地初始化，那么创建一个部分堆实现，并包装在所需的结构中（类似于 sort 包中的 wrapper example）。

type Max struct{ IntHeap }

func (h Max) Less(i, j int) bool {
    return h.IntHeap[i] > h.IntHeap[j]
}

type Min struct{ IntHeap }

func (h Min) Less(i, j int) bool {
    return h.IntHeap[i] < h.IntHeap[j]
}

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }

func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Peek() interface{} { return (*h)[0] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    length := len(*h)
    res := (*h)[length-1]
    *h = (*h)[0 : length-1]
    return res
}

// Now these can be initialized like
//     Min{IntHeap{1, 2, 3}}
//     Max{IntHeap{1, 2, 3}}

如何在 Go 中嵌入和覆盖结构

How to embed and override a struct in Go

heap

go

data-structures