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

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

# 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

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


c arrays heap min-heap
person Neel    schedule 28.10.2019    source источник
comment
Вы можете посмотреть на эту реализацию: gist.github.com/sudhanshuptl/d86da25da46aa3d060e7be876bbdb343   -  person klutt    schedule 28.10.2019
comment
Вы всегда меняете родителя правильным потомком, так что ваша программа работает хорошо   -  person pandy giankoulidis    schedule 28.10.2019
comment
@pandygiankoulidis, так что ты предлагаешь мне сделать?   -  person Neel    schedule 28.10.2019
comment
@klutt, реализация по ссылке не помогает. Я все еще не получаю ожидаемого результата.   -  person Neel    schedule 28.10.2019
comment
Итак, что именно должен делать ваш код? Создание кучи обычно включает вставку по одной с шагом снизу вверх для каждой вставки - я этого не вижу, но я мог что-то упустить. Шаг сверху вниз обычно выполняется при удалении самого маленького элемента. Итак, я думаю, что некоторые комментарии в вашем коде относительно того, что вы делаете и почему, а также некоторые указания на то, что вы сделали на бумаге для создания кучи. FWIW ваш список статей кажется мне подходящим для вставки по одному.   -  person Euan Smith    schedule 28.10.2019
comment
Я думаю, что вы ошиблись в последнем шаге при построении кучи на бумаге: 90 заменяются на 10, а не на 30. Результат — ваш фактический результат.   -  person M Oehm    schedule 28.10.2019

Ответы (2)


arrow_upward
1
arrow_downward

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

    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

Результирующая мини-куча должна быть 10 30 90 70 50

person rsonx    schedule 28.10.2019

arrow_upward
2
arrow_downward

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

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

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

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

person Deepak Tatyaji Ahire    schedule 28.10.2019
comment
Как добавить элементы в кучу по отдельности?? - person Neel; 28.10.2019
comment
Если у вас есть размер кучи N с использованием элементов 0..N-1, обычно вы добавляете новый элемент в свой массив в N, а затем добавляете его. Куча никогда не будет взаимодействовать с элементами выше N. Если у вас уже есть массив из data, вы добавляете элемент 1 в существующую кучу из 1 элемента, затем добавляете элемент 2 в кучу из 2 элементов и так далее, пока не будет добавлен весь ваш массив, после чего ваш массив будет полностью куче. Интересное примечание. Существующий отсортированный массив является допустимой кучей, хотя, возможно, его потребуется перевернуть. - person Gem Taylor; 28.10.2019