Реализация биноминальной кучи

Моя цель — построить биноминальную кучу. Вот мой код, который я написал прямо сейчас:

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

но я не знаю, как реализовать это, потому что в целом, как получить доступ к поддеревьям? другой вариант — построить очередь приоритетов и с помощью функции вставки вставить сначала из одного массива, а затем из другого массива, но это оптимально? пожалуйста, помогите мне написать код эффективно объединить эти две максимальные кучи в одну

1

Решение

Это хороший пример биномиальной кучи, но это в c. Вы получите базовую логику для реализации биномиальной кучи. См пример Вот

Или получите видеоурок к Вот понять алгоритм.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]