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

发布于 2024-08-21 11:53:53 字数 362 浏览 6 评论 0 原文

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

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

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

I'm looking for algorithms like ones in the stl (push_heap, pop_heap, make_heap) except with the ability to pop both the minimum and maximum value efficiently. AKA double ended priority queue. As described here.

Any clean implementation of a double ended priority queue would also be of interest as an alternative, however this question is mainly about a MinMax Heap implementation.

My google-fu has not been fruitful, but surely, it must exist?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

勿挽旧人 2024-08-28 11:53:53

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

Is there a reason you can't use std::set? It sounds like that, along with some wrappers to access and remove set::begin() and --set::end() will solve the problem. I imagine it will be difficult to find something that can generally do a MinMax Heap much faster than the default implementation of set.

巨坚强 2024-08-28 11:53:53

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

一篇似乎没有人提到的论文是 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

I can't find any good implementations, but since no one else can either I'm guessing you'll be writing your own, in which case I have a few handy references for you.

A paper that no one seems to have mentioned is the original proposition for Min-Max-Heaps:

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

I've implemented a min-max heap from this paper twice (not in C) and found it fairly trivial.

An improvement, which I haven't ever implemented, is a Min-Max-Fine-Heap. I can't find any good papers or references on a plain old fine heap, but I did find one on the min-max-fine-heap, which apparently performs better:

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

烟火散人牵绊 2024-08-28 11:53:53

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

If you're looking for the algorithm implementation try searching Github.

难得心□动 2024-08-28 11:53:53

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

snipplr 上的代码

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

Not sure if this is exactly what you're looking for, but here is a MinMax Heap i created back in my university days. This was part of a larger project so, there is an extraneous reference on a 'Stopwatch' class which measured performance. I'm not including this class as it isn't my work. It isn't hard to strip it out so i'm leaving the reference to it as it is.

The code on snipplr

To use, just create a new instance of the heap with whatever type you want to use. (Note, custom types would need to overload comparison operators). Create array of that type and then pass it to the constructor and specify the current array size and what the maximum should be. This implementation works on top of a passed array only since this is the only thing i needed, but you have everything you need to implement push and pop methods.

百合的盛世恋 2024-08-28 11:53:53

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

Sorry for lengthy code but it works fine except it may complicate to read and may contain some unnecessary variables and I am not uploading the Insert function. Use it as include .h
file.

#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;
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文