首先需要知道的是,如果想要对一个数组排升序,要建大堆,排降序,要建小堆。
具体过程:(以排降序为例)
1)建小堆;
2)交换堆顶(第一个)和堆尾(最后一个)的数据;
3)交换完后,最后一个数据不动,剩下的数据对堆顶元素进行向下调整;
4)循环2)3)步骤。
下面用图来展示一下过程:
1)假设对数组arr[10] = {3,1,5,23,64,7,45,37,9,23}进行排序,建好的小堆如图:
2)交换堆顶和堆尾的数据,
3)对64进行向下调整,进行向下调整时,不将堆尾的1算入数组,那么就是对下图进行调整:
因为只换了堆顶和堆尾,堆顶的左右子树仍然是小堆,所以可以直接对堆顶调整:
这里的黄色框内表示没有参与调整。
继续交换:
交换完继续对堆顶调整,调整时对下图框外数据调整:
以此循环进行,最终实现排序。
部分流程图如下:
最终得到:
以数组形式来看就是{64,45,37,23,23,9,7,5,3,1};实现了降序。
参考代码如下:
void AdjustDown(int* a, int k, int parent)
{
int child = 2 * parent + 1;
while (child < k)
{
//找左右孩子小的那一个
if (child + 1 < k && a[child + 1] < a[child])
child++;
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int main()
{
int arr[10] = {3,1,5,23,64,7,45,37,9,23};
int k = sizeof(arr)/sizeof(arr[0]);
int i = 0;
for (i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr,k,i);
}
int end = n - 1;
while(end > 0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
end--;
}
}
标签:arr,end,parent,23,实现,堆排序,int,child From: https://blog.csdn.net/guaiguaiyalj/article/details/140417501