大顶堆排序图解,大顶堆排序图解大全

用一组｛14，15，30，28，5，10｝关键字序列，写出初始建堆过程图示，再根据初始堆写出堆排序过程图示。

起始序列为14，15，30，28，5，10，

(1)因此起始堆的情况如下：

14

15 30

28 5 10

(2)假设是打算得到一个从小到大的c，所以需要建大顶堆，起始状态从下向上建堆：

第一步： 第二步：

14 30

28 30 28 14

25 5 10 25 5 10

(3)此时已经建立完了初始的堆。此时堆顶元素30即为最大元素，将堆顶元素与堆最后

一个元素进行交换，此时30是最大元素位于队尾，因此无需继续排序。所以堆如下图

所示：10 28 14 25 5

(4)此时由于除被交换到堆顶的10以外其他的都基本有序，所以自上而下建堆得到的堆

如下：

28

25 14

10 5

(5)重复（3）和（4）步骤确定了28的位置并得到堆如下：

25

10 14

5

(6)重复（3）和（4）步骤确定了25的位置并得到堆如下：

14

10 5

(7)重复（3）和（4）步骤确定了14的位置并得到堆如下：

10

5

(8)重复（3）和（4）步骤确定了10的位置,此时只有一个数5也位于了堆的第一个位置，

因此排序完成。

扩展资料：

建堆效率

n个结点的堆，高度d =log2n。根为第0层，则第i层结点个数为2^i，考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1，不移动（叶）。四分之一的结点深度为d-2，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一。

这种算法时间代价为Ο（n)

由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是

Ο（log n）。

操作实现

在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：

1.事先不知道程序所需对象的数量和大小。

2.对象太大，不适合使用堆栈分配器。

堆使用运行期间分配给代码和堆栈以外的部分内存。

传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。

语言运行时库也可在一个进程内创建单独的堆。（例如，C 运行时库创建自己的堆。）除这些专用堆外，应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的?API用于创建和使用专用堆。有关堆函数的优秀教程，请参阅 MSDN 平台 SDK 节点。

参考资料来源：百度百科-堆

8.堆排序

1)堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

2)堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。

3)每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

4)大顶堆举例说明

堆排序的基本思想是：

1)将待排序序列构造成一个大顶堆

2)此时，整个序列的最大值就是堆顶的根节点，将其与末尾元素进行交换，此时末尾就为最大值。

3)然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

3.堆排序步骤图解说明:

针对无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }：

谈谈堆排序，大顶堆，小顶堆？

堆是一种非线性结构， 可以 把堆看作一个数组， 也可以 被看作一个完全二叉树，通俗来讲堆其实就是 利用完全二叉树的结构来维护的一维数组 但堆并不一定是完全二叉树

按照堆的特点可以把堆分为大顶堆和小顶堆

大顶堆：每个结点的值都大于或等于其左右孩子结点的值

小顶堆：每个结点的值都小于或等于其左右孩子结点的值

如果仅仅是需要得到一个有序的序列，使用排序就可以很快完成，并不需要去组织一个新的数据结构。但是如果我们的需求是对于一个随时会有更新的序列，我要随时知道这个序列的最小值或最大值是什么。显然如果是线性结构，每次插入之后，假设原数组是有序的，那使用二分把它放在正确的位置也未尝不可，但是插入的时候从数组中留出空位就需要O(n)的时间复杂度，删除的时候亦然。

可是如果我们将序列看作是一个集合，我们需要的是这个集合的一个最小值或者最大值，并且，在它被任意划分成为若干个子集的时候，这些子集的最小值或者最大值我们也是知道的，这些子集被不断划分，我们依然知道这些再次被划分出来的子集的最小值或者最大值。而且我们去想办法去保持这样的一个性质，那么这个问题是不是变得非常好解决了呢？那么问题就转换成了一种集合之间的关系，并且是非常明显的一种包含关系，那么最适合于解决这种集合上的关系的数据结构是什么呢？那么就是树，所以就形成了这样的一种树，他的每一个节点都比它的子节点们小或者大。 当我们插入一个新的节点的时候，实际上我们需要去调整的大部分时候只是这棵树上的一条路径，也就是决定它在哪一个集合里面，树上的路径长度相对于这个集合，由于是对数级别的，所以非常可以接受，那么这种数据结构也就应运而生，而这个数据结构为什么叫做堆，那就不知道了。

内存占用：

普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额外的内存。 堆仅仅使用数组，且不使用指针

平衡：

二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到 O(nlog2n) 。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证 O(nlog2n) 的性能

搜索：

在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为 使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作

堆排序的基本思想 假设是构建大顶堆

1.给一个无序序列如下

int a[6] = {7, 3, 8, 5, 1, 2}

2.根据数组将完全二叉树还原出来

3.为什么升序要用大顶堆呢

大顶堆的特点：每个结点的值都大于或等于其左右孩子结点的值，我们把大顶堆构建完毕后根节点的值一定是最大的，然后 把根节点和最后一个元素（也可以说最后一个节点）交换位置 ，那么末尾元素此时就是最大元素了

4.图解交换过程

先要找到最后一个非叶子节点，数组的长度为6，那么最后一个非叶子节点就是： 长度/2-1 ，也就是 6/2-1=2 ，然后下一步就是比较该节点值和它的子树值，如果该节点小于其左\右子树的值就交换（意思就是将最大的值放到该节点）

8只有一个左子树，左子树的值为2，82不需要调整

到这里大顶堆的构建就算完成了

然后下一步交换根节点 8 与最后一个元素 2 交换位置（将最大元素"沉"到数组末端），此时最大的元素就归位了，然后对剩下的5个元素重复上面的操作

这里用紫色来表示已经归位的元素

剩下只有5个元素，最后一个非叶子节点是 5/2-1=1 ，该节点的值 5 大于左子树的值 3 也大于右子树的值 1 ，满足大顶堆性质不需要交换

将堆排序的过程分成了两部分，构建一个大顶堆，就沉下去最大值，然后断开与最大值的链接，重新构建大顶堆

可以看到过程打印的数组值就是图解中的每步。

堆排序的最坏、最好、平均时间复杂度均为 O(nlogn) ，是不稳定排序算法。

参考文章