堆的维护时间复杂度

2024-01-02 06:16:38

堆的维护时间复杂度

前言

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

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

什么是堆?

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

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

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

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

建堆分两种:自底向上建堆自顶向下建堆

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

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

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

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

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

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

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

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

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

953680-20200531004135177-1000133948

建堆的时间复杂度

根据上面的构建过程,我们可以知道:

  • 最下层的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 步直到整个数组排序完成。

953680-20200531013230974-864063180

堆排序时间复杂度

? 推算过程:

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

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

引用

文章来源:https://blog.csdn.net/guigenyi/article/details/135330621
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。