堆排序详解：从原理到代码实现
堆排序详解：从原理到代码实现
堆排序是一种基于堆这种数据结构的排序算法。堆是一个近似完全二叉树的结构，分为大顶堆和小顶堆。堆排序的基本思想是：先将待排序的序列构建成一个堆，然后将堆顶元素与堆的最后一个元素交换，重复这个过程，直到整个序列有序。本文将详细介绍堆排序的原理和实现方法。
一、原理
堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，分为大顶堆和小顶堆。大顶堆的特点是每个节点的值都大于或等于其左右子节点的值，小顶堆则是每个节点的值都小于或等于其左右子节点的值。堆排序的基本思想是：先将待排序的序列构建成一个堆（初始建堆可以从最后一个非叶子节点开始调整，使其满足堆的性质），然后将堆顶元素（大顶堆的最大值或小顶堆的最小值）与堆的最后一个元素交换，此时最大（小）值就放到了它最终的位置。接着对剩下的n-1个元素重新调整为堆，重复这个过程，直到整个序列有序。
二、代码实现
2.1 向下调整实现
相信听着原理很懵，接下来我们来详细说一下堆排序的过程。
我们在学习堆排序之前，我们要先了解向上调整和向下调整，这里就不详细说了，可以参考相关资料。
首先我们使用多个方法联合来实现堆排序。
2.1.1 详细过程
我们来详细说一下这个过程。
我们先创建一个无序数组，实现它的堆结构，首先我们先实现上面的代码。
第一次先找到26，通过向下调整，把3换上去了。
画的不好，请见谅。
接下来就到了1的那里。发现不用换。最后就到了根节点了，发现1小，把1换上去，然后parent就到了原来1的位置，child就到了下面，发现5最小，再把5换上去。
就是这样
这样就形成了一个简单的排序，使每个堆都是一个小堆。
但是并没有完成排序呀，我们还要怎么做呢？
我们还要实现下面这个功能才能实现完整的序。这个的过程先把堆顶和堆尾的元素换一下，此时最小的那个元素就跑到了最后一个位置。
此时在这个方法里面，你传的是n-1，此时你无法再改变和访问到最后一个位置的元素了，此时最后一个位置的元素就是最小的了。
就是这样了，堆顶还是最小的元素，再交换，再调整，反复重复这个过程，最终就排好了顺序。
这样就排好了。注意我们向下调整我们开始得到的是小堆，我们反而得到了一个降序的顺序，这点要注意。得到大堆，我们就得到了升序。
2.1.2 源代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//先找最小的孩子
if (child +1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* arr, int n)
{
//根据给定的arr来进行建堆
//child:n-1 parent:(n-1-1)/2
//向下调整算法建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)//O(n)
{
AdjustDown(arr, i, n);//O(logn)
}
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
void CreateNDate()
{
int arr[]={15,1,26,5,9,6,3};
HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++){
printf("%d ",arr[i]);
}
}
int main(){
CreateNDate();
}
2.2 向上调整实现
向下调整能实现，向上调整当然也是可以实现的。
2.2.1 详细的过程
时间复杂度是o（nlogn）
还是用这棵树，首先我们还是先把它们向上调整，15没有双亲，所以先不动，再找到1，找到双亲15，然后把1换上去。
再找到26，发现不用换，再找到5，换上去，5比1小，就不用换了，最后形成这样。
就形成了一个这样的树了。
然后再通过下面的代码，实现再排序。还是和上面的向下调整一样。交换。
小堆就是降序。
2.2.2 源代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//> : 大堆
//< : 小堆
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void HeapSort(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
//堆排序
//排升序---建大堆
//排降序---建小堆*/
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
void CreateNDate()
{
int arr[]={15,1,26,5,9,6,3};
HeapSort(arr,sizeof(arr)/sizeof(arr[0]));
for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++){
printf("%d ",arr[i]);
}
}
int main(){
CreateNDate();
}
2.2.3 升序的实现
调整 AdjustUp 函数（建大堆的上浮调整）：
目的是让新插入的节点在满足大堆性质的情况下上浮到合适位置。
当前代码中比较条件是用于建小堆的（if (arr[child] < arr[parent])），要实现大堆，应将其改为 if (arr[child] > arr[parent])，即当子节点的值大于父节点的值时，进行交换并继续上浮调整。
修改后的 AdjustUp 函数如下：
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
// 改为 > 实现大堆
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
调整 AdjustDown 函数（大堆的下沉调整）：
当堆顶元素（最大值）与末尾元素交换后，需要对新的堆顶元素进行下沉调整以重新维护大堆性质。
原代码中找最小孩子的逻辑（if (child + 1 < n && arr[child] > arr[child + 1])）是用于小堆的，对于大堆应改为找最大孩子，即 if (child + 1 < n && arr[child] < arr[child + 1])，当右子节点比左子节点大时，让 child 指向右子节点。
并且后续比较交换的条件也是基于小堆的，应改为当最大孩子的值大于父节点的值时进行交换和下沉调整。
修改后的 AdjustDown 函数如下：
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
// 改为找最大孩子实现大堆
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
// 改为 > 实现大堆
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
这样就可以了。
三、结束语
感谢大家的查看，希望可以帮助到大家，做的不是太好还请见谅，其中有什么不懂的可以留言询问，我都会一一回答。 感谢大家的一键三连。