Построение максимальной кучи из заданного массива с помощью Heapify - PullRequest
Новая
       81

Построение максимальной кучи из заданного массива с помощью Heapify

0 голосов
/ 27 октября 2019

Я пытаюсь рекурсивно построить максимальную кучу из заданного массива, используя метод heapify.

Вот моя рекурсивная функция: 

void MaxHeap::heapify(int lastNode){

int largest=lastNode;

for (int i = largest ; i>=0; i--) {
         int l = 2 * i + 1;
         int r = 2 * i + 2;
        if(l<size && A[l] > A[largest])
             largest = l;

        if(r<size && A[r] > A[largest])
            largest = r;

        if(A[largest] != A[lastNode]){
            cout<<"inside"<<endl;
            swap(&A[largest], &A[lastNode]);
            i = largest;
            heapify(i);
        }

    }
}

Вот мой конструктор: 

MaxHeap::MaxHeap(int inputArr[], int cap)
{
   capacity = cap;
   A = new int[capacity];
   for(int i =0; i<cap; i++){
     A[i] = inputArr[i] ;
  }
   size = capacity;

   cout<<"Size of the array"<<size<<endl;

}

Вот основная функция: 

int A[] = {2,10,20,5,8,13};
MaxHeap maxH(A, 6);
//Passing the parent of last child (n/2 - 1)
maxH.heapify(2);

Проблема

Проблема, с которой я сталкиваюсь, заключается в том, что в рекурсивном вызове значение наибольшего никогда не меняется.

Первоначальная реализация этого алгоритма заключается в следующем. Я попытался написать его, используя только один рекурсивный вызов. 

void MaxHeap::heapify(int lastNode){
    int l = 2 * lastNode + 1;
    int r = 2 * lastNode + 2;
    int largest=lastNode;

        if(l<size && A[l] > A[largest])
         largest = l;

        if(r<size && A[r] > A[largest])
        largest = r;


        if(A[largest] != A[lastNode]){
        cout<<"inside"<<endl;
        swap(&A[largest], &A[lastNode]);
        heapify(largest);
        }

}

int MaxHeap::dequeue(int n){
    int startIndex = (n/2) -1 ;
    for(int i=startIndex; i>=0; i--){
        heapify(i);
    }
}

Вопрос

Как реализовать тот же алгоритм, используя только один метод?

...