数据结构C++——优先队列

文章目录

一、定义
二、ADT
三、优先队列的描述
- 3.1 线性表
- 3.2 堆
- - 3.2.1 最大堆的ADT
  - 3.2.2 最大堆的插入
  - 3.2.3 最大堆的删除
  - 3.2.4 最大堆的初始化
- 3.3 左高树 LT
- - 3.3.1 高度优先左高树HBLT
  - 3.3.2 重量优先左高树WBLT
  - 3.3.3 最大HBLT的插入
  - 3.3.4 最大HBLT的删除
  - 3.3.5 合并两棵最大HBLT
  - 3.3.6 初始化最大HBLT
四、应用
- 4.1 堆排序
- 4.2 霍夫曼编码

一、定义

优先级队列(priority queue)：

0个或多个元素的集合
每个元素都有一个优先级或值。
与FIFO结构的队列不同，优先级队列中元素出队列的顺序由元素的优先级决定。
从优先级队列中删除元素是根据优先级高或低的次序，而不是元素进入队列的次序.
优先级队列中的元素可以有相同的优先级

对优先级队列执行的操作有:

查找一个元素(top)
插入一个新元素(push)
删除一个元素(pop)

两种优先级队列：

最小优先级队列：“查找/删除” 操作用来“查找/删除”优先级最小的元素
最大优先级队列：“查找/删除”操作用来“查找/删除”优先级最大的元素

二、ADT

实例：

有限个元素集合
每个元素都有一个优先级

操作（以最大优先级队列为例）：

empty()：判断优先级队列是否为空，为空时返回true
Size()：返回队列中的元素数目
top()：返回优先级最大的元素
pop()：删除优先级最大的元素
push(x)：插入元素x

三、优先队列的描述

3 种描述方法：

线性表
堆
左高树

3.1 线性表

采用无序线性表来描述最大优先级队列

数组描述(利用公式Location(i)=i-1)
插入：表的右端末尾执行，时间: $\Theta(1)$ ;
删除: 查找优先级最大的元素，时间: $\Theta(n)$ ;
链表描述
插入：在链头执行，时间: $\Theta(1)$ ;
删除: 查找优先级最大的元素， $\Theta(n)$ ;

采用有序线性表描述最大优先级队列

数组描述(利用公式Location(i)=i-1),元素按递增次序排列)
插入：先查找插入元素的位置，时间: O(n) ;
删除: 删除最右元素，时间: $\Theta(1)$ ;
链表描述(按递减次序排列)
插入：先查找插入元素的位置，时间: O(n) ;
删除: 表头删除，时间: $\Theta(1)$ ;

3.2 堆

大/小根树：

每个节点的值都大于(小于)或等于其子节点(如果有的话)值的树
大根树(max tree):又称最大树
小根树(min tree):又称最小树
大根树或小根树节点的子节点个数可以大于2

在这里插入图片描述

大根堆/小根堆：

既是大根树(小根树)，又是完全二叉树
大根堆(max heap):又称最大堆
小根堆(min heap):又称最小堆

堆是完全二叉树，可用一维数组有效地描述堆。
关于完全二叉树，见本系列数据结构C++——二叉树和树

在这里插入图片描述

3.2.1 最大堆的ADT

数据成员：

T *heap; // 元素数组
int arrayLength; //数组的容量
int heapSize; //堆中的元素个数

方法：

empty()：判断heapSize是否为0
Size()：返回heapSize的值
top()：如果堆为空(heapSize==0)，抛出异常queueEmpty；否则返回 heap[1]（heap[0]未使用）
pop()
push(x)

重点：插入push、删除pop

3.2.2 最大堆的插入

流程：

作为叶子节点插入最大堆
与其父节点比较，若新插入节点更大，则两者交换(实际只是将父节点的值向下移)。否则该位置就是合法的，插入结束。
若发生交换，则重复这个过程，直到位置合法/交换为根节点

在这里插入图片描述

代码实现：

template<class T>
maxHeap<T>& maxHeap<T>::push(const T& theElement)
{// 把theElement 插入到大根堆中if  (heapSize = = arrayLength-1) // 没有足够空间……//数组长度加倍//为theElement寻找应插入位置// currentNode 从新的叶节点开始，并沿着树上升int  currentNode = ++heapSize;while (currentNode != 1 && theElement > heap[currentNode/2]){//不能够把theElement放入heap[currentNode]heap[currentNode] = heap[currentNode/2]; // 将元素下移currentNode /= 2; // 移向父节点}heap[currentNode] = theElement;}