个性化阅读
专注于IT技术分析

优先队列(priority queue)和堆(heap)详解:二叉堆、d-堆、左式堆、斜堆和二项堆

优先队列(priority queue)类似于一般队列(queue),一般队列是一种简单的数据结构,特点是先进先出,详情可查看队列数据结构和实例详解。数据结构从最简单的线性结构,到树结构(二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理),然后是上一节谈到的散列表实现原理,本节讨论的优先队列和堆(heap)相对而言常用于辅助实现其它算法,例如数据压缩赫夫曼编码算法、Dijkstra最短路径算法、Prim最短生成树算法,优先队列还可以实现事件模拟、选择问题,另外人工智能中的A*搜索算法和操作系统的线程调度也使用优先队列。

优先队列的特点是元素正常入队,按照优先级的大小进行出队。堆是另一种与优先队列不同的数据结构,一般来说,堆是用来实现优先队列的,非严格来说,优先队列可以等同于堆,因为堆是用来实现优先队列的,所以优先队列的大部分内容都是在讨论堆,但不要忘记主要内容还是优先队列。下面会首先介绍优先队列的定义,然后讨论各中堆的原理和实现。

优先队列(priority-queue)和堆(heap)

一、优先队列的概念和定义

优先队列(priority queue)概念图解

优先队列和普通队列不同的地方在于,在优先队列中,每个记录保存一个优先级值或关键字(本文使用关键字表示),任意记录正常从队尾入队,按照优先级大小或关键字的大小进行出队。最大关键字先出队,称为最大优先队列或降序优先队列;最小关键字先出队,称为最小优先队列或升序优先队列,如下图是一个使用普通数组表示的最大优先队列:

优先队列(priority queue)实例图解

第一次出队操作,关键字12最大,所以12先出队,第二次进行出队操作,此时11最大,所以11出队,如果遇到关键字相等的情况,则按照它们在队中的位置进行出队。

优先队列的实现方式有哪些呢?一般来说,实现优先队列的方式有:有序表或无序表(即数组,或顺序表和链表)、二叉树、AVL平衡二叉树、堆和二叉堆。使用普通的表实现优先队列的性能比较低,有序表插入为O(1),无序表取出为O(n),另外使用普通二叉树实现优先队列只能保证平均时间为O(log n),但最差情况是O(n),AVL树则需要复杂的无关操作,而堆可以实现性能较好的优先队列,取出效率可达到O(1),一般的操作都能达到O(log n)。

二、堆和二叉堆(binary heap)

堆主要用来实现优先队列,二叉堆是堆的一种。堆是一个完全二叉树,也就是一棵二叉树,在叶子上从左到右被完全填满元素,结点中至少包括优先级值或关键字,堆的主要特点是:任意结点的关键字大于或等于(小于或等于)儿子结点,又可分为最大堆(max heap),结点的关键字大于或等于儿子结点;最小堆(min),其结点关键字小于或等于儿子结点,这个特点又称为堆的有序性,下图是最大堆的一个实例:

堆(Heap)实例图解

1、二叉堆的概念和定义

上图就是一个二叉堆,二叉堆是堆的最简单形式,设二叉堆的高度为h,二叉堆的所有叶子结点位于第h层或第h-1层(h>0),高度为h的二叉堆有2^h到2^(h+1)-1个结点,其中h=log n。堆的实现方式可使用顺序表或数组和二叉树,不管哪种实现方式,优先队列或堆的表示一般都是使用二叉树或多叉树。看下图中的二叉堆和对应的数组,根据它们的索引,我们看另一种二叉堆的逻辑定义:

二叉堆(Binary Heap)实例和数组实现

上图是一个最小堆,任意结点关键字小于或等于儿子结点,给堆中的结点从左到右加上索引,对应于数组中的索引和关键字。这是二叉堆使用数组表示的一种常见形式,得出二叉堆的逻辑定义如下:

  • n个元素序列{k1, k2, …, ki, …, kn},k为关键字或优先级值,i为元素的索引;
  • 任取i属于{1, 2, 3, …, n/2};
  • 最小堆表示为:ki <= k2i,ki <= k(2i+1);
  • 最大堆表示为:ki >= k2i,ki >= k(2i+1)。

