Go语言实现无重复Heap（优先队列）的优化方案及替代结构问询

堆中去重的检查方式优化 #

你当前的思路是在Push元素前先检查堆中是否存在该元素，但要注意：如果contains方法是通过遍历整个堆实现的，时间复杂度是O(n)，这会把堆原本O(logn)的Push操作复杂度拉低到O(n)，整体效率会下降很多。

如果严格要求不使用额外内存，那确实没有更高效的检查方式——因为堆本质是完全二叉树，元素并非全局有序，没办法用二分查找这类O(logn)的方法判断元素是否存在，只能做线性遍历检查。

要是可以放宽“不使用额外内存”的限制，更优雅高效的方案是搭配一个map来记录已存在的元素：Push前先查map，确认元素不存在后再执行堆的Push操作，同时把元素存入map；当从堆中Pop元素时，同步删除map里的对应记录。这样检查的时间复杂度是O(1)，整体Push操作仍能维持O(logn)的复杂度，只是会多占用一点内存存储map。

补全这个思路的示例代码：

import "container/heap"

type PriorityQueue struct {
    data  []int
    exist map[int]struct{} // 用空结构体占位，节省内存
}

func (pq *PriorityQueue) Push(x interface{}) {
    num := x.(int)
    if _, ok := pq.exist[num]; !ok {
        pq.data = append(pq.data, num)
        pq.exist[num] = struct{}{}
        heap.Fix(pq, len(pq.data)-1)
    }
}

// 需实现heap.Interface的其他必备方法
func (pq *PriorityQueue) Len() int { return len(pq.data) }
func (pq *PriorityQueue) Less(i, j int) bool { 
    // 按需求实现优先级逻辑，示例为小顶堆
    return pq.data[i] < pq.data[j] 
}
func (pq *PriorityQueue) Swap(i, j int) { 
    pq.data[i], pq.data[j] = pq.data[j], pq.data[i] 
}
func (pq *PriorityQueue) Pop() interface{} {
    old := pq.data
    n := len(old)
    num := old[n-1]
    pq.data = old[0 : n-1]
    delete(pq.exist, num)
    return num
}

标准库中的目标数据结构 #

Go标准库没有内置满足“有序、无重复、插入时间复杂度O(logn)”的现成数据结构。如果需要这类结构，要么自己基于container/heap和map封装（如上面的示例），要么使用第三方实现的平衡二叉搜索树（比如红黑树），但第三方库不属于标准库范畴。

内容的提问来源于stack exchange，提问作者Boris Azanov