优先队列

原创
2013/03/26 12:54
阅读数 339

优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
例如操作系统必须决定进程的运行顺序。一般一个进程只能被允许运行一个固定的时间片,短的的作业要尽可能快的结束,因此在已经被运行的作业当中这些短作业拥有优先权。

优先队列中必须包含两个基本的操作:入队和出队。

实现方法

可以用链表来实现优先队列,但每次出队的代价必须遍历所有节点才能找到优先级最高的节点,此时的时间复杂度为O(n)。

另一种实现方法是二叉堆(完全二叉树),入队的时间复杂度为O(log N),出队的时间复杂度为O(1),出队后必须进行相应的调整保证结构的有效性(时间复杂度为O(log N)),

二叉堆的两个性质:

1.  必须是完全二叉树(任意元素i的左子树为2i,右子树为2i+1)。

2.  所有节点必须比子节点小(或者大)。

代码实现:

因为完全二叉树的性质,可以用数组实现。

image

初始化时,根据传递来的参数设定最大容量,并且在数组0处保留一个标志位(MINDATA的定义为-32767).

image

入队

image

出队

image

完整代码实现见如下链接

http://www.oschina.net/code/snippet_161121_19580

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部