以上定义从1开始,也可以从0开始,两者的区别是,使用0开始需要对0进行检测,若使用1开始,最大堆第0个放一个极大的值,最小堆放一个极小的值,因为使用数组表示二叉堆,所以堆的大小需要预先进行预测。下面索引从第0个开始,结点间的索引关系为:

  • i为第i个结点,根结点没有父结点;
  • 父结点索引为:(i-1)/2;
  • 左结点索引为:2*i+1;
  • 右结点索引为:2*i+2。

2、二叉堆的基本操作详细实现

下面讨论的二叉堆操作是优先队列的基本操作,其它堆实现时也是提供类似的操作,其中最重要的两个操作就是入队和出队,入队又称为插入操作,出队又称为删除最小/最大元素,下面是常见的优先队列操作,首先看看下面,最小二叉堆的ADT声明:

// 使用最小二叉堆使用优先队列

// 基本数据记录
typedef struct Song{
    char name[128];
    char singer[128];
} Song;

// 结点
typedef struct qnode{
    int key; // 关键字或优先级值
    Song song;
} QNode;

// 优先队列对外ADT
typedef struct priorityqueue{
    int length; // 数组长度
    int size; // 记录数量
    QNode **list; // 记录数组,使用一个数组表示一个二叉堆/二叉树
} PriorityQueue;

// 最小堆优先队列函数声明
extern PriorityQueue *pqueue_init(int length);
extern int pqueue_is_empty(PriorityQueue *queue);
extern int pqueue_is_full(PriorityQueue *queue);
extern int pqueue_push(PriorityQueue *queue, int key, Song *song);
extern QNode *pqueue_top(PriorityQueue *queue); // 获取顶部元素
extern int pqueue_pop(PriorityQueue *queue); // 释放顶部元素
extern int pqueue_decrease(PriorityQueue *queue, int index, int delta);
extern int pqueue_increase(PriorityQueue *queue, int index, int delta);
extern int pqueue_delete(PriorityQueue *queue, int index);
extern PriorityQueue *pqueue_build(QNode *list, int length);
extern void pqueue_traverse(PriorityQueue *queue);
extern int pqueue_clear(PriorityQueue *queue);

该最小二叉堆优先队列的实现提供了完整的操作,包括检查优先队列是否已满、入队或插入操作、删除或出队操作、增加和降低关键字的值、删除关键字和直接构建优先队列的操作。

(1)二叉堆插入和上滤操作图解

二叉堆插入和上滤操作图解

(2)二叉堆删除和下滤操作图解

二叉堆删除和下滤操作图解

注意,以上是使用一个数组来表示一个二叉树,虽然是使用数组表示,但是操作方式依然是按照二叉树的形式操作,后面还可能会有类似的表示方式,以上最小二叉堆优先队列完整实现可在github上查看,在main.c文件中提供类似STL库的使用方式:https://github.com/onnple/priorityqueue

三、d-堆(d-heap)

d-堆是二叉堆的推广,d-堆的每个结点有d个儿子,二叉堆也就是2-堆,又类似于树中的B树或散列表中的可扩散列表。d-堆的所有基本操作时间复杂度为O(log n),底数为d,删除/出队操作时间复杂度为O(d log n),底数为d,下面是一个3-堆的实例:

d-堆和3-堆实例

当优先队列过大而不适合放在内存中时,可采取类似B树的方式操作d-堆。在讨论堆中有一个基本的操作:合并(merge),d-堆的合并操作比较困难,下面介绍的三种堆(左式堆、斜堆和二项堆)都支持高效率的合并。

四、左式堆(leftist heap)

1、左式堆的定义

左式堆示例

左式堆是一种支持合并的堆,合并是集合的基本操作,在第一节有谈到集合这种数据结构,其特点是数据结构之间没有任何关系,和数学中的集合是类似的。所有支持高效合并的数据结构都需要使用指针,但是可能会导致其它操作变慢。

