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

Question

Я пытаюсь написать программу для представления минимальной кучи с помощью массива. Я знаю, что минимальная куча похожа на древовидную структуру данных, где корневой узел меньше своих дочерних узлов. Вот мой код: -

# include <stdio.h>
# include <math.h>

int leftChild(int i)
{
    return 2 * i + 1;
}

int rightChild(int i)
{
    return 2 * i + 2;
}

void minHeap(int Arr[], int n, int i)
{
    int l, r, Least;
    l = leftChild(i);
    r = rightChild(i);
    Least = i;

    if(l < n && Arr[l] < Arr[Least])
        Least = l;

    if(r < n && Arr[r] < Arr[Least])
        Least = r;

    if(Least != i)
    {
        int Temp = Arr[i];
        Arr[i] = Arr[Least];
        Arr[Least] = Temp;
        minHeap(Arr, n, Least);
    }
}

int main(void) 
{
    int n;
    printf("\nEnter number of elements : ");
    scanf("%d", &n);

    printf("\nEnter The Elements : ");
    int Arr[n];

    for(int i = 0 ; i < n ; i++)
    {
       scanf("%d", &Arr[i]);
    }

    for(int i = n / 2 - 1 ; i >= 0 ; i--)
      minHeap(Arr, n, i);

    printf("\nMin Heap : ");

    for(int i = 0 ; i < n ; i++)
     printf("%d ", Arr[i]);
    return 0;
}


Input : 
Enter number of elements : 5
Enter the elements : 90 70 10 30 50
Output : 10 30 90 70 50 

Но, когда я пытаюсь построить кучу на бумаге, я получаю следующий вывод: -

Expected Output : 10 30 70 90 50

Может кто-нибудь указать здесь на ошибкудля меня?

Answer 1

Вывод, заданный вашим кодом, является действительным выводом.

Теперь вы получите ожидаемый результат, когда вы отдельно добавляете каждый элемент в min heap.

Здесь вы пытаетесь это сделатьна массиве в целом. Вот почему вы запутались.

Добавление каждого элемента по отдельности в min heap и min heapification массива в целом - вот два сценария, из-за которых вы запутались.

Answer 2

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

    90     heapify(Arr,1)
   /  \    swap(1,3)
 >70   10   
 / \
30  50



   >90     heapify(Arr,0)
   /  \    swap(0,2)
  30   10   
 / \
70  50



    10   
   /  \   
  30   90   
 / \
70  50

Результирующий minheap должен быть 10 30 90 70 50