首页 > itarticle > 优先队列

优先队列

admin 1月 29, 2021 0

这次，我们来说一说一个新的数据结构——优先队列。

什么是优先队列？以一个简单的例子来说，有一堆作业难度打乱的作业，作业难度从1-10（1是作业难度最小的，10是作业难度最大的）。为了能够在有限的时间内做完最多份作业，我们会怎么做？当然是每一次都做剩余作业中难度最小的那份作业，而这就是优先队列的特性，根据每个元素的优先级来决定出队列的次序。

优先队列的表示有许多，像链表、二叉查找树以及今天介绍的堆，现在，我们详细的说说堆这个数据结构。

堆实际上是一棵被完全填满的二叉树，并且，每一个父亲的值都要小于他的孩子节点的值，不然就不满足二叉堆。二叉堆是完全二叉树，那么二叉堆深度和完全二叉树计算相同，为 ⌊ logN ⌋ ，并且，由于是一棵完全二叉树，因此我们完全可以有数组来表示这棵完全二叉树：对于数组中任意位置 i 上的元素，其左儿子在位置 （2i） 上，右儿子在 （2i + 1）上，而它的父亲所在位置为 ⌊ i / 2 ⌋ 上，下面是一棵完全二叉树以及它的数组表示法：

queue_1
Screenshot from 2017-12-18 19-45-42

二叉堆的结构就和完全二叉树一样，前面我们提到，根据元素的优先级来决定出队列的次序，那么优先级是什么呢？优先级的标准其实是根据优先队列的应用场景来决定的：如果是将堆用于排序，那么优先级就是元素的大小；如果是系统调度程序决定运行那个进程，那么优先级就是该进程的作业完成的时长……我们就举优先级最简单的——元素大小，也就是优先队列进行排序的应用，既然讲到优先队列用于排序，那么就会有两个堆：大顶堆与小顶堆。大顶堆，顾名思义就是每一次都是剩余元素中最大元素出队，小顶堆就是剩余元素中最小的元素出队，两种堆的实现方法几乎是相同的，只不过优先级的设定改变而已。下图就是一个小顶堆的图示：

queue_2.png

下面是二叉堆的声明代码

二叉堆声明代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
struct  {
    int capacity;
    int size;
    ElementType *Elements;
}

typedef struct  *PriorityQueue;

PriorityQueue Initizlize(int MaxElements) {
    PriorityQueue H;
    if(MaxElements <5)
        return;
    H = malloc(sizeof(struct HeadStruct));
    if(H ==NULL)
        return;//二叉堆申请内存空间失败
    H -> Elements = malloc((MaxElements + 1) * sizeof(ElementType))
    if(H ->Elements==NULL)
        return;//二叉堆的数组内存空间申请失败
    H -> capacity = MaxElements;
    H -> size = 0;
    H -> Elements[0] = -1;
    return H;
}

现在，假设有一个元素 14 要入堆，过程如何呢？首先，我们在下一个空位置创建一个空穴，接着，我们判断待进入元素进入空穴后此时是否满足二叉堆，如果满足，插入成功，否则，根据前面说的，对于小顶堆，父亲节点的值均小于孩子节点的值，那么我们就把空穴的父节点的值放入空穴中，那么，空穴实际就向着根的方向向上走了一步，就这样不断朝着根的方向上行空穴，直到 14 这个新节点符合插入空穴后满足二叉堆的要求为止

queue_3.png

我们称这种插入方法为上滤：新的元素在堆中上滤直到找到适合的插入位置即停止；下面是二叉堆的插入元素代码：

元素插入代码：

二叉堆 新元素插入代码 

1
2
3
4
5
6
7
8
 
void Insert(ElementType x, PriorityQueue H) {
    int i;
    if(IsFull(H))
        return;//二叉堆已经存满了，存满标志就是 H->size = H -> capacity
    for(i =++ H ->size; H ->Elements[i /2]> x; i /=2)
    H -> Elements[i] = H -> Elements[i / 2];
    H -> Elements[i] = x
}

讲完插入，那么肯定还会有删除的；既然我们的插入是上滤操作，那么删除肯定就是下滤操作了，当我们删除一个元素时，那么就会出现一个空穴，在插入中，我们是将空穴的父亲节点的值放入空穴，使空穴向根的方向上行一步；删除操作可以说是插入的逆操作，将空穴的两个孩子节点中的较小值放入空穴中，然后，我们将堆中的最后一个元素放入空穴中，再放入的时候同样需要满足二叉堆的要求，就这样不断的下移空穴，知道元素可插入为止，下图是演示过程

queue_4.png

下面是二叉堆元素删除的代码：

二叉堆 元素删除代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
ElementType DeleteMin(PriorityQueue H) {
    int i, child;
    ElementType MinElement, LastElement;
    if(IsEmpty(H))
        return H ->Elements[0];//二叉堆为空，无元素可出
    MinElement = H -> Elements[1];
    LastElement = H -> Elements[H -> size --];
    for(i =1; i *2<= H ->size; i = child){
        child = i * 2;
        if(child != H ->size && H ->Elements[child +1]< HeadStruct ->Elements[child])
            child += 1;
        if(LastElement > H ->Elements[child])
            H -> Elements[i] = H -> Elements[child];
        else
            break;
    }
    H -> Elements[i] = LastElement;
    return MinElement;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能