如上图是一个左式堆的例子,类似于AVL平衡二叉树,提供相关的平衡信息,和二叉堆一样具有相同的堆序性,同样也是二叉树的形式,左式堆的所有操作都是以合并为主,删除和插入都是使用合并,合并操作的时间复杂度为O(log n)。

左式堆的平衡信息使用结点的零路径长,零路径长是指结点到一个没有两个儿子的叶子结点的最短路径长,空结点的最短路径长为-1,零路径长实际是结点的最短高度,也就是到最近树叶的距离,如上图的蓝色数字是对应结点的零路径长。

2、左式堆的性质

(1)堆序性,一般左式堆都是使用最小堆(也可以实现最大堆),对于最小堆,任意结点关键字大于或等于其父结点的关键字,也就是key(i) >= key(parent(i))。

(2)左边树更深,任意结点的左儿子零路径长大于或等于右儿子零路径长,也就是distance(left(i)) >= distance(right(i));任意结点的零路径长比右儿子的零路径长最小值多1,也就是distance(i)=1+distance(right(i))。

在右路径上有r个结点的左式树必然至少有2^r-1个结点,函数n个结点的左式树,其右路径最多有log(n+1)个结点,因此将左式堆的所有操作放在右路径上进行会更加节省时间,相关操作可能需要相应的恢复性质的操作。

3、左式堆的数据结构

左式堆的实现不使用数组表示,而是使用二叉树表示,其数据结构成员至少包括:

  • 数据项,实体数据;
  • 关键字或优先级值;
  • 左右儿子,和二叉树的一样;
  • 零路径长,和AVL树的结点高度一样。

4、左式堆的合并操作

左式堆的所有基本操作都可以使用合并操作,插入是合并的特殊情况,即合并操作已经包括插入操作,插入可看作是一个单结点堆和一个大的堆的合并。

合并的核心主要是将两个堆的右路径上的结点进行合并(这里使用最小堆),每次递归合并处理,更新已合并根结点的零路径长,检查根结点左右儿子是否符合左式堆属性。

h1和h2是两个最小左式堆,若h1和h2中有一个空堆,则返回非空堆,如果两个都不是空堆,则进行合并操作,下面是详细的合并步骤:

  • 比较h1和h2根关键字大小,如key(root(h1)) > key(root(h2));
  • 将最小的关键字结点入栈,在最小关键字的堆中位置移动到下一个最右边的儿子(下移操作);
  • 递归比较两个堆的关键字,将最小关键字结点入栈,并在最小关键字的堆中下移到下一个右儿子;
  • 重复操作,知道遇到一个null结点;
  • 将最后处理的结点作为栈顶的右儿子,并调整该子树转为左式堆;
  • 递归将栈元素出栈,将出栈的元素作为栈顶的右儿子,并调整为左式堆。

下图是两个左式堆合并的完整实例图解:

左式堆(leftist heap)合并操作完整图解

5、左式堆完整代码实现

左式堆合并操作递归处理图解

上面解释的合并步骤是以栈为基础的,可以使用栈作为辅助,也可以不使用栈辅助仅是作为一种逻辑处理方式,我们可以使用递归的方式进行处理,上图是递归处理的实例图解,下面是左式堆的ADT声明:

// 左式堆实现优先队列(最小堆)

// 实体数据
typedef struct label{
    int color;
    char title[128];
} Label;

// 左式堆结点
typedef struct lnode{
    int key;
    int dist;
    Label label;
    struct lnode *left;
    struct lnode *right;
} LNode;

// 左式堆对外ADT
typedef struct leftistheap{
    int size;
    LNode *root;
} LeftistHeap;

// 左式堆操作函数声明(参考优先队列的基本操作)
extern LeftistHeap *lheap_init();
extern int lheap_is_full(LeftistHeap *heap);
extern int lheap_is_empty(LeftistHeap *heap);
extern int lheap_push(LeftistHeap *heap, int key, Label *label);
extern LNode *lheap_top(LeftistHeap *heap);
extern int lheap_pop(LeftistHeap *heap);
extern void lheap_traverse(LeftistHeap *heap);
extern int lheap_clear(LeftistHeap *heap);

