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


高清播放
赞赏支持

前言

堆排序是一种选择排序。

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

 

算法思想

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

动态效果示意图:

排序(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]。

元素8在数组中以R[1]表示,它的左孩子结点是R[3],右孩子结点是R[4],它的父结点是R[0]。可以看出,它们满足以下规律:

设当前元素在数组中以R[i]表示,那么,

(1) 它的左孩子结点是:R[2*i+1];

(2) 它的右孩子结点是:R[2*i+2];

(3) 它的父结点是:R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

首先,按堆的定义将数组R[0..n]调整为堆(这个过程称为创建初始堆),交换R[0]和R[n];

然后,将R[0..n-1]调整为堆,交换R[0]和R[n-1];

如此反复,直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作:

(1)根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。

(2)每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后,这个数组已经是按照从小到大的顺序排列了。

 

先通过详细的实例图来看一下,如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后,我们来看一下完整的堆排序处理:

还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信,通过以上两幅图,应该能很直观的演示堆排序的操作处理。 

看完上面所述的流程你至少有一个疑问:

如何确定最后一个非叶子结点?

其实这是有一个公式的,设二叉树结点总数为 n,则最后一个非叶子结点是第 ⌊n/2⌋ 个。

 

代码实现

#include <iostream>
using namespace std;
//调整堆
void HeapAdjust(int *a, int i, int n) {
    int lc = i << 1;
    int rc = (i << 1) + 1;
    ...
登录查看完整内容


课后作业

课后习题

 

【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

赞(0)