手撕排序之堆排序

一、概念：

什么是逻辑结构、物理结构？

逻辑结构：是我们自己想象出来的，就像内存中不存在一个真正的树

物理结构(存储结构)：实际上在内存中存储的形式。

堆的逻辑结构是一颗完全二叉树

堆的物理结构是一个数组

之前讲过二叉树可以用两种结构进行表示。

第一种就是链式结构，将一个一个结点进行链接。

第二种就是用数组表示。

数组表示意味着我们就是以数组为结构进行访问，但我们可以通过父子结点的下标关系将其看成树。

下面是孩子与结点的下标关系（需要记住！）

、

思路：

我们将数组想象成一个完全二叉树——首先第一个表示树的根，接下来两个表示根的两个孩子，数组的下面4个表示树的两个孩子的下面一层，以此类推。最后一层不满，前面的都是连续的。

但是进行了上面的步骤后，还是不能将其称为堆。

堆分为两类：

• 大顶堆（大根堆）：树中所有的父亲都大于等于孩子
• 小顶堆（小根堆）：树中所有的父亲都小于等于孩子

一道经典例题（判断一串数字是否是堆）

解题方法：

将第一个数字看作二叉树的根，再往后取两个数字当作根的左右孩子，接着再取4个数，以此类推。直至还原成一个完全二叉树，接着看是不是属于堆的两种类型，如果既不是大顶堆，也不是小顶堆，那么这一串数字就不是堆。

堆的插入：

首先堆在逻辑结构上是一颗二叉树，但逻辑结构是我们自己想象出来的，本质上数据还是存储在数组中，所以我们应该对数组进行修改。

这里的插入我们选择尾插，尾插后有一下几种情况：

1、

直接尾插，不用改变任何顺序

2、

发现尾插顺序不满足大堆或者小堆，记住插入只影响自己的祖先，与其他的祖先没有关系！

所以我们只要改变孩子与祖先的关系，如何根据孩子找到父亲的下标呢？

parent = （child-1）/ 2 即可。

将这两个位置进行交换。

3、最坏的情况

最坏情况下可能会一直到根节点

因此每次交换完，都要进行孩子与父亲的比较。

时间复杂度：

我们看最坏的情况，执行次数就是树的高度次，也就是O（logN）.

原码：

Swap(HeapDataType* a, HeapDataType* b)
{HeapDataType tmp = *a;*a = *b;*b = tmp;
}void AdujstUp(HeapDataType* a,int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}void HeapPush(HP* php,HeapDataType x)
{assert(php);//判断是否需要扩容if (php->capcity == php->size){int newCapcity = php->capcity == 0 ? 4 : php->capcity * 2;//注意realloc的使用方法HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newCapcity);if (tmp == NULL){perror(realloc);exit(-1);}php->a = tmp;php->capcity = newCapcity;}php->a[php->size] = x;php->size++;//向上调整算法，跟祖先进行比较AdujstUp(php->a, php->size-1);
}

堆的删除：

首先我们需要明确针对堆的删除，我们需要删除的是堆的根节点。

思路一（错误）

我们直接将数组的首元素删除，然后移动（memmove）后面的数据内容，但这样极大可能影响了大小堆的结构！

思路二：（向下调整算法）

我们直接将数组的首元素和数组的最后一个元素交换位置，然后size--，删除最后一个元素，也就是根节点。

这时候我们发现根节点的左右子树都是大堆/小堆

然后将根节点与左右节点的较小结点进行比较，如果还小，那么继续交换，直到叶节点为止

以此类推，堆顶的元素是最小的，继续pop，那么次小的元素又到堆顶……

原码：

void AjustDown(HeapDataType* a,int n,int parent)
{int child = parent * 2 + 1;while (child < n){//确定最小孩子if (child + 1 < n && a[child] < a[child + 1])//防止只有左叶子，访问右叶子会越界child++;if (a[parent] < a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}
}void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AjustDown(php->a,php->size,0);
}

小总结：（调整算法的前提）

向上调整算法的前提是：前面的数据内容都是大堆/小堆

向下调整算法的前提是：左右子树的数据内容都是大堆/小堆

TIP：

我们可以根据这个思路，可以实现一个排序算法，也就是堆排序。

时间复杂度：

跟插入一样，都是O（logN）。

堆排序：

1、建堆：

我们可以直接用向上寻找算法进行建堆。——为什么？

建堆有两种方式：

第一种就是向上建堆。

利用向上调整算法，每一个插入然后进行向上调整，完成建堆

时间复杂度：O(N) = N*logN

解析：

我们采取最差情况，得到O(h)的表达式，然后再用等式将h替换成n

总体的时间复杂度是O(N) = N*logN

第二种就是向下建堆。

从倒数第一个非叶子结点开始跳（也就是最后一个结点的父亲）

时间复杂度：O(N)

解析：

先假设h是树的高度，N是结点的个数

我们先用树的高度h作为自变量便于计算。最后再用等式进行替换。

考虑最坏的情况：

每层数据的个数 * 向下移动的层数

然后是等差*等比的数列求和，我们采用错位相减法计算。

最后的计算结果是2^h - 1- h.

因为2^h - 1 = n.

所以O(N) = N - log(N+1)

为什么向下调整算法要比向上调整复杂度低呢？

因为向下调整层数越低，向下调整的次数越多，所以是低*高

而向上调整层数越高，向上调整的次数就越多，所以是高*高，并且层数越高，占比越大，最后一层的结点个数就占了50%。

最后一层结点个数多并且向上调整的次数也多！

2、排序

如果我们排升序，建大堆。

排降序，建小堆。

原因：

 建小堆有可能关系全乱了，剩下数据，看成新的完全二叉树，不一定是堆，重新建堆代价太大！

例子：

建大堆：

堆顶跟最后一个位置交换，最大的数据排好了，然后将最后一个元素不列入排序，剩下元素除了根节点其余是堆。剩下的数据由堆顶元素进行向下调整算法，选出次大的，代价是logN。

注意向上调整算法和向下调整算法的前提都是保证数据是堆！

以下是建小堆的堆排序算法

所以一共的时间复杂度O(N) = N*logN.

原码：

void HeapSort(int* a, int n)
{//建堆//建小堆/大堆//向上调整建堆//O(N*logN)/*for (int i = 1; i < n; i++){AdujstUp(a, i);}*///向下调整建堆//O(N)，效率比向上调整高for (int i = (n - 1 - 1) / 2; i >= 0; i--)//注意这里的n是数据个数，而公式中的n是下标{AjustDown(a, n, i);}//根节点的值要么最大，要么最小，可以进行排序//这一部分的时间复杂度O(N) = N*logNint end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AjustDown(a, end, 0);end--;}
}