以上左式堆的实现相对比较简单,主要是合并操作,使用栈也会比较简单,其完整源码可在github上查看:https://github.com/onnple/leftistheap,其中调用例子中的左式堆如下:

左式堆代码调用实例

五、斜堆(skew heap)

斜堆类似于伸展树,也就是对左式堆的扩展,不需要相关的平衡信息,只需要保留堆的基本有序性,和上面使用数组表示的二叉堆对比,斜堆则是使用二叉树表示的。斜堆的最坏执行情况为O(n)(链表的形式),每次操作的摊还时间为O(log n),斜堆的基本操作也是合并。

1、斜堆合并操作

斜堆的基本操作和左式堆一样,主要对右路径的结点进行合并,其中有两个例外的地方,如下:

  • 左式堆需要检查左右儿子是否满足左式堆的性质,斜堆则不需要;
  • 斜堆除了最大关键字结点外,其它结点都无条件交换左右儿子。

下图是斜堆合并操作的完整图解:

斜堆(skew heap)合并操作完整图解

2、斜堆代码实现

和左式堆的实现类似,可借用栈或直接处理,另外要注意上面提到的两点,下面是斜堆的ADT声明:

// 斜堆实现优先队列

// 数据实体
typedef struct process{
    int threads;
    int memsize;
} Process;

// 斜堆结点
typedef struct knode{
    int key;
    Process process;
    struct knode *left;
    struct knode *right;
} KNode;

// 斜堆对外ADT
typedef struct skewheap{
    int size;
    KNode *root;
} SkewHeap;

// 斜堆实现优先队列,函数操作声明
extern SkewHeap *sheap_init();
extern int sheap_is_full(SkewHeap *heap);
extern int sheap_is_empty(SkewHeap *heap);
extern int sheap_push(SkewHeap *heap, int key, Process *process);
extern KNode *sheap_top(SkewHeap *heap);
extern int sheap_pop(SkewHeap *heap);
extern void sheap_traverse(SkewHeap *heap);
extern int sheap_clear(SkewHeap *heap);

斜堆的实现和左式堆的实现差不多,同样可以使用栈作为辅助,完整实现源码可查看github项目:https://github.com/onnple/skewheap,项目调用实例其中的堆为:

斜堆代码调用实例

六、二项队列(binomial queue)

二项队列使用二项堆(binomial heap)实现,二项堆的主要应用是实现优先队列,而二项堆是二项树的合集,也就是多个二项树形式一个二项堆,又称为森林。

二项树(binomial tree)实例图解

0阶二项树有1个结点,k阶二项树由两个k-1阶的二项树组成,其中一个二项树作为另一个的最左儿子(也可以放在最右边),k阶二项树的特点如下:

  • k阶二项树有2^k个结点;
  • 深度为k;
  • 深度i处有kCi个结点,0 <= i <=k;
  • 根结点的度数为k,从右到左的子树阶数k-1, k-2, …, 0。

一个二项堆中的二项树的数量等于二项堆结点数量n的二进制表示中的1的个数,或为O(log n),下面是一个二项堆的实例:

二项堆(binomial heap)实例图解

以上二项堆的元素个数为n=12,二进制表示为1100,也就是有2棵二项树,分别是2阶二项树和3阶二项树组成,log(12)向上取整也为3,二项堆的最坏运行时间为O(log n)。

1、二项堆的数据结构

二项堆的表示形式同样使用类似二叉树的形式,基本数据结构是类似的,但有些地方稍有不同,后面会有提到。

  • 关键字和数据项;
  • 度数;
  • 最左儿子;
  • 其它儿子(兄弟)数组;
  • 父结点。

2、二项堆的基本操作

(1)合并操作

二项堆的所有主要操作都依赖于合并操作,h1和h2是两个二项堆,如果其中有一个为空堆则返回另一个堆。

合并的第一个操作是直接合并:找出h1和h2的多个二项树,按照二项树的度数或阶数从左到右升序的方式预先合并两个二项堆。

