Fork me on GitHub

二叉树学习笔记(二)之堆

前言

继续上一篇笔记,本文接着讲 堆 。

是一类完全二叉树,常用于实现排序,选择最小(大)值和优先队列等

优先队列:一种特殊的队列,队列中元素出栈的顺序是按照元素的优先权大小,而不是元素入队的先后顺序。

堆的定义

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  • 堆中所有非叶子结点总是不大于或不小于其左右孩子结点
  • 堆总是一棵完全二叉树

即按完全二叉树的结点编号排列,n个结点的关键字序列称为

堆可分为:

  • 小顶堆:若堆中所有非叶子结点均不大于其左右孩子结点,则称为小顶堆,显然,根节点必为 n 个结点的最小值
  • 大顶堆:若堆中所有非叶子结点均不小于其左右孩子结点,则称为大顶堆,显然,根节点必为 n 个结点的最大值

相关概念:

  • 子堆:堆中的子树称为子堆
  • 堆顶:堆中根节点的位置称为堆顶
  • 堆尾:堆中最后结点的位置称为堆尾
  • 堆长度:堆中结点的个数称为堆长度

堆的存储结构类型与完全二叉树有所不同,定义如下:

1
2
3
4
5
6
7
8
9
10
typdefstruct {
RcdType *rcd; //堆基址,0号单元闲置
int n; //堆长度
int size; //堆容量
int tag; //小顶堆与大顶堆的标志:tag = 0为小顶堆,tag = 1为大顶堆
int (* prior)(KeyType,KeyType); //函数变量,用于关键字优先级比较
} Heap; //堆类型
/* 假设关键字类型为整型,大顶堆和小顶堆的优先函数可分别定义如下: */
int greatPrior(int x,int y) { return x>=y; }
int lessPrior(int x,int y) { return x<=y; }

堆的实现

堆的筛选

堆的筛选:将堆中指定的以 pos 结点为根的子树调整为子树,其前提是 pos 结点的左右子树均为子堆。

筛选操作的过程:

  • 将 pos 结点与左右孩子较优先者比较,若 pos 结点较优先则结束
  • 否则 pos 结点与左右孩子中较优先者交换位置,pos 位标下移
  • 重复上述步骤,直至 pos 指示叶子节点

算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Status swapHeapElem(Heap &H, int i, int j){
//交换堆H中的第i结点和第j结点
RcdType temp;
if(i<=0 || i>H.n || j<=0 || j>H.n) {
return ERROR;
}
temp = H.rcd[i];
H.rcd[i] = H.rcd[j];
H.rcd[j] = temp;
return OK;
}
void ShiftDown(Heap &H, int pos) {
//对堆H中位置为 pos 的结点做筛选,将以 pos 为根的子树调整为子堆
int lc,rc;
while(pos<=H.n/2) { //若pos结点为叶子结点,循环结束
lc = pos*2; //lc为pos结点的左孩子位置
rc = pos*2+1//rc为pos结点的右孩子位置
if(rc<=H.n&&H.prior(H.rcd[rc].key,H.rcd[lc].key)){
lc = rc; //lc为pos结点的左右孩子中较优先者的位置
}
if(H.prior(H.rcd[pos].key,H.rcd[lc].key)){
return; //若pos结点较优先,则筛选结束
}
swapHeapElem(H, pos, lc); //否则pos和较优先者lc交换位置
pos = lc; //继续向下调整
}
}

该筛选算法的时间复杂度为O(logn)

堆的插入

插入操作:将插入元素加到堆尾,此时须判别堆尾和其双亲结点是否满足堆特性,若不满足,则需要进行向上调整,将插入元素与双亲交换;交换后,插入元素若存在双亲且此双亲结点不满足堆特性,则需要继续重复上述过程。

步骤:

  • 将插入元素加到堆尾,并用 curr 指示堆尾
  • 若 curr 指示堆尾,插入操作结束,否则,将 curr 结点与其双亲结点比较,若 curr 结点较优先则交换, curr 上移,重复本步骤;否则操作结束

