时间戳

首页 > 解决方案 > 使用数组实现最小堆

c - 使用数组实现最小堆

问题描述

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

# 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

有人可以在这里为我指出错误吗？

标签： carraysheapmin-heap

解决方案

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

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

在这里，您将在整个阵列上进行尝试。这就是你感到困惑的原因。

将每个元素单独添加到最小堆和最小堆作为一个整体，是您感到困惑的两种情况。

推荐阅读