接着对已合并的树进行调整,以确保满足二项堆的性质:

  1. 最多只有一个二项树是任意阶数,也就是说,在一个二项堆中每个二项树的阶数都不一样,若遇到相同阶数的二项树则合并,这是调整的最主要原则。合并操作从左到右遍历已合并的各个二项树根结点。
  2. 遍历已合并的二项树根结点,从最左边的结点开始遍历,当前结点为x,上一个结点为prev,下一个结点为next,下一个的下一个为next-next。
  3. x和next的阶数不同,跳过不处理。
  4. x和next的阶数相同。(1)x和next-next的阶数相同,跳过处理;(2)x的关键字小于或等于next,将next作为x的最左儿子;(3)x的关键字大于next,将x作为next的最左儿子。

下图是二项堆合并操作的完整实例图解:

二项堆(binomial tree)合并操作完整图解

(2)最小元

寻找最小元可通过搜索所有二项树的根找出,也就是从根结点的最左元素开始,时间为O(log n),一个二项堆中最多有O(log n)棵不同的树,另外或者也可以在其它操作中将最小元放到根上,即可达到O(1)。

(3)删除最小元

先找出拥有最小元的二项树C的根,除了树根外,使用该树C的其它元素创建一棵新的二项堆A,除了拥有最小元的二项树C外,其它二项树重新组成一个新的二项堆B,将这两个二项堆A和B进行合并即可完成删除操作。

3、二项队列或二项堆的实现代码

在本实现中,根结点不指向所有儿子结点,只指向最左儿子,由这个儿子的兄弟指针指向其它儿子;另外所有二项树的根结点均用一个表存起来,这里使用链表,额外实现了一个双向循环链表(如果你用其它语言实现,则可以使用类似list的容器)。代码稍微有些复杂,下面先看二项堆ADT的声明代码:

#include "list.h"

// 二项堆实现优先队列BinomialHeap

// 数据项
typedef struct area{
    int width;
    int height;
} Area;

// 结点
typedef struct anode{
    int key;
    Area value;
    int degree;
    struct anode *parent, *sibling, *child;
} ANode;

// 二项堆对外ADT
typedef struct binomialheap{
    list *list;
    int size;
} BinomialHeap;

// 二项堆优先队列操作函数声明
extern BinomialHeap *bheap_init();
extern int bheap_is_full(BinomialHeap *bheap);
extern int bheap_is_empty(BinomialHeap *bheap);
extern int bheap_push(BinomialHeap *bheap, int key, Area *value);
extern ANode *bheap_top(BinomialHeap *bheap);
extern void bheap_pop(BinomialHeap *bheap);
extern void bheap_traverse(BinomialHeap *bheap);
extern int bheap_clear(BinomialHeap *bheap);

优先队列的操作都是类似的,以上使用二项堆实现的优先队列,完整源码可以在github上的项目查看:https://github.com/onnple/binomialheap。其中在main文件中有调用实例,实例中的二项堆如下图:

二项堆调用实例

七、优先队列和堆的应用

1、编程语言中的实现

C++的STL库中提供优先队列,Boost则提供更完整的优先队列和不同的堆,如二项堆、d-堆、斐波那契堆、配对堆和斜堆等,其它语言如Java、Python、PHP、Perl、Go也有提供。

2、使用优先队列的Dijkstra最短路径算法

当图以邻接表或矩阵的形式存储时,优先队列可以在实现Dijkstra算法时有效地提取最小值。

3、Prim算法

实现Prim算法存储节点密钥,每一步提取最小密钥节点。

4、数据压缩

用于压缩数据的哈夫曼编码中。

5、人工智能中的A*搜索算法

A*搜索算法寻找加权图中两个顶点之间的最短路径,先尝试最有希望的路径。优先级队列(也称为边缘)用于跟踪未探索的路由,总路径长度的下界最小的路由具有最高优先级。

6、堆排序

堆排序通常使用堆实现,堆是优先级队列的实现。

7、操作系统

它也用于操作系统的负载平衡(服务器上的负载平衡)、中断处理。

赞(0) 打赏
未经允许不得转载:srcmini » 优先队列(priority queue)和堆(heap)详解:二叉堆、d-堆、左式堆、斜堆和二项堆
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