数据结构之优先队列

数据结构之优先队列

刖言

数据结构队列的学习中，我们知道队列是先进先出的。任务被提

交到队列中，按照先进先出的原则

对各个任务进行处理。不过在现实的情况下，任务通常有着优先

级的概念，例如短任务、管理员的操作

应该优先执行。这是使用队列就无法描述了，这种特殊的应用我

们使用一种称之为优先队列(堆)的方式

来解决。

优先队列

和队列一样优先队列也支持入队和出队操作，不过区别在于优先

队列的出队操作出队的是优先级最高

的元素，这里以元素的大小来判定任务的优先级，越小，优先级

越高。优先队列的模型如下图：

最小住出队入鼠、插入

*---------优先队列*----------

基于这种优先队列的模型，我们可以多种方法对其进行实现，一种常

用的方法就是使用链表以0⑴执

行插入操作〃遍历最小元素并删除花费0(N)时间。基于优先队列

的插入操作一般情况下多除操作这

一情况，前者是一种较好的实现。

另外可以使用二叉查找树来实现，这样一来插入和删除操作都是

0(logN)，不过二叉树支持多种

操作用以实现优先队列未免有点杀猪用牛刀的感觉。下面将介绍

二叉堆实现优先队列。

二叉堆

二叉堆就结构性质上来说就是一个完全填满的二叉树，满足结构

性和堆序性。结构性不必多说，

就是完全二叉树应该满足的树结构。堆序性指的是：父节点的键

值总是大于或等于（小于或等于）任何

一个子节点的键值，且每个节点的左子树和右子树都是一个二叉

堆（都是最大堆或最小堆）。

最大堆：当父节点的键值总是大于或等于任何一个子节点的键值。

最小堆：当父节点的键值总是小于或等于任何一个子节点的键值。

最小堆：1最大堆：11

/\/\

23910

/\/\/\/\

45675678

上面图片直接沿用的维基百科上的，笔者懒得在自己做个图了。

结构性质

上面对二叉堆的结构性质略有提及，这里我们进行下详细说明。

看看二叉堆是如何

实现的。

仔细观察上述完全二叉树的结构，我们可以发现的是对于任意一

个位置i,其

结点的左孩子在2i的位置，右孩子在2i+l的位置上，基于上述的

性质我们可以使用

数组来实现二叉堆。

由此二叉堆可以使用一个数组和一个代表当前堆的大小的整数组

成。考虑到涉及到

元素大小的比较，该数组元素实现了Comparable接口。

[java]viewplaincopy

1.publicclassBinaryHeap

2.(

3./**

4.*Constructthebinaryheap.

5.*/

6.publicBinaryHeap()

7.(

8.this(DEFAULT_CAPACITY);

9.}

10.

11./**

12.*Constructthebinaryheap.

13.*@paramcapacitythecapacityofthebinaryheap.

14.*/

15.publicBinaryHeap(intcapacity)

16.{

17.currentsize=0;

18.array=newComparable[capacity+1];

19.)

20.privatestaticfinalintDEFAULT_CAPACITY=100;

21.

22.privateintcurrentsize;//Numberofelementsinh

eap

23.privateComparable[]array;//Theheaparray

24.)

以上代码显示的是一个优先队列的架构。至于其提供的具体操作，

我们先看看

二叉堆的堆序性。

堆序性

简单的说保证优先队列的删除操作快速执行是堆序性质，基于这

个特点我们需要找出

最小元素，那么最小元素应该在根结点上，也就是最小堆。这样

我们就能以常数时间执行

findMin()操作了。

二叉堆基本操作

基于二叉堆的堆序性，我们来看看二叉堆基本操作是如何实现的

吧！

insert(插入)

根据优先队列的模型，二叉堆实现的优先队列应该具备插入操作，

不过根据其对序性

具体的插入操作是如何进行的呢？看下面的演示：

二叉堆插入元素14的情况。

为将一个元素X插入到堆中，我们在下一个可用位置创建一个空

穴，否则该堆将不是完全数。

如果X可以放在该空穴中而不破坏堆的序，那么插入完成。否则,

我们把空穴的父节点上的元素

移入该空穴中，这样，空穴就朝着根的方向上冒一步。继续改过

程直到X能被放入空穴中为止。

这种实现过程称之为上滤：新元素在堆中上滤直到找出正确的插

入位置。

实现代码：

[java]viewplaincopy

1.publicvoidinsert(Comparablex)throwsOverflow

2.(

3.〃这里没有进行扩容处理

4.if(isFullO)

5.thrownewException();

6.

7.//Percolateup

8.inthole=++currentSize;

9.〃上滤，首先找到插入位置，之后元素交换一次

10.for(;hole>1&&pareTo(array[hole/2])<0;

hole/=2)

11.arrayfhole]=array[hole/2];

12.array[hole]=x;

13.)

可以知道的是当插入的元素小于堆中所有的元素的时候，必须上

滤到根，插入时间为o（logN）

deleteMin（删除最小元）

基于优先队列的模型，出队的应该是最小元，按照最小堆的堆序性，

找出最小元十分容易，麻烦

的地方在于删除之后破坏了结构型，这是需要进行一些额外的操

作。

当删除一个最小元时，要在根节点建立一个空穴。由于现在堆少

了一个元素，因此堆中最后一

个元素X必须移动到该堆的某个地方。如果X可以直接被放到空

穴中,那么deleteMin完成。

不过这一般不太可能，因此我们将空穴的两个儿子中比较小者移

入空穴，这样就把空穴向下推了

一层。重复该步骤直到X可以被放入空穴中。因此，我们的做法

是将X置入沿着从根开始包含

最小儿子的一条路径上的一个正确的位置。

