堆排序
标签: 数据结构
学习人数: 7930


全屏播放
赞赏支持

前言

堆排序是一种选择排序。

选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。

 

算法思想

堆排序是利用堆的性质进行的一种选择排序。

动态效果示意图:

排序(6):堆排序

是一棵顺序存储完全二叉树

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆
其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;

如上图所示,序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个结点,元素3和元素8。

元素3在数组中以R[0]表示,它的左孩子结点是R[1],右孩子结点是R[2]...

登录查看完整内容


课后作业

课后习题

 

【2018年真题】在将数据序列(6, 1, 5, 9, 8, 4, 7) 建成大根堆时,正确的序列变化过程是()

A. 6,1,7,9,8,4,5    →    6,9,7,1,8,4,5    →    9,6,7,1,8,4,5    →    9,8,7,1,6,4,5    
B. 6,9,5,1,8,4,7    →    6,9,7,1,8,4,5    →    9,6,7,1,8,4,5    →    9,8,7,1,6,4,5    
C. 6,9,5,1,8,4,7    →    9,6,5,1,8,4,7    →    9,6,7,1,8,4,5    →    9,8,7,1,6,4,5    
D . 6,1,7,9,8,4,5    →    7,1,6,9,8,4,5    →    7,9,6,1,8,4,5    →    9,7,6,1,8,4,5    → 9,8,6,1,7,4,5

参考答案:A

 

【2015年真题】已知小根堆为 8,15,10,21,34,16,12,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是()。

A.1    B.2        C.3    D.4

参考答案:

 

【2011年真题】已知序列25,13,10,12,9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是()
A.1
B.2
C.4
D.5 

解答:B。首先与10比较,交换位置,再与25比较,不交换位置。比较了二次。 


【2009年真题】已知关键字序列 5,8,12,19,28,20,15,22 是小根堆(最小堆),插入关键字 3,调整后得到的小根堆是()。 

A.3,5,12,8,28,20,15,22,19 
B.3,5,12,19,20,15,22,8,28 
C.3,8,12,5,20,15,22,28,19 
D.3,12,5,8,28,20,15,22,19

参考答案:A
答案解析:考查小根堆的调整操作。 
小顶堆在逻辑上可以用完全二叉树来表示,根据关键序列得到的小顶堆的二叉树形式为下图左图: 

插入关键字 3 时,先将其放在小顶堆的末端,再将该关键字向上进行调整,得到的结果上图右边所示。所以,调整后的小顶堆序列为:3,5,12,8,28,20,15,22,19。 


登录后发布评论

1 条评论
skt otto
2020年12月9日 01:04

if (lc <= n && a[lc] < a[max]) max = lc;

我c语言学得不好,为啥这里a[lc]都小于a[max]了,max还变成lc了呢crying