英文:
Heap (Priority queue) without duplicates in Golang
问题
我发现标准库中的heap包包含了一个默认情况下可以包含重复元素的堆接口。
但是如果我不想在我的堆中存储重复元素怎么办？如何在不使用额外内存的情况下处理这种情况？
我只找到一种方法，在推入元素之前检查堆是否包含该元素：
import "container/heap"
type PriorityQueue []int
func (pq *PriorityQueue) Push(x interface{}) {
if !pq.contains(x) {
*pq = append(*pq, x.(int)))
}
}
func (pq *PriorityQueue) contains(x interface{}) bool {
// 一些检查包含函数
}
有没有更优雅的方法来检查呢？或者有没有其他数据结构（在标准库中）可以按顺序存储元素且不包含重复元素，并且在*O(log n)*时间内添加新元素？
英文:
I found that std lib package heap contains interface for heap which could contains duplicates by default.
But what if I don't want to store duplicates in my heap? How can I handle this situation without using extra-memory?
Only one way I found is to check is heap contains element before pushing:
import "container/heap"
type PriorityQueue []int
func (pq *PriorityQueue) Push(x interface{}) {
if !pq.contains(x) {
*pq = append(*pq, x.(int)))
}
}
func (pq *PriorityQueue) contains(x interface{}) bool {
// some checking contains func
}
Is any way to check it more elegant? Or other data structure (in std lib) with ordered elements and without duplicates with adding new element for O log n?
答案1
得分: 2
我不使用golang，所以无法给出代码实现，但是我可以用口头描述几种可能的解决方案。
二叉堆不会阻止重复值的出现，并且由于内部排序只是部分有序，它们可以位于完全不同的子树中，即不相邻。然而，一旦其中一个重复值上浮到根位置，重复值将会相邻。因此，你可以编写一个包装函数来弹出值，该函数执行以下操作：
- 从堆中弹出一个值
- 查看新的根节点
- 如果它与第一个弹出的项匹配，则弹出并丢弃它，然后重复步骤2
- 否则，返回弹出的值
换句话说，在检索时丢弃重复值，每个重复值的成本为O(log n)，而不是在插入时丢弃。如果重复值相对稀疏，这种方法将非常高效。
如果每个值平均有两个或更多的重复出现，最好在堆中保留一个值的哈希表。在插入之前，检查哈希表是否已经存在该值，如果是，则丢弃它。在弹出时，删除哈希表中对应的条目。相对于维护一个数据结构，这将使存储需求增加一倍，但由于哈希操作的O(1)复杂度，额外的计算要求可以忽略不计。
英文:
I don't use golang, so I can't give a code implementation, but here's a verbal description of a couple of possible solutions.
Binary heaps do not prevent duplicates, and since the internal ordering is only partially ordered they can be in completely different subtrees, i.e., not adjacent. However, duplicates will be adjacent once one of them percolates up to the root position. Consequently, you could write a wrapper function for popping values which does the following operations:
- Pop a value off the heap
- Peek at the new root
- If it matches the first popped item, pop and discard it, then repeat step 2
- Otherwise, return the popped value
In other words, throw away duplicates at retrieval time at a cost of O(log n) per duplicate, rather than at insertion time. If duplicates are relatively sparse, this would be fairly efficient.
If each value has two or more duplicate occurrences on average, you'd do better to keep a hash table of values in the heap. Before inserting, check the hash table to see if a value is already there and discard it if so. On popping, delete the corresponding entry in the hash table. This doubles the storage requirements relative to maintaining one data structure, but the additional computational requirements are negligible due to the O(1) complexity of hash operations.
答案2
得分: -1
Golang没有集合（sets）的概念。但是你可以使用 map 来代替切片（slice）。
类似这样：
type PriorityQueue map[int]bool
func (pq *PriorityQueue) Push(x int) {
if !pq[x] {
pq[x] = true
}
}
英文:
Golang doesn't have sets. But you could use a map in stead of a slice.
Something like:
type PriorityQueue map[int]bool
func (pq *PriorityQueue) Push(x int) {
if !pq[x] {
pq[x] = true
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论