使用数组实现最小堆

Implemenation Of A Min Heap Using An Array

我正在尝试编写一个程序来使用数组表示最小堆。我知道最小堆类似于树数据结构,其中根节点小于它的子节点。这是我的代码:-

# 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

谁能帮我指出这里的错误?

您的代码给出的输出是有效输出。

现在,当您将每个元素单独添加到最小堆时,您将获得预期的输出。

在这里,您正在对整个阵列进行尝试。这就是你困惑的原因。

将每个元素单独添加到最小堆和最小堆化整个数组,是您感到困惑的两种情况。

您的程序运行正常。是你的计算出了问题。
这些步骤的简单可视化如下。

    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