队列性质是先进先出,在链表(C语言实现)中,我们介绍了使用链表实现队列的方法。对于有一些应用场景,我们并不希望完完全全地先进先出,而是希望不同的工作有不同的权重。这时候就需要用到优先队列了。
以下介绍了优先队列的C语言代码实现,代码链接。
0 二叉堆
二叉堆是一棵完全填满的二叉树,有可能的例外在最底层,底层元素从左到右填入。这样的树称为完全二叉树。一棵高度为h的完全二叉树有2h到2h+1-1个节点,显然其是O(lgn)。因为完全二叉树很有规律,所以它可以用一个数组表示,而不需要指针。
二叉堆可以分为两种形式:最大堆和最小堆。
在最大堆中,最大堆性质:除了根节点,对于所有的节点i都要满足:A[PARENT(i)] ≥ A[i]
;同理,最小堆性质:除了根节点,对于所有的节点i都要满足:A[PARENT(i)] ≤ A[i]
。
在堆排序算法中,我们一般使用最大堆;在这里所要描述的优先队列中,最小堆通常用于构造优先队列。
1 声明
如下,我们声明优先队列的形式:
1 |
|
2 插入
为了保证二叉堆的性质,其插入操作的基本思想就是创建一个空穴,将其往上冒,最后摆在其合适的位置。如下:
其代码实现如下:
1 | bool is_full(pQueue_t *H) |
3 删除
我们一般认为插入的值越小即权限越大,所以优先队列的出队列即获取并删除最小元。
我们采取的策略称之为下滤,即:
- 我们取出最后一个元素;
- 删除最小元后,我们将其较小的儿子放到空出的位置,同时空穴下滑了一层;
- 重复以上操作直到空穴中正好可以填入最后一个元素。
代码如下:
1 | MyElement get_and_delete_min(pQueue_t *H) |