1

我的目标是构建一个二项式堆。这是我现在编写的代码：

#include<iostream>
using namespace std;
void maxheapify(int a[],int length,int i)
{
    int left=2*i;
    int right=2*i+1;
    int largest=i;
    if(left<length && a[left]>a[largest])
    {
        largest=left;

    }
    if ( right<length && a[right]>a[largest])
    {
        largest=right;
    }

    if(largest!=i)
    {
int temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheapify(a,length,largest);

    }

}
void buildmax(int a[],int length)
{
    for(int i=(length-1)/2;i>=0;i--)
    {
        maxheapify(a,length,i);

    }


}
/*void heapsort(int a[],int length)
{
    buildmax(a,length);
    for(int i=length-1;i>0;i--)
    {
        int temp=a[i];
        a[i]=a[0];
        a[0]=temp;
        maxheapify(a,i,0);


    }


}
*/
 void combine_heap(int a[],int n,int b[],int m,int c[])
 {

 }
int main()
{
    int a[100];
    int n=sizeof(a)/sizeof(a[0]);

    int b[100];
    int m=sizeof(b)/sizeof(b[0]);
    int c[200];
    int length=sizeof(a)/sizeof(a[0]);
    for(int i=0;i<length;i++){
        a[i]=34+rand()%(length-33);
         b[i]=rand()%(i+1);
            }
    /*heapsort(a,length);*/
    /*for(int i=0;i<length;i++)
        cout<<a[i]<<"  ";*/


    return 0;
}

我认为简单的解决方案是将两个数组组合成第三个数组，然后调用 buildmax 程序，但我认为它效率不高，我试图从维基百科实现这个伪代码

function merge(p, q)
    while not( p.end() and q.end() )
        tree = mergeTree(p.currentTree(), q.currentTree())
        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())
            heap.addTree(tree)
        else
            heap.addTree(tree)
        heap.next() p.next() q.next()

但我不知道如何实现它，因为通常如何访问子树？另一种变体是构造优先级队列并使用插入函数先从一个数组插入，然后从另一个数组插入，但这是最优的吗？请帮我写代码有效地将这两个最大堆合并为一个

4

1 回答 1

0

这是二项式堆的一个很好的例子，但它是在 c 中的。您将获得实现二项式堆的基本逻辑。请参阅此处的示例

或在此处获取视频教程以了解算法。

于 2014-07-26T07:08:09.423 回答