演示过程如下：

首先我们删除根元素13,建立一个空穴，之后判断元素31是否可以

放入这个空穴中，

明显不能，会破坏堆序性.

之后我们选择较小的左儿子放入空穴，同时空穴下滑一层，之后判断

31是否置于空穴中

同上,26置于空穴中,空穴下滑一层,31可以置于空穴中，过程结束。

这一种操作过程称之为下滤:空穴一步步下滑.

源码实现：

[java]viewplaincopy

1.publicComparabledeleteMin()

2.(

3.if(isEmpty())

4.returnnull;

5.

6.Comparableminitem=findMin();

7.array[1]=array[currentsize—];

8.percolateDown(1);

9.

10.returnminitem;

11.)

12.privatevoidpercolateDown(inthole)

13.{

14.intchild;

15.Comparabletmp=array[hole];

16.

17.for(;hole*2<=currentsize;hole=child)

18.(

19.child=hole*2;

20.if(child!=currentsize&&

21.array[child+1].compareTo(array[child])<0)

22.child++;

23.if(array[child].compareTo(tmp)<0)

24.array[hole]=array[child];

25.else

26.break;

27.}

28.array[hole]=tmp;

29.}

同样的这个操作在最坏的情况下为O(logN),平均而言也为

O(logN).

优先队列其他操作

上面对二叉堆实现的优先队列的两个基本操作做了一些讲解。我

们知道的是在将任务提交给

优先队列的时候有时候我们需要根据实际情况修改任务的优先级。

decreaseKey(降低关键字的值)

desreaseKey(p,m臊作降低在位置p处的值，降值幅度为正m,

不过这种方式很可能破坏

堆序性，因此需要通过上滤操作进行调整。

这种方式能够动态的提高某个任务的优先级，使其在能够优先开

始。

increaseKey(降低关键字的值)

与上个操作相反，降低任务的优先级。

delete(删除)

删除堆中某个任务，不过必须先执行decreasekey(P,+河,然后

执行deleteMin操作

这种操作的任务并不是正常终止的，而是被用户终止的。

构造二叉堆

上述讲了二叉堆的方式实现优先队列。那么一个二叉堆又是如何

构造的呢？

简单的我们可以认为它可以使用N个相继的insert操作来完成。

每个insert最坏时间为O(logN)

则其构建时间为0(N)。

更为常用的算法是先保持其结构性，之后再通过检查每个位置,

下滤操作使其满足堆序性。

一开始满足结构性，但是并不满足堆序性，我们在元素70的位置

进行下滤操作。

代码实现情况如下：

[java]viewplaincopy

1.publicBinaryHeap(T[]items){

2.currentsize=items.length;

3.array=(T[])newComparable[(currentsize+2)*11/10]

4.

5.inti=l;

6.for(Titem:items){

7.arrayfi++]=item;

8.}

9.buildHe叩()；

10.)

11.

12.privatevoidbuildHeap(){

13.for(inti=currentSize/2;i>0;i—)

14.percolateDown(i);

15.}

完整源码：

[java]viewplaincopy

1.packagecom.kiritor;

2.

3.importjava.util.Arrays;

4.

5.

6.publicclassBinaryHeap

7.{

8.

9.publicBinaryHeap()

10.(

11.this(DEFAULT_CAPACITY);

12.}

13.publicBinaryHeap(Comparable[]items){

14.currentsize=items.length;

15.array=newComparable[(currentsize+2)*11/10];

16.

17.inti=l;

18.for(Comparableitem:items){

19.array[i++]=item;

20.)

21.buildHeapO;

22.}

23.

24.publicBinaryHeap(intcapacity)

25.(

26.currentsize=0;

27.array=newComparable[capacity+1];

28.)

29.

30.publicvoidinsert(Comparablex)

31.(

32.

33.〃Percolateup

34.inthole=++currentSize;

35.for(;hole>1&&pareTo(array[hole/2])<0;

hole/=2)

36.array[hole]=array[hole/2];

37.array[hole]=x;

38.)

39.

40.

41.publicComparablefindMin()

42.(

43.if(isEmpty())

44.returnnull;

45.returnarray[1];

46.)

47.

48.

49.publicComparabledeleteMin()

50.{

51.if(isEmpty())

52.returnnull;

53.

54.Comparableminitem=findMin();

55.array[1]=array[currentsize-];

56.percolateDown(1);

57.

58.returnminitem;

59.)

60.

61.

62.privatevoidbuildHeap()

63.(

64.for(inti=currentsize/2;i>0;i—)

65.percolateDown(i);

66.}

67.

68.

69.publicbooleanisEmpty()

70.{

71.returncurrentsize==0;

72.)

73.

74.

75.publicbooleanisFull()

76.(

77.returncurrentsize==array.length-1;

78.}

79.

80.

81.publicvoidmakeEmpty()

82.(

83.currentsize=0;

84.}

85.

86.privatestaticfinalintDEFAULT_CAPACITY=100;

87.

88.privateintcurrentsize;//Numberofelementsinh

eap

89.privateComparable[]array;//Theheaparray

90.

91.

92.privatevoidpercolateDown(inthole)

93.(

94.intchild;

95.Comparabletmp=array[hole];

96.

97.for(;hole*2<=currentsize;hole=child)

98.(

99.child=hole*2;

100.if(child!=currentsize&&

101.array[child+1].compareTo(array[child])<0)

102.child++;

103.if(array[child].compareTo(tmp)<0)

104.array[hole]=array[child];

105.else

106.break;

107.}

108.arrayfhole]=tmp;

109.)

110.

111.//Testprogram

112.publicstaticvoidmain(String[]args)

113.(

114.intnumitems=50;

115.BinaryHea