c++ - 实现二叉堆

Question

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

#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()

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

Answer 1

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

或获取视频教程至here理解算法。