是否可以实现既是最大堆又是最小堆的二叉堆？

Question

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

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

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

我也有这个想法，但想先了解一下大家的想法。

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

Answer 1

按照 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;

Answer 2

你很接近。诀窍是使用另一个间接级别。将键保存在数组 K[i] 中，并仅将索引 i 存储在堆中。还要保留两个反向映射：一个用于最大堆，一个用于最小堆。反向映射是整数 R 的数组，使得 R[i] 是索引 i 的最小（或最大）堆中键 K[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 . The larger algorithm is for map marker merging: https://github.com/gene-ressler/lulu/wiki

Answer 3

您可以为堆元素创建一个散列table，它由两个堆共享。 table 由堆元素的值索引。哈希桶的值可以是一个struct，分别由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;

请注意，对堆的任何更改都可能会更改现有元素的基础数组索引。因此，当您 add/remove 一个元素，或交换两个元素时，您可能需要相应地更新其在哈希 table 中的数组索引。

Answer 4

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

Min-Max heap 如果最频繁的操作是findMin和findMax，我想说的是"user2357112"所指出的答案。如果我们真的不想要一个完全有序的数据结构，BST 可能有点矫枉过正，上面是一个部分有序的数据结构。参考上面发布的link。

是否可以实现既是最大堆又是最小堆的二叉堆？

Is it possible to implement a binary heap that is both a max and a min heap?

c++

algorithm

data-structures

priority-queue

binary-heap