优先级队列-堆

首先明确优先级队列的两个表象：

1. 插入元素
2. 删除最小元素

能够实现上述两个操作的数据结构-----优先级队列。

我们可以使用数组（有序或无序）、单链表、二叉查找树、堆等数据结构来实现。

为什么选择堆来实现呢？

主要是从时间复杂度来考虑

1. 数组（有序）:插入操作 O(n) 删除操作 O(1)
2. 数组（无序）:插入操作 O(1) 删除操作 O(n)
3. 单链表:        插入操作 O(1)(往表头插) 删除操作 O(n)
4. 二叉查找树： 插入操作 O(logn) 删除操作 O(logn)
5. 堆 ---- 同二叉查找树 （但二叉查找树对于删除操作来说，因为总是删除左子树，会造成树的不平衡）

综上所述，选择最小堆来实现优先级队列

实现代码:

设数组A[0---n-1]满足堆性质

设Maxsize为队列的最大元素数

void siftup(int A[],int i,int x);

void siftdown(int A[],int i,int n);

1）插入操作：

/*
pre:  A[0---n-1]满足堆性质
post：插入元素t，使得A[0--n-1,n]同样满足堆性质
*/
void insert(int A[],int &n,int t)
{
    if(n>=Maxsize)
        return;
    n++;
    A[n-1] = t;
    siftup(A,n-1,t);
}

2) 删除操作

/*
pre:  A[0---n-1]满足堆性质
post：删除最小值
*/
int extractmin(int A[],int &n)
{
    if(n<1)
        return ERROR;
    int temp = A[0];
    swap(A[0],A[n-1]);
    n--;
    siftdown(A,0,n);
    return temp;
}

优先级队列-堆

原文：http://www.cnblogs.com/welsh-android-learning/p/3516370.html