有没有 C++最小最大堆实现？

Question

我正在寻找类似于 stl 中的算法（push_heap、pop_heap、make_heap），除了能够弹出最小值和最大值有效地实现价值。又称双端优先级队列。如此处所述。

作为替代方案，双端优先级队列的任何干净实现也将引起人们的兴趣，但是这个问题主要是关于 MinMax Heap 实现。

我的 google-fu 尚未取得成果，但它肯定存在吗？

Answer 1

您是否有无法使用 std::set 的原因？听起来，加上一些访问和删除 set::begin() 和 --set::end() 的包装器将解决问题。我想很难找到比 set 的默认实现更快地完成 MinMax Heap 的东西。

Answer 2

我找不到任何好的实现，但由于没有其他人可以，我猜您会编写自己的实现，在这种情况下，我为您提供了一些方便的参考。

一篇似乎没有人提到的论文是 Min-Max-Heaps 的原始命题：

http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf

我已经从这篇论文中实现了两次最小-最大堆（不是 C 语言）并且发现它相当微不足道。

我从未实施过的一项改进是最小-最大-精细堆。我在普通的旧细堆上找不到任何好的论文或参考文献，但我确实在 min-max-fine-heap 上找到了一篇，它显然表现更好：

http://arxiv.org/ftp/cs/papers/0007/0007043.pdf

Answer 3

如果您正在寻找算法实现，请尝试搜索 Github 。

Answer 4

不确定这是否正是您正在寻找的，但这是我在大学时代创建的 MinMax 堆。这是一个更大项目的一部分，因此，在测量性能的“秒表”类上有一个无关的参考。我不包括这门课，因为这不是我的工作。删除它并不难，所以我保留对它的引用不变。

snipplr 上的代码

要使用，只需使用任何内容创建一个新的堆实例您要使用的类型。 （注意，自定义类型需要重载比较运算符）。创建该类型的数组，然后将其传递给构造函数并指定当前数组大小和最大值。此实现仅在传递的数组之上工作，因为这是我唯一需要的东西，但您拥有实现推送和弹出方法所需的一切。

Answer 5

抱歉，代码很长，但它工作正常，只是它可能会使阅读变得复杂，并且可能包含一些不必要的变量，而且我没有上传插入函数。将其用作包含 .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;
}