堆排序（c语言）

---

前言

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

---

一.什么是堆

堆它分两种结构逻辑结构和物理结构

逻辑结构是完全二叉树

物理结构是数组

堆还有两种特征

1.结构性：用数组表示的完全二叉树。

2.有序性：任一结点的根要大于或小于子节点：称为大堆小堆

通过向标建立父子节点的关系

左孩子（默认为child）

leftchild=parent*2+1
rightchild=parent*2+2
parent=(child-1)/2

二.向下调整算法

要想实现堆排序，首先必须知道什么是向下调整算法。

前提：左右子树都是小堆或者大堆

思路：从根节点开始，选出左右孩子中小的那一个，跟父亲比较，如果父亲小就交换，然后再往下调调到叶子节点结束

void AdjustDwon(int* a, int n, int root)
{int parent = root;//默认左孩子为childint child = parent * 2 + 1;//不能越界，所以要小于n，因为下标最高到n-1，随意当迟来的当n是出while语句while (child < n){//选出左右孩子中小的那一个//child + 1 < n如果出现只有左孩子没有右孩子的节点，就会存在越界现象if (child + 1 < n && a[child + 1] < a[child])child += 1;//如果小就交换，默认排升序if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//如果不存在大小交换，说明已经排完了else{break;}}

三.堆排序的创建

建堆

就是先把数组转化为堆

利用向下调整算法去建立堆

思路：叶子是不用排的，从倒数最后一个非叶子的父亲开始调

	//int i = (n - 1 - 1)父亲公式for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}

思考：排一个升序是建大堆还是小堆

如果是排小堆的化，每次从头顶拿出数据，就要打乱一个堆，又要把一个堆重新排，他的时间复杂度就为O（N*N),所以要用大堆排，第一个和最后一个交换，把它不看作堆里面的前N -1个数向下调整，选出最大的数再跟倒数第二个位置交换这样它的时间复杂度就为O（N*logN)。

void Heapsort(int* a, int n);
{//int i = (n - 1 - 1)父亲公式for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}}

四.堆的时间复杂度

---

总结

  堆是一种很好做调整的结构，在算法题里面使用频度很高。常用于想知道最大值或最小值的情况，比如优先级队列，作业调度等场景。