...写出初始建堆过程图示,再根据初始堆写出堆排序过程图示。_百度知 ...
发布网友
发布时间：2022-04-24 17:02
共7个回答
热心网友
时间：2022-05-22 02:44
起始序列为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 节点。
参考资料来源：百度百科-堆
热心网友
时间：2022-05-22 04:02
(1)因此起始堆的情况如下：
14
15 30
28 5 10
(2)假设是打算得到一个从小到大的序列，所以需要建大顶堆，起始状态从下向上建堆：
第一步： 第二步：
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也位于了堆的第一个位置，
因此排序完成
热心网友
时间：2022-05-22 05:36
热心网友
时间：2022-05-22 07:28
则完全二叉树的节点编号1-6的元素初始内容依次为14 15 30 28 5 10
排序的过程：（以下为小根堆过程）
建堆步骤1 14 15 30 28 5 10
建堆步骤2 14 15 10 28 5 30
建堆步骤3 14 5 10 28 15 30
5 14 10 28 15 30(维护堆的性质)
建堆(小根堆)完成
热心网友
时间：2022-05-22 09:36
则完全二叉树的节点编号1-6的元素初始内容依次为14 15 30 28 5 10
排序的过程：（以下为小根堆过程）
建堆步骤1 14 15 30 28 5 10
建堆步骤2 14 15 10 28 5 30
建堆步骤3 14 5 10 28 15 30
5 14 10 28 15 30(维护堆的性质)
建堆(小根堆)完成
热心网友
时间：2022-05-22 12:00
热心网友
时间：2022-05-22 14:42
