Почему этот код корректен, хотя он должен явно попадать в бесконечный цикл? - PullRequest
Новая
       35

Почему этот код корректен, хотя он должен явно попадать в бесконечный цикл?

0 голосов
/ 09 июля 2019

У меня некоторое время была проблема с этим кодом. Размещение рекурсивного вызова функции не кажется правильным.

Я попытался запустить код, и да, он действительно запустил бесконечный цикл. 

// I DEFINE HEAP STRUCTURE AS :
struct heap_array
{
  int *array;  // heap implementation using arrays(note : heap is atype of a tree).

  int capacity;  // how much the heap can hold.
  int size;   //how much size is currently occupied.

void MaxHeapify(struct heap_array *h,int loc)  // note : loc is the location of element to be PERCOLATED DOWN.
{
  int left,right,max_loc=loc;
  left=left_loc_child(h,loc);
  right=right_loc_child(h,loc);

  if(left !=-1 && h->array[left]>h->array[loc])
  {
    max_loc=left;
  }

  if(right!=-1 && h->array[right]>h->array[max_loc])
  {
    max_loc=right;
  }

  if(max_loc!=loc)  //i.e. if changes were made:
  {
    //swap the element at max_loc and loc
    int temp=h->array[max_loc];
    h->array[max_loc]=h->array[loc];
    h->array[loc]=temp;


  }
    MaxHeapify(h,max_loc); // <-- i feel that this recursive call is misplaced. I have seen the exact same code in almost all the online videos and some books i referred to. ALSO I THINK THAT THE CALL SHOULD BE MADE WITHIN THE SCOPE OF condition if(max_loc!=loc).
    //if no changes made, end the func right there.
}

1 Ответ

0 голосов
/ 09 июля 2019

В вашей текущей реализации похоже, что у вас нет базового сценария для остановки рекурсии.

Помните, что вам нужен базовый случай в рекурсивной функции (в данном случае, ваша MaxHeapify функция), и она не выглядит таковой.

Вот пример MaxHeap , который может быть изобретательным, чтобы посмотреть 

// A recursive function to max heapify the given 
    // subtree. This function assumes that the left and 
    // right subtrees are already heapified, we only need 
    // to fix the root. 
    private void maxHeapify(int pos) 
    { 
        if (isLeaf(pos)) 
            return; 

        if (Heap[pos] < Heap[leftChild(pos)] ||  
            Heap[pos] < Heap[rightChild(pos)]) { 

            if (Heap[leftChild(pos)] > Heap[rightChild(pos)]) { 
                swap(pos, leftChild(pos)); 
                maxHeapify(leftChild(pos)); 
            } 
            else { 
                swap(pos, rightChild(pos)); 
                maxHeapify(rightChild(pos)); 
            } 
        } 
    }

Здесь вы можете увидеть нижний регистр: 

    if (isLeaf(pos)) 
        return;

Вам необходимо добавить базовый регистр в рекурсивную функцию.

...