数据结构-优先队列 接口定义与实现分析

顾名思义，优先队列将数据按优先级顺序排列。一个优先队列由许多有序的元素构成，优先级最高的元素可以有效而快速的确定。

例如，用来做负载均衡的服务器，当连接请求到达时，优先队列可以告知当前哪台服务器是处理此连接请求最佳的服务器。一般情况下，最空闲的服务器获取的优先级最高，因为它可以最好地处理服务请求。

优先队列的接口定义

优先队列的基本接口包含，1、初始化优先队列；2、销毁优先队列；3、向优先队列中插入一个元素；4、提取优先队列顶部的元素（释放）；5、获取优先队列中优先级最高的元素（不释放）；6、统计优先队列中元素的数量。

我们以名称pqueue作为优先级队列的名称，下面是各接口的定义：

pqueue_init

void pqueue_init(PQueue *pqueue, int (*compare)(const void *key1,const void *key2), void (*destroy)(void *data));

返回值：无

描述：初始化优先队列pqueue。

在对优先队列进行其他操作之前必须先调用初始化函数。在优先队列形成过程中，函数指针compare会被优先队列的各种操作调用，用来维持优先队列的堆特性。如果队列中较大的值有较高的优先级，那么当key1>key2时，函数返回1；当key1=key2时，函数返回-1。如果相反，队列中较小的值有较高的优先级，那么函数的返回结果相反。参数destroy是另一个函数指针，通过调用pqueue_destroy来释放动态分配的内存空间。例如，如果一个优先队列包含使用malloc动态分配内存的数据，那么当销毁队列时，destroy会调用free来释放内存空间。当一个结构化数据包含若干动态分配内存的数据成员时，destroy应该指向一个用户自定义的析构函数来释放数据成员和结构本身的内存空间。如果优先队列中的数据不需要释放，那么destroy应指向NULL。

复杂度：O(1)

pqueue_destory

void pqueue_destroy(PQueue *pqueue);

返回值：无

描述：销毁优先队列pqueue。

在调用pqueue_destroy之后不再允许进行其他操作，除非再次调用pqueue_init。

pqueue_destory会从优先队列中提取所有的元素，在删除每个元素的同时调用pqueue_init中destroy所指向的销毁函数（前提是此函数指针不为NULL）。

复杂度 O(n)，其中n是优先队列中结点的个数。

pqueue_insert

int pqueue_insert(PQueue *pqueue, const void *data);

返回值：如果插入元素成功，返回0，否则返回-1。

描述：向优先队列pqueue中插入一个元素。新元素包含一个指向data的指针，只要结点仍然存在于优先队列中，此指针就一直有效。与data相关的内存空间由函数的调用者来管理。

复杂度：O(lg n)，其中n是优先队列中结点的个数。

pqueue_extract

int pqueue_extract(PQueue *pqueue, void **data);

返回值：如果元素提取成功返回0；否则返回-1。

描述：从优先队列pqueue中提取优先队列顶部的元素。返回时，data指向已提取元素中存储的数据。与data有关的内存空间将由函数的调用者来管理。

复杂度：O(lg n)，其中n是优先队列中结点的个数。

pqueue_peek

void *pqueue_peek(const PQueue *pqueue);

返回值：优先队列中优先级最高的元素；如果队列为空，那么返回NULL。

描述：获取优先队列pqueue中优先级最高元素的宏。

复杂度：O(1)

pqueue_size

int pqueue_size(const PQueue *pqueue);

返回值：优先队列中的结点个数。

描述：获取优先队列pqueue结点个数的宏。

复杂度：O(1)

优先队列的实现与分析

实现优先队列最常用而简单的方法就是维护一个有序数据集。优先级最高的元素位于数据集的头部。然而，插入或提取元素之后必须重新排列数据集，这是一个复杂度为o(n)的操作（n为数据集元素的个数）。

