我正在寻找类似 stl ( push_heap, pop_heap, make_heap) 中的算法，除了能够有效地弹出最小值和最大值。AKA 双端优先级队列。如此处所述。
双端优先级队列的任何干净实现也将作为替代方案感兴趣，但是这个问题主要是关于 MinMax Heap 实现。
我的 google-fu 没有结果，但它肯定存在吗？
问问题
10678 次
5 回答
7
你有没有理由不能使用std::set？听起来像这样，以及一些用于访问和删除的包装器set::begin()，--set::end()将解决问题。我想很难找到通常可以比 set 的默认实现更快地执行 MinMax Heap 的东西。
于 2010-02-12T18:22:27.630 回答
4
我找不到任何好的实现，但是由于没有其他人可以，我猜你会自己写，在这种情况下，我有一些方便的参考资料供你参考。
一篇似乎没人提到的论文是 Min-Max-Heaps 的原始命题：
http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf
我已经两次（不是在 C 中）从这篇论文中实现了一个 min-max 堆，并且发现它相当微不足道。
我从未实施过的改进是 Min-Max-Fine-Heap。我在普通的旧精细堆上找不到任何好的论文或参考资料，但我确实在 min-max-fine-heap 上找到了一篇，它显然性能更好：
于 2010-02-17T00:14:14.730 回答
2
如果您正在寻找算法实现，请尝试搜索Github。
于 2010-02-17T08:22:14.323 回答
0
不确定这是否正是您要寻找的，但这是我在大学时代创建的 MinMax Heap。这是一个更大项目的一部分，因此在衡量性能的“秒表”类上有一个无关的参考。我不包括这门课，因为它不是我的工作。剥离它并不难，所以我保留对它的引用。
snipplr上的代码
要使用，只需使用您想要使用的任何类型创建一个新的堆实例。（注意，自定义类型需要重载比较运算符）。创建该类型的数组，然后将其传递给构造函数并指定当前数组大小和最大值。此实现仅在传递的数组之上工作，因为这是我唯一需要的，但您拥有实现推送和弹出方法所需的一切。
于 2010-02-21T18:07:40.430 回答
-2
很抱歉代码冗长，但它工作正常，除了它可能会使阅读变得复杂并且可能包含一些不必要的变量，而且我没有上传插入函数。将其用作包含 .h 文件。
#include <math.h>
#define bool int
#define true 1
#define false 0
#define Left(i) (2 * (i))
#define Right(i) (2 * (i) + 1)
#define Parent(i) ((i) / 2)
void TrickleDown(int* A, int n)
{
int i;
for (i = 1; i <= n / 2; i++)
{
if (isMinLevel(i, n) == true)
TrickleDownMin(A, i, n);
else
TrickleDownMax(A, i, n);
Print(A, n);
printf("i = %d\n", i);
}
}
int isMinLevel(int i, int n)//i is on min level or not
{
int h = 2;
if (i == 1)
return true;
while (true)
{
if (i >= pow(2, h) && i <= pow(2, h + 1) - 1)
return true;
else if (i > n || i < pow(2, h))
return false;
h += 2;
}
}
void swap(int* a, int* b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
void TrickleDownMin(int* A, int i, int n)
{
int m, lc, rc, mc, lclc, lcrc, mlc, rclc, rcrc, mrc;
int child;
lc = Left(i);
if (lc > n) // A[i] has no children
return;
else
{
rc = Right(i);
mc = rc > n ? lc : (A[lc] > A[rc]) ? rc : lc;
child = true; // keep tracking m comes from children or grandchildren
// m = smallest of children and grand children
lclc = Left(lc);
if (lclc <= n)
{
lcrc = Right(lc);
mlc = lcrc > n ? lclc :(A[lclc] > A[lcrc]) ? lcrc : lclc;
mc = mlc > mc ? mc : mlc;
if (mc == mlc)
child = false;
}
rclc = Left(rc);
if (rclc <= n)
{
rcrc = Right(rc);
mrc = rcrc > n ? rclc : (A[rclc] > A[rcrc]) ? rcrc : rclc;
mc = mrc > mc ? mc : mrc;
if (mc == mrc)
child = false;
}
m = mc;
if (!child)//m is one of the child of i
{
if (A[m] < A[i])
{
swap(&A[m], &A[i]);
if (A[m] > A[Parent(m)])
swap(&A[m], &A[Parent(m)]);
TrickleDownMin(A, i, m);
}
}
else //m is child of i
{
if (A[m] < A[i])
swap(&A[i], &A[m]);
}
}
}
void TrickleDownMax(int* A, int i, int n)
{
int m, lc, rc, mc, lclc, lcrc, mlc, rclc, rcrc, mrc;
int child;
lc = Left(i);
if (lc > n)//A[i] has no children
return;
else
{
rc = Right(i);
mc = rc > n ? lc : (A[lc] < A[rc]) ? rc : lc;
child = true; //keep tracking m comes from choldren or grandchildren
//m = greatest of children and grand children
lclc = Left(lc);
if (lclc <= n)
{
lcrc = Right(lc);
mlc = lcrc < n ? lclc : (A[lclc] < A[lcrc]) ? lcrc : lclc;
mc = mlc < mc ? mc : mlc;
if (mc == mlc)
child = false;
}
rclc = Left(rc);
if (rclc <= n)
{
rcrc = Right(rc);
mrc = rcrc < n ? rclc : (A[rclc] < A[rcrc]) ? rcrc : rclc;
mc = mrc < mc ? mc : mrc;
if (mc == mrc)
child = false;
}
m = mc;
if (!child)//m is one of the child of i
{
if (A[m] > A[i])
{
swap(&A[m], &A[i]);
if (A[m] < A[Parent(m)])
swap(&A[m], &A[Parent(m)]);
TrickleDownMax(A, i, m);
}
}
else //m is child of i
{
if (A[m] > A[i])
swap(&A[i], &A[m]);
}
}
}
void Print(int* a, int n)
{
int i;
for (i = 1; i < n + 1; i++)
{
printf("%d ", a[i]);
}
}
int DeleteMin(int* A, int n)
{
int min_index = 1;
int min = A[1];
swap(&A[min_index], &A[n]);
n--;
TrickleDown(A, n);
return min;
}
int DeleteMax(int* A, int n)
{
int max_index, max;
max_index = n < 3 ? 2 : (A[2] > A[3]) ? 2 : 3;
max = A[max_index];
swap(&A[max_index], &A[n]);
n--;
TrickleDown(A, n);
return max;
}
于 2013-06-23T07:55:30.607 回答