Python - 哈希堆实现

Question

Python - 哈希堆实现

3

我有一组流数据，我将它们一个接一个地推入堆（优先队列）中进行维护，最终的堆看起来像：

[(a,1), (b,2), (c, 7), (d, 2), ...]

因为我需要不断更新项目（例如将(a,1)更改为(a,2)，或者删除(c,7)）以便随时有效地查找和删除堆中的项，因此我希望使用哈希表构建一个存储堆中每个项位置的哈希表。

这样，每次我想要更新一个项目时，我可以使用哈希表轻松地在堆中找到它并进行更改，同时更新哈希表中每个项目的位置。

相同的问题已在此帖子中提出：如何在哈希表上实现O(1)的最小堆删除，C++代码如下：

template<typename state, typename CmpKey, class dataStructure>
bool AStarOpenClosed<state, CmpKey, dataStructure>::HeapifyUp(unsigned int index)
{
        if (index == 0) return false;
        int parent = (index-1)/2;
        CmpKey compare;

        if (compare(elements[theHeap[parent]], elements[theHeap[index]]))
        {
                // Perform normal heap operations
                unsigned int tmp = theHeap[parent];
                theHeap[parent] = theHeap[index];
                theHeap[index] = tmp;
                // Update the element location in the hash table
                elements[theHeap[parent]].openLocation = parent;
                elements[theHeap[index]].openLocation = index;
                HeapifyUp(parent);
                return true;
        }
        return false;
}

我对c++的经验很少，想知道有没有人可以帮我解释这个思路或者提供一个python版本的代码实现？

- enaJ

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Leon · Accepted Answer

据我所知，您的一对中的第一个项目作为键，第二个项目作为数据有效负载。然后，我建议采用另一种方法，有些类似于此答案，但更简单。

让哈希表成为主要的数据存储结构，让最小堆成为辅助数据结构以维护数据集中当前最小的键。
插入新项：将数据添加到哈希表和最小堆中。
更新给定键的值：仅在哈希表中更新值。
删除具有给定键的项：仅从哈希表中删除具有给定键的条目。
访问最小键：如果堆顶上的元素未在哈希表中找到，则放弃它；重复这个过程，直到顶部的键存在于哈希表中。