版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
数据结构之优先队列前言数据结构队列的学习中，我们知道队列是先进先出的。任务被提交到队列中，按照先进先出的原则对各个任务进行处理。不过在现实的情况下，任务通常有着优先级的概念，例如短任务、管理员的操作应该优先执行。这是使用队列就无法描述了，这种特殊的应用我们使用一种称之为优先队列(堆)的方式来解决。优先队列和队列一样优先队列也支持入队和出队操作，不过区别在于优先队列的出队操作出队的是优先级最高的元素，这里以元素的大小来判定任务的优先级，越小，优先级越高。优先队列的模型如下图：基于这种优先队列的模型,我们可以多种方法对其进行实现,一种常用的方法就是使用链表以O(1)执行插入操作,,遍历最小元素并删除花费O(N)时间。基于优先队列的插入操作一般情况下多于删除操作这一情况，前者是一种较好的实现。另外可以使用二叉查找树来实现，这样一来插入和删除操作都是O（logN），不过二叉树支持多种操作用以实现优先队列未免有点杀猪用牛刀的感觉。
下面将介绍二叉堆实现优先队列。二叉堆二叉堆就结构性质上来说就是一个完全填满的二叉树，满足结构性和堆序性。结构性不必多说，就是完全二叉树应该满足的树结构。堆序性指的是：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。最大堆：当父节点的键值总是大于或等于任何一个子节点的键值。最小堆：当父节点的键值总是小于或等于任何一个子节点的键值。上面图片直接沿用的维基百科上的，笔者懒得在自己做个图了。结构性质上面对二叉堆的结构性质略有提及，这里我们进行下详细说明。看看二叉堆是如何实现的。仔细观察上述完全二叉树的结构，我们可以发现的是对于任意一个位置i，其结点的左孩子在2i的位置，右孩子在2i+1的位置上，基于上述的性质我们可以使用数组来实现二叉堆。由此二叉堆可以使用一个数组和一个代表当前堆的大小的整数组成。考虑到涉及到元素大小的比较，该数组元素实现了Comparable接口。[java]viewplaincopypublic
class
BinaryHeap
{
/**
*
Construct
the
binary
heap.
*/
public
BinaryHeap(
)
{
this(
DEFAULT_CAPACITY
);
}
/**
*
Construct
the
binary
heap.
*
@param
capacity
the
capacity
of
the
binary
heap.
*/
public
BinaryHeap(
int
capacity
)
{
currentSize
=
0;
array
=
new
Comparable[
capacity
+
1
];
}
private
static
final
int
DEFAULT_CAPACITY
=
100;
private
int
currentSize;
//
Number
of
elements
in
heap
private
Comparable
[
]
array;
//
The
heap
array
}
以上代码显示的是一个优先队列的架构。至于其提供的具体操作，我们先看看二叉堆的堆序性。堆序性简单的说保证优先队列的删除操作快速执行是堆序性质，基于这个特点我们需要找出最小元素，那么最小元素应该在根结点上，也就是最小堆。这样我们就能以常数时间执行findMin()操作了。二叉堆基本操作基于二叉堆的堆序性，我们来看看二叉堆基本操作是如何实现的吧！insert(插入)根据优先队列的模型，二叉堆实现的优先队列应该具备插入操作，不过根据其对序性具体的插入操作是如何进行的呢？看下面的演示：二叉堆插入元素14的情况。为将一个元素X插入到堆中，我们在下一个可用位置创建一个空穴，否则该堆将不是完全数。如果X可以放在该空穴中而不破坏堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上冒一步。继续改过程直到X能被放入空穴中为止。这种实现过程称之为上滤：新元素在堆中上滤直到找出正确的插入位置。实现代码：
[java]viewplaincopypublic
void
insert(
Comparable
x
)
throws
Overflow
{
//这里没有进行扩容处理
if(
isFull(
)
)
throw
new
Exception(
);
//
Percolate
up
int
hole
=
++currentSize;
//上滤,首先找到插入位置,之后元素交换一次
for(
;
hole
>
1
&&
pareTo(
array[
hole
/
2
]
)
<
0;
hole
/=
2
)
array[
hole
]
=
array[
hole
/
2
];
array[
hole
]
=
x;
}
可以知道的是当插入的元素小于堆中所有的元素的时候，必须上滤到根，插入时间为O(logN）deleteMin(删除最小元)基于优先队列的模型,出队的应该是最小元,按照最小堆的堆序性，找出最小元十分容易，麻烦的地方在于删除之后破坏了结构型，这是需要进行一些额外的操作。当删除一个最小元时，要在根节点建立一个空穴。由于现在堆少了一个元素，因此堆中最后一个元素X必须移动到该堆的某个地方。如果X可以直接被放到空穴中，那么deleteMin完成。不过这一般不太可能，因此我们将空穴的两个儿子中比较小者移入空穴，这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。因此，我们的做法是将X置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。演示过程如下:首先我们删除根元素13,建立一个空穴,之后判断元素31是否可以放入这个空穴中,明显不能,会破坏堆序性.之后我们选择较小的左儿子放入空穴,同时空穴下滑一层,之后判断31是否置于空穴中同上,26置于空穴中,空穴下滑一层,31可以置于空穴中,过程结束。这一种操作过程称之为下滤:空穴一步步下滑.源码实现:[java]viewplaincopypublic
Comparable
deleteMin(
)
{
if(
isEmpty(
)
)
return
null;
Comparable
minItem
=
findMin(
);
array[
1
]
=
array[
currentSize--
];
percolateDown(
1
);
return
minItem;
}
private
void
percolateDown(
int
hole
)
{
int
child;
Comparable
tmp
=
array[
hole
];
for(
;
hole
*
2
<=
currentSize;
hole
=
child
)
{
child
=
hole
*
2;
if(
child
!=
currentSize
&&
array[
child
+
1
].compareTo(
array[
child
]
)
<
0
)
child++;
if(
array[
child
].compareTo(
tmp
)
<
0
)
array[
hole
]
=
array[
child
];
else
break;
}
array[
hole
]
=
tmp;
}
同样的这个操作在最坏的情况下为O(logN),平均而言也为O(logN).优先队列其他操作上面对二叉堆实现的优先队列的两个基本操作做了一些讲解。我们知道的是在将任务提交给优先队列的时候有时候我们需要根据实际情况修改任务的优先级。decreaseKey(降低关键字的值)desreaseKey(p,m)操作降低在位置p处的值，降值幅度为正m，不过这种方式很可能破坏堆序性，因此需要通过上滤操作进行调整。这种方式能够动态的提高某个任务的优先级，使其在能够优先开始。increaseKey(降低关键字的值)与上个操作相反，降低任务的优先级。delete(删除)删除堆中某个任务，不过必须先执行decreasekey(P，+∞),然后执行deleteMin操作这种操作的任务并不是正常终止的，而是被用户终止的。构造二叉堆上述讲了二叉堆的方式实现优先队列。那么一个二叉堆又是如何构造的呢？简单的我们可以认为它可以使用N个相继的insert操作来完成。每个insert最坏时间为O(logN)则其构建时间为O（N）。更为常用的算法是先保持其结构性，之后再通过检查每个位置，下滤操作使其满足堆序性。一开始满足结构性，但是并不满足堆序性，我们在元素70的位置进行下滤操作。代码实现情况如下：
[java]viewplaincopypublic
BinaryHeap(
T[]
items
){
currentSize
=
items.length;
array
=
(T[])
new
Comparable[
(currentSize
+
2)
*
11
/
10
];
int
i=1;
for(
T
item
:
items
){
array[
i++
]
=
item;
}
buildHeap();
}
private
void
buildHeap(){
for(
int
i
=
currentSize/2;
i>0;
i--
)
percolateDown(
i
);
}
完整源码：[java]viewplaincopypackage
com.kiritor;
import
java.util.Arrays;
public
class
BinaryHeap
{
public
BinaryHeap(
)
{
this(
DEFAULT_CAPACITY
);
}
public
BinaryHeap(
Comparable[]
items
){
currentSize
=
items.length;
array
=
new
Comparable[
(currentSize
+
2)
*
11
/
10
];
int
i=1;
for(
Comparable
item
:
items
){
array[
i++
]
=
item;
}
buildHeap();
}
public
BinaryHeap(
int
capacity
)
{
currentSize
=
0;
array
=
new
Comparable[
capacity
+
1
];
}
public
void
insert(
Comparable
x
)
{
//
Percolate
up
int
hole
=
++currentSize;
for(
;
hole
>
1
&&
pareTo(
array[
hole
/
2
]
)
<
0;
hole
/=
2
)
array[
hole
]
=
array[
hole
/
2
];
array[
hole
]
=
x;
}
public
Comparable
findMin(
)
{
if(
isEmpty(
)
)
return
null;
return
array[
1
];
}
public
Comparable
deleteMin(
)
{
if(
isEmpty(
)
)
return
null;
Comparable
minItem
=
findMin(
);
array[
1
]
=
array[
currentSize--
];
percolateDown(
1
);
return
minItem;
}
private
void
buildHeap(
)
{
for(
int
i
=
currentSize
/
2;
i
>
0;
i--
)
percolateDown(
i
);
}
public
boolean
isEmpty(
)
{
return
currentSize
==
0;
}
public
boolean
isFull(
)
{
return
currentSize
==
array.length
-
1;
}
public
void
makeEmpty(
)
{
currentSize
=
0;
}
private
static
final
int
DEFAULT_CAPACITY
=
100;
private
int
currentSize;
//
Number
of
elements
in
heap
private
Comparable
[
]
array;
//
The
heap
array
private
void
percolateDown(
int
hole
)
{
int
child;
Comparable
tmp
=
array[
hole
];
for(
;
hole
*
2
<=
currentSize;
hole
=
child
)
{
child
=
hole
*
2;
if(
child
!=
currentSize
&&
array[
child
+
1
].compareTo(
array[
child
]
)
<
0
)
child++;
if(
array[
child
].compareTo(
tmp
)
<
0
)
array[
hole
]
=
array[
child
];
else
break;
}
array[
hole
]
=
tmp;
}
//
Test
program
public
static
void
main(
String
[
]
args
)
{
int
numItems
=
50;
BinaryHeap
h
=
new
BinaryHeap(
numItems
);
int
i
=
37;
try
{
for(
i
=
37;
i
!=
0;
i
=
(
i
+
37
)
%
numItems
)
h.insert(
new
Integer(
i
)
);
System.out.println(Arrays.toStri
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五版港口工程保险合同3篇
- 二零二五版涵洞工程环保监测合同3篇
- 二零二五版反担保合同模板：供应链金融3篇
- 二零二五年计时工劳动合同管理与心理关怀协议3篇
- 二零二五年度软件开发项目合同及其廉洁规定2篇
- 二零二五版教育SaaS平台软件服务合同3篇
- 二零二五版粉煤灰运输安全规范与应急预案编制合同3篇
- 二零二五年度特种饲料原料采购合同模板2篇
- 二零二五年防火墙安全防护系统集成与维护合同3篇
- 二零二五年度大数据中心建设与运营劳务分包合同3篇
- 2024版塑料购销合同范本买卖
- 二年级下册加减混合竖式练习360题附答案
- 大三上-诊断学复习重点
- 应收账款的管理培训课件
- 2021年道路交通安全法期末考试试题含答案
- 股东变更情况报告表
- 自带药物治疗告知书
- 房产中介门店6S管理规范
- 吞咽解剖和生理研究
- TSG11-2020 锅炉安全技术规程
- 异地就医备案个人承诺书
评论
0/150
提交评论