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;
}

簡単な解決策は、2 つの配列を 3 つ目の配列に結合してから 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()

しかし、一般的にサブツリーにアクセスする方法があるため、それを実装する方法がわかりません?別のバリアントは、優先キューを構築し、挿入関数を使用して、最初に1つの配列から挿入し、次に別の配列から挿入しますが、これは最適ですか?コードを書くのを手伝ってくださいこれら 2 つの最大ヒープを 1 つに効率的に結合するには

4

1 に答える 1

0

これは二項ヒープの良い例ですが、c です。二項ヒープを実装するための基本的なロジックが得られます。こちらの例を参照してください

または、ビデオ チュートリアルを入手して、アルゴリズムを理解してください。

于 2014-07-26T07:08:09.423 に答える