因此，更好的方法就是 用一个局部有序的堆来实现优先队列。位于堆顶部的结点优先级最高，而且插入或提取数据之后重新排列堆的复杂度仅为o(lg n)。

优先队列与堆的操作基本相同，优先队列仅仅比堆多了一个接口而已。因此，我们可以通过 typedef Heap PQueue这种简单的方式来实现一个优先队列。

为了实现这些接口，我们只需要将优先队列的相应操作定义成堆的操作就可以了。优先队列中独有的操作pqueue_peek与pqueue_extract相类似，只是pqueue_peek返回队列中优先级最高的元素而不删除它。

示例：优先队列的头文件

/*pqueue.h*/
#ifndef PQUEUE_H
#define PQUEUE_H

#include "heap.h"

/*将优先队列作为堆实现*/
typedef Heap PQueue;

/*优先队列的公共接口*/
#define pqueue_init heap_init
#define pqueue_destroy heap_destroy
#define pqueue_insert heap_insert
#define pqueue_extract heap_extract 

#define pqueue_peek(pqueue)((pqueue)->tree == NULL ? NULL : (pqueue)->tree[0])

#define pqueue_size heap_size
#endif // PQUEUE_H

优先队列的示例：包裹分拣

很多大型快递公司每天要处理数以百万计的包裹，将这些包裹按照优先级排序是非常重要的。这在投递的人力、物力有限的情况下尤为重要。在这种情况下，具有高优先级的包裹往往优先投递。例如，一架用于投递服务的飞机，如果它每天只跑一个往返，那么那些要求第二天就要投递的包裹在当天就应该将上飞机。

确保包裹能够按照正确的优先级顺序送达指定目的地的方法是，将包裹的信息按照正确的优先级顺序存储在一个优先队列中。包裹分拣时，首先扫描包裹的信息，并将信息录入系统中。对于每个扫描过的包裹，其信息将会按照优先级顺序存储到队列中，以便包裹在系统中传递时，具有最高优先级的包裹将首先传递。

示例列举两个函数get_parcel和put_parcel，它们都是用来操作一个包含包裹信息parcel的优先队列。parcel在parcel.h中定义，此处不再列举。一个分拣器调用put_parcel将一个包裹信息加载到系统中。parcel中传递给put_parcel的一个成员变量代表优先序号。put_parcel将一个包裹插入一个优先队列中，并按照优先级找到它在队列中的位置。当分拣器准备在系统中传递下一个包裹时，它会调用get_parcel。函数get_parcel会取到最高优先级的包裹，这样就能保证包裹按照正确的顺序处理。

优先队列是管理包裹的最佳方法，因为某些场合，我们只关心下一个优先级最高的包裹是哪一个。这样可以避免维护包裹完全有序的系统开销。get_parcel和put_parcel的时间复杂度都是O(lg n)，因为这两个函数分别只调用了复杂度为O(lg n)的函数pqueue_extract和pqueue_insert。

示例：包裹分拣函数的示例

/*parcels.c*/
#include <stdlib.h>
#include <string.h>

#include <parcel.h>
#include <parcels.h>
#include <pqueue.h>

/*get_parcel 从优先队列提取包裹*/
int get_parcel(PQueue *parcels,parcel *parcel)
{
    parcel *data;
    
    if(pqueue_size(parcels)==)
        /*没有包裹可返回*/ 
        return -;
    else
    {
        if(pqueue_extract(parcels,(void **)&data)!=)
            return -;
        else
        {
            memcpy(parcel,data,sizeof(parcel));
            free(data);
        }
    }
    return ;
}
/*put_parcel 将包裹插入优先队列*/
int put_parcel(PQueue *parcels,const parcel *parcel)
{
    parcel *data;
    
    /*为包裹分配空间*/
    if((data = (parcel *)malloc(sizeof(parcel)))==NULL)
        return -;
    
    /*将包裹插入优先队列中*/
    memcpy(data,parcel,sizeof(parcel));
    
    if(pqueue_insert(parcels,data)!=)
        return -;
        
    return ;
}