3

我正在尝试实现一个具有最小堆和最大堆功能的二进制堆（优先级队列）。它需要有一个insert(value), extractMin(), 和一个extractMax()方法。extract 方法从堆中删除值并返回值。

我最初使用两个数组，称为minHeapand maxHeap，一个将数据存储在最小堆结构中，另一个将相同的数据存储在最大堆结构中。因此，当我调用时extractMin()，它会从 中删除并返回值minHeap。然后我也必须从中删除该值maxHeap（如果我调用 ，反之亦然extractMax()），以保持两个堆中的数据集相同。而且由于堆顺序属性，可以保证我会在另一个堆的叶子中找到该值。在另一个堆中搜索该值会导致时间复杂度为 O(n) 或更准确地说是 O(n/2)，因为我只会搜索叶子。更不用说，percolatingDown()和percolatingUp()删除值后恢复堆的方法已经是 O(log n)；所以总的来说，提取方法将是 O(n)。问题是，我需要提取方法为 O(log n)。

有没有更好的方法来解决这个问题？

我也想过这个想法，但想知道大家首先是怎么想的。

我刚刚完成了一个“中值堆”的编码，将较小的一半数据放在最大堆中，将较大的一半放在最小堆中。使用该结构，我可以轻松检索给定值集的中值。我正在考虑使用类似的结构，将较小的一半数据放在最小堆中，将较大的一半放在最大堆中，并使用所有值的平均值（而不是中位数）作为决定是否调用时将值放在最大或最小堆中insert(value)。我认为这可能会起作用，因为提取方法将保持 O(log n)。

4

4 回答 4

4

正如 M. Shaw 建议的那样，简单的方法是只使用二叉搜索树。

如果您需要在二进制堆之上构建它，那么在每个堆中，在每个元素旁边，将元素的位置存储在另一个堆中。每次在一个堆中移动一个元素时，您都可以直接转到它在另一个堆中的位置并更新它。当您执行 delete-min 或 delete-max 时，不需要在另一个堆中进行昂贵的线性扫描。

例如，如果将std::pairs存储first为元素值和second另一个堆中的位置，则交换最小堆中的两个元素同时更新最大堆中的对应元素可能如下所示：

swap(minheap[i], minheap[j]);
maxheap[minheap[i].second].second = i;
maxheap[minheap[j].second].second = j;
于 2015-07-23T03:18:01.353 回答
3

您可以为堆元素创建一个哈希表，该哈希表由两个堆共享。该表由堆元素的值索引。哈希桶的值可以是一个结构体，分别由 minHeap 和 maxHeap 中的数组索引组成。

这种方法的好处是它是非侵入式的，这意味着堆元素的结构保持不变。而且您不必并排创建堆。您可以使用通常的堆创建程序一个接一个地创建。

例如，

struct tIndex
{
   // Array index of the element in two heaps respectively
   size_t minIndex;
   size_t maxIndex;
};

std::unordered_map<int, tIndex> m;

在此处输入图像描述

请注意，对堆的任何更改都可能会更改现有元素的底层数组索引。因此，当您添加/删除一个元素或交换两个元素时，您可能需要相应地更新其在哈希表中的数组索引。

于 2015-07-23T05:33:25.420 回答
0

你很近。诀窍是使用另一个级别的间接性。将键保存在数组 K[i] 中，并仅将索引 i 存储在堆中。还要保留两张反向映射：一张用于最大堆，一张用于最小堆。反向映射是整数 R 的数组，使得 R[i] 是键 K[i] 在索引 i 的最小（或最大）堆中的位置。换句话说，如果 M[j] 是最小（或最大）堆，则 R[M[j]] = j；现在，每当您执行筛选操作以在堆中移动元素时，您必须同时更新相应的反向映射。事实上，它就像上面的关系一样工作。在更改堆元素 M[j] = z 的每一步，也更新反向映射 R[z] = j；这仅将运行时间增加了一个很小的常数因子。现在要从堆中删除 K[i]，您可以在恒定时间内找到它：它位于 M[R[i]]。

我知道这很有效（在恒定时间内找到要删除的堆对象），因为我已经将它作为更大算法的一部分来实现。查看https://github.com/gene-ressler/lulu/blob/master/ext/lulu/pq.c。较大的算法用于地图标记合并：https ://github.com/gene-ressler/lulu/wiki

于 2015-07-23T03:34:32.783 回答
0

http://www.geeksforgeeks.org/a-data-structure-question/

如果最频繁的操作是 findMin 和 findMax，我会说最小-最大堆是“user2357112”所指出的答案。如果我们真的不想要一个完全有序的数据结构，BST 可能有点过头了，上面是一个部分有序的数据结构。请参阅上面发布的链接。

于 2015-07-24T09:19:38.593 回答