首页 > 其他 > 详细

优先级队列-堆

时间:2014-01-16 00:00:34      阅读:457      评论:0      收藏:0      [点我收藏+]

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

  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)插入操作:

bubuko.com,布布扣
/*
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);
}
bubuko.com,布布扣

2) 删除操作

bubuko.com,布布扣
/*
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;
}
bubuko.com,布布扣


 

优先级队列-堆

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!