算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
Status InsertHeap(Heap &H, RcdType e) {
//将结点 e 插入至堆H中
int curr;
if(H.n>=H.size-1) return ERROR; //堆已满,插入失败
curr = ++H.n;
H.rcd[curr] = e; //将插入元素加到堆尾
while(1!=curr && H.prior(H.rcd[curr].key,H.rcd[curr/2].key)){
swapHeapElem(H, curr, curr/2); //交换curr与curr/2结点,向上调整
curr /=2;
}
return OK;
}

该插入算法的时间复杂度为O(logn)。

筛选与插入区别

  • 筛选操作是叶子节点向上调整;
  • 插入操作是叶子节点向下调整

建堆

  • 单节点的完全二叉树满足堆特性,叶子结点都是堆
  • n 个结点的完全二叉树建堆,须将以编号为n/2、n/2-1、…、1的结点为根的子树筛选为子堆

算法如下:

1
2
3
4
5
6
7
8
9
10
11
void MakeHeap(Heap &H, RcdType *E, int n, int size, int tag,int (* prior)(KeyType,KeyType)) {
//prior 为自定义的优先函数
int i;
//初始化
H.rcd = E;
H.n = n; H.size = size; H.tag = tag; H.prior = prior;
//对以i结点为根的子树进行筛选
for(i=n/2; i>0; i--) {
ShiftDown(H, i);
}
}

该建堆算法的时间复杂度为O(n)。

删除堆顶结点

操作:删除堆顶结点后,需对新的堆顶结点进行筛选

堆删除根节点1.png

算法如下:

1
2
3
4
5
6
7
8
9
Status RemoveFirstHeap(Heap &H, RcdType &e) {
//删除堆H的堆顶结点,并用e返回
if(H.n<=0) return ERROR; //堆已满,插入失败
e =H.rcd[1]; //取堆顶结点
swapHeapElem(H, 1, H.n); //交换堆顶与堆尾结点,
H.n--; //堆长度减1
if(H.n>1) ShiftDown(H, 1);//对新的堆顶结点进行筛选
return OK;
}

堆排序

堆排序属于选择类排序。

选择类排序的基本思想:在 n 个记录中,第 i 趟(i = 1,2,..,n-1)在第 i 到 n 个记录中选取关键字最小的记录作为有序序列中的第 i 个记录。选取最小关键字的策略决定了选择类排序算法的效率。

堆排序可采用大顶堆进行升序排序,采用小顶堆进行降序排序

以大顶堆升序排序为例

  • 先将待排序列建成大顶堆
  • 将堆顶与堆尾交换位置(也就是删除堆顶结点操作),堆长度-1,取堆顶结点进新序列
  • 对新的堆顶结点进行筛选,得到次大值结点
  • 重复以上步骤,可得一个升序序列

算法如下:

1
2
3
4
5
6
7
8
9
10
void HeapSort(RcdSqList &L) {//L为待排序列
Heap H; RcdType e; int i;
//将待排序列建成大顶堆
MakeHeap(H, L.rcd, L.length, L.size, 1, greatPrior);
//对以i结点为根的子树进行筛选
for(i=H.n; i>0; i--) {
//交换堆顶与堆尾结点,堆长度减1,筛选新的堆顶结点
RemoveFirstHeap(H, e);
}
}

堆排序算法的时间复杂度最坏为O(nlogn),空间复杂度为O(1)。

附上一张总结图

image

-------------Page's overThanks for reading-------------

本文标题:二叉树学习笔记(二)之堆

本文作者:SherlockYang

发布时间:2018年12月08日 - 16:12

最后更新:2018年12月09日 - 00:12

原始链接:https://sherlock-y.com/2018/12/08/二叉树学习笔记(二)之堆/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

如果文章内容对你有帮助,就赏博主一瓶维他奶吧~