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