堆的维护时间复杂度

堆的维护时间复杂度

前言

要回答这个问题，我们首先要明确堆是什么？堆的构建过程是什么样的？堆排序是什么？再来计算它们的时间复杂度。

首先要感谢作者：呦呦鹿鸣：本文的主要内容参考自文章：图解大顶堆的构建、排序过程

什么是堆？

堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。

堆可以分为大顶堆和小顶堆。
大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

如果是排序，求升序用大顶堆，求降序用小顶堆。

一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现，
最大的 K 个：小顶堆
最小的 K 个：大顶堆

建堆分两种：自底向上建堆和自顶向下建堆。

这里有一个结论：自底向上建堆时间复杂度为：O(n);自顶向下建堆时间复杂度为：O(nlogn)。

我们这里只讨论效率高的自底向上建堆方式。

堆的构建过程：(以大顶堆自底向上为例)

大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整。

最后一个非叶子节点怎么找？这里我们用数组表示待排序序列，则最后一个非叶子结点的位置是：数组长度/2-1。假如数组长度为9，则最后一个非叶子结点位置是 9/2-1=3。

比较当前结点的值和左子树的值，如果当前节点小于左子树的值，就交换当前节点和左子树；
交换完后要检查左子树是否满足大顶堆的性质，不满足则重新调整子树结构；

再比较当前结点的值和右子树的值，如果当前节点小于右子树的值，就交换当前节点和右子树；
交换完后要检查右子树是否满足大顶堆的性质，不满足则重新调整子树结构；

无需交换调整的时候，则大顶堆构建完成。

画个图理解下，以 [3, 7, 16, 10, 21, 23] 为例：

建堆的时间复杂度

根据上面的构建过程，我们可以知道：

• 最下层的n/2个元素不需要动；

• 次下层的n/4个元素最多下沉1层；

• 倒数第三层的n/8个元素最多下沉2层；

• 倒数第四层的n/16个元素最多下沉3层；

• 以此类推，所有元素总的移动次数最多为：

  S = 0 * n / 2 + 1 * n / 4 + 2 * n / 8 + 3 * n /16 + …

这是一个等差数列与等比数列逐项相乘后求和的问题。解法为两边同乘以公比后与原式错位相减：

2S = 0 * n + 1 * n / 2 + 2 * n / 4 + 3 * n /8 + 4 * n /16 + …

2S - S = 1 * n / 2 + 1 * n / 4 + 1 * n / 8 + 1 * n /16 + …

S = n

故时间复杂度为O(n)。

堆排序过程

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，如此反复执行，便能得到一个有序序列了。

是不是对上面这一大段文字很头疼？其实排序过程用下面 4 步就能概括：

第 1 步：先 n 个元素的无序序列，构建成大顶堆
第 2 步：将根节点与最后一个元素交换位置，（将最大元素"沉"到数组末端）此时，末尾的数为最大值，剩余待排序数组个数为n-1
第 3 步：交换过后可能不再满足大顶堆的条件，所以需要将剩下的 n-1 个元素重新构建成大顶堆
第 4 步：重复第 2 步、第 3 步直到整个数组排序完成。

堆排序时间复杂度

? 推算过程：

? 1、循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn - logn ；

? 综上所述：堆排序的时间复杂度为：O(nlogn)

引用

• 图解大顶堆的构建、排序过程

• 排序算法之 堆排序 及其时间复杂度和空间复杂度