常见基本的数据结构——优先队列（堆）
Baby-Lily 人气:0在多用户环境中，操作系统调度程序必须决定在若干进程中运行那个进程。一般一个进程只能被允许运用一个固定的时间片。一种算法是使用一个队列。开始时作业被放在队列的末尾。调度程度将反复提取队列中的第一个作业并运行它，直到运行完毕或者该作业的时间片被用完，并在作业为被用完时将其放入队列的末尾。但是一般来说，短的作业要尽可能快地结束，这一点很重要，因此在已经被运行的作业中这些短作业应该拥有优先权。此外，有些作业虽然短小但也很重要，也应该拥有优先权。这种特殊的应用似乎需要一些特殊的队列，我们称之为优先队列。
模型
优先队列应该允许至少下面的两种操作，Insert(插入)，以及DeleteMin(删除最小值)，它的作用是找出，返回和删除优先队列中的最小值。Insert操作相当于队列的入队，DeleteMin操作相当于队列中的出队操作。在贪婪算法中，优先队列也是重要的，因为该算法通过反复的求出最小元来进行计算。
一些简单的实现
使用简单链表可以在表头进行插入并以O(1)的时间复杂度，但是遍历最小元的话则需要O(N)的时间复杂度。另外的一种思路是始终保持排序状态，这使得插入的高昂代价O(N)，而DeleteMin的代价是O(1)，但是在实际中，DeleteMin的操作次数从不多于插入的操作次数。
还可以使用二叉查找树来实现优先队列，它对这两种操作的时间都是O(logN)。反复出去左子树的节点似乎损害树的平衡，使得右子树加重，最坏的情况下，左子树为空，右子树拥有的元素最多也就是它的两倍，这只是在其期望深度上加上了一个小的常数。
使用查找树可能有些过分，因为它支持的操作太多了实际上并不需要你这么多。我们使用的数据结构不需要指针，它以最坏的情形时间O(logN)支持上述的两种操作，插入实际上将花费常数平均时间，并且能够使用线性的时间建立具有N项的优先队列。
二叉堆
二叉堆，它的使用对于优先队列的实现是如此的普遍，以至于堆可以不加修饰使用一般是指这种数据结构的实现。和二叉查找树相类似，堆也有两个性质，即结构性和堆序性，堆的操作必须必须要到堆的所有性质被满足时才能终止。
结构性质
堆是一棵被完全填满的二叉树，有可能的例外只在底层，在底层从左到右的填入，这样的树称为完全二叉树。容易证明，一棵高为h的完全二叉树有2^h到2^(h+1) - 1个节点。这意味着，完全二叉树的高是logN，显然它是O(logN)。
一个很重要的规律是完全二叉树是不需要指针的，它能够使用一个数组表示而不需要指针。对于数组中的任意的位置i上面的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i+1)中，它的父亲则在位置[i/2]上。因此，这里面不需要指针，而且遍历该树的操作也是非常简单。这种实现的唯一问题在于需要事先确定堆的大小。
一个堆数据结构将由一个数组，一个代表最大值的整数以及当前堆的大小组成。下面是典型的有限队列的声明：
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;
struct HeapStruct{
int Capacity;
int Size;
ElementType *Element;
}
堆序性质
使操作被快速执行的性质是堆序性，由于我们想要找出最小元，因此最小元应该在根上面，那么我们考虑任意子树也是一个堆，这任意节点就应该小于它的所有后裔。
由此，我们得到了堆序的性质。在一个堆中，对于每个节点X，X的父亲中的关键字小于X中的关键字，根节点除外。在例子中，我们假设关键字是整数，虽然可能任意复杂。
根据堆序的性质，最小元总是在根处能够找到，因而FindMin可以以常数时间完成。
PriorityQueue
Initialize(int MaxElements){
PriorityQueue H;
if(MaxElements < MinPQSize){
Error("queue is too small");
}
H = malloc(sizeof(struct HeapStruct));
if(H == NULL){
FatalError("out of space");
}
H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
if(H->Elements == NULL){
FatalError("out of space");
}
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[0] = MinData;
return H;
}
基本的堆序操作
无论从概念上还是实际考虑，执行插入和删除最小元都需要保持堆序性。
Insert(插入)
为了将X插入到空穴中，我们在下一个空闲位置创建一个空穴，否则该堆将不再是完全二叉树。如果X可以放在空穴并不会破坏堆序性，那么插入完成。否则，我们把父节点上面的元素移入空穴，空穴就朝着根的方向上行了一步。继续改过程，知道空穴能够放下X为止。
这种一般的策略叫做上虑，新元素在堆上虑直到找到正确的位置。
插入到一个二叉堆的过程：
void
Inserti(Element X, PriorityQueue H){
int i;
if(IsFull(H)){
Error("Priority queue is full");
return;
}
for(i = ++H->Size; H->Element[i/2] > X; i = i / 2){
H->Elements[i] = H->Emelemts[i/2];
}
H->Elements[i] = X;
}
在实现过程中，我们总可以通过进行反复交换来进行实现，这样就需要3条赋值语句，那么上虑d层的话，交换的次数就需要3d，而在这里仅仅需要d+1次。
如果要插入的元素是性的最小值，那么它将一直被推导顶端。在某一次时，i将是1，我们就需要跳出循环，故我们可以在0位置处放置一个很小的值，来使循环终止，这个值需要小于堆中的任何值，我们称之为标记。
如果新插入的元素是新的最小元，那么这种高度是O(logN)。但是平均来看，执行一次插入平均需要2.607次比较，因此Insert将元素平均上移1.607层。
DeleteMin(删除最小元)
DeleteMin 以类似于插入的方式处理。找出最小元是容易的，问题的关键在于删除它。当我们要要删除一个最小元时，在根节点产生了一个空穴。由于现在堆缺少了一个元素，因此堆中的最后一个元素X必须要移动到该堆的某个地方。如果X可以被放到空穴中，那么DeleteMin就完成了。我们的做法是将空穴两个儿子中的较小者移入空穴，这样就能够把空穴向下推进，重复该步骤直到X可以放在该空穴中。综上，我们的做法是将X放置在从根开始包含最小儿子的一条路径上面的正确的位置。我们将这种策略叫做下虑，并且也可以通过覆盖来避免交换，下面是下虑的过程示意图：
在堆中经常发生的错误是当堆中存在偶数个元素的时候，此时将遇到一个节点只有一个儿子的情况，所以我们必须要考虑节点只有一个儿子的情况，当堆的元素个数是偶数的时候，在每个开始下虑的时候，可将其值大于堆中任何元素的标记放到堆的终端的后面的位置上。下面具体的代码实现：
ElementType
DeleteMin(PriorityQueue H){
int i, Chid;
ElementType MinElement, LastElement;
if(IsEmpty(H)){
return H->Element[0];
}
MinElement = H->Elements[1];
LastElement = H->Element[H->Size--];
for(i = 1; i*2 < H->Size; i = Chid){
Chid = i * 2;
if(Chid != H->Size && H->Elements[Chid+1] < H->Elements[Chid])
Chid++;
if(LastElement > H->Elements[Chid])
H->Elements[i] = H->Elements[Chid];
else
break;
}
H->Elements[i] = LastElement;
return MinELement;
}
平均运行时间为O(logN)。
其他的堆操作
虽然求最小值的操作可以在常数时间完成，但是按照最小元设计的堆对于求最大元方面却是无任何帮助。事实上，一个堆蕴含的关于序的信息很少，若不会整个堆进行线性所受搜索，是不能找出特定元素的，虽然我们知道最大元在树叶上面，但是半数的元素在树叶上面。
构建堆
BuildHeap操作把N个关键字作为输入并把它们放在堆中，可以通过Insert操作进行完成，由于每个Insert操作花费的时间是O(1)，总的时间是O(N)。一般的算法是将N个关键字以任意的顺序放入树中，保持结构特性，然后再开始对父节点进行下虑操作，遍历所有的父节点之后，堆将会满足堆序性。
定理
包含2^(b+1) - 1个节点，高为h的理想二叉树的节点的高度为2^(b+1) - 1 - (b+1)。
证明：高度为b上面的节点有1个，高度b-1上面的节点2个，高度为b-2上面的节点2^2个.....一般的高度b-i上的节点2^i个，所以所有节点的高度的和是：
S = sum(2^i)(b-i)
通过左乘2相减相消就能够求和。
完全树不是理想二叉树，一个完全二叉树节点树是2^b和2^(b+1)之间。
虽然我们得到的结果对证明BulidHeap是线性的而言是充分的，但是高度的和的界却是尽可能强的。
下面是一个完整例程：
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef int ElementType;
typedef struct HeadStruct *PriorityQueue;
#define MinPQSize 10
#define MinData 0
struct HeadStruct{
int Capacity;
int size;
ElementType *Elements;
};
// 优先队列的初始化
PriorityQueue Initialze(int MaxElements){
PriorityQueue H;
if(MaxElements < MinPQSize){
printf("Priority QUeue is too small\n");
}
H = new HeadStruct();
H->Elements = new ElementType[MaxElements + 1];
H->Capacity = MaxElements;
H->size = 0;
H->Elements[0] = MinData;
return H;
}
//优先队列插入元素
void insert(ElementType x, PriorityQueue H){
int i;
if(H == NULL){
printf("Priority queue is Full \n");
return;
}
for(i=++H->size; H->Elements[i/2]>x; i/=2){
H->Elements[i] = H->Elements[i/2];
}
H->Elements[i] = x;
}
//优先队列删除最小元
ElementType DeletMin(PriorityQueue H){
int i, child;
ElementType MinElement, LastElement;
if(H == NULL){
printf("PriorityQueue is null\n");
return H->Elements[0];
}
MinElement = H->Elements[1];
LastElement = H->Elements[H->size--];
for(i=1; 2*i<=H->size; i=child){
child = i*2;
if(child != H->size && H->Elements[child +1] < H->Elements[child]){
child++;
}
if(LastElement > H->Elements[child]){
H->Elements[i] = H->Elements[child];
}else{
break;
}
}
H->Elements[i] = LastElement;
return MinElement;
}
void printfPriorityQueue(PriorityQueue H){
for(int i=1; i<=H->size; i++){
printf("%d ", H->Elements[i]);
}
}
int main(){
PriorityQueue H = Initialze(50);
int list[10] = {13,21,16,24,31,19,68,65,26,32};
for(int i=0; i<10; i++){
insert(list[i], H);
}
insert(14, H);
printfPriorityQueue(H);
int min = DeletMin(H);
printf("min: %d\n", min);
printfPriorityQueue(H);
}
d-堆
d堆是二叉堆的推广，它恰像一个二叉堆，只是所有的节点都有d个儿子(因此，二叉堆是2堆)。d堆显然要比二叉堆浅的多，它将Insert时间改进为O(logdN)。然而，对于大的d，DeleteMin操作费时用的多，因为虽然树浅了，但是d个儿子中的最小者是必须要找出的，使用标准的算法，这会花费d-1次。虽然仍然是一个数组，找出儿子和父亲都有个因子d，除非d是2的幂，否则将会大大的增加运行时间，因为我们不能时间二进制的移位计算了。当优先队列太大不能完全装入主存时，d堆也是很有用的。在这种情况下，d堆能够以于B树大致相同的方式发挥作用。在实践过程中，4-堆可以胜过二叉堆。
除了不能执行Find外，堆的实现的最明显的缺点是：将两个堆合并成一个堆是困难的，这种附加的操作叫做Merge，存在许多的实现堆的方法使得Merge操作的运行时间是O(logN)。
左式堆
设计一种堆结构像二叉树那样高效地支持合并操作(即以O(N)时间处理一次Merge)而且只使用一个数组似乎很困难。原因在于，合并似乎需要把一个数组拷贝到另外一个数组中去，对于相同大小的堆这将花费时间O(N)，正是因为如此，所有支持合并的高级数据结构都需要使用指针。
类似二叉堆那样，左式堆也具有结构性和有序性。事实上，和所有使用的堆一样，左式堆具有时间的堆序性质。左式堆也是二叉树，左式堆和二叉树唯一的区别是：左式堆不是理想平衡的，而实际上是趋向于非常不平衡。
左式堆的性质
我们把任一节点的零路径长Npl定位为从X到一个没有两个儿子的节点的最短路径长。因此，具有0个或者1个儿子的节点Npl为0，而Npl(NULL)=-1。任一节点的零路径长比它的诸儿子节点的零路径长的最小值多1，这个结论也适合用少于两个儿子的节点。
左式堆性质是：对于堆中的每一个节点X，左儿子的零路径长至少与右儿子的零路径长一样大。这个性质实际上超出了平衡的要求，因为它显然更偏向于使树向左增加深度。确实有可能存在左节点形成的长路径构成的树，因此，我们就有了左式堆。左式堆趋向于加深左路径，所以右路径应该短。否则就会存在一条路径上通过某个节点X并取得做儿子，此时X则破坏了左式堆的性质。
在右路径上有r个节点的左式树必然至少有2^r - 1 个节点。
对左式堆的基本操作是合并，插入只是合并的特殊情形，因为我们可以把插入看成是单节点堆与一个大的堆的Merge。
下面是具体的代码实现：
struct TreeNode;
typedef struct TreeNode *PriorityQueue;
struct TreeNode{
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
int Npl;
}
合并左式堆的驱动例程
PriorityQueue
Merge(PriorityQueue H1, PriorityQueue H2){
if(H1 == NULL)
return H2;
if(H2 == NULL)
return H1;
if(H1->Element < H2->Element)
Merge1(H1, H2);
else
Merge1(H2, H1);
}
static PriorityQueue
Merge1(PriorityQueue H1, PriorityQueue H2){
if(H1->Left == NULL)
H1->Left = H2;
else{
H1->Right = Merge(H1->Right, H2);
if(H1->Left->Npl < H1->Right->Npl)
SwapChildren(H1);
H1->Npl = H1->Right->Npl + 1;
}
return H1;
}
左式堆的插入例程
PriorityQueue
Insert1(ElementType X, PriorityQueue H){
PriorityQueue SingleNode;
SingleNode = malloc(sizeof(struct TreeNode));
if(SingNode == NULL){
FatalError("out of space");
}else{
SingleNode->Element = X;
SingleNode->Npl = 0;
SingleNode->Left = SingleNode->Right = NULL;
H = Merge(SingleNode, H);
}
return H;
}
PriorityQueue
DeleteMin1(PriorityQueue H){
PriorityQueue LeftHeap, RightHeap;
if(IsEmpty(H)){
Error("empty");
return H;
}
LeftHeap = H->Left;
RRightHeap = H->Right;
free(H);
return Merge(LeftHeap, RightHeap);
}
斜堆
斜堆是左式堆的自调节形式，实现起来及其简单，斜堆和左式堆的关系类似于伸展树和AVL树间的关系。斜堆是具有堆序的二叉树，但是不存在堆树的结构的限制。不同于左式堆，关于任意节点的零路径长的任何信息都不保存。斜堆的左路径在任意时刻都可以任意长，因此所有操作的最坏情形运行时间均为O(N)。然而，正如伸展树一样，任意M次操作，总的最坏运行时间是O(MlogN)。因此斜堆每次操作的摊还时间是O(logN)。
二项队列
虽然左式堆和斜堆每次操作花费O(logN)时间，这有效地支持了合并，插入和DeleteMin。但是还有改进的余地，因为二叉堆每次操作花费常数平均时间支持插入。二项队列支持所有这三种操作，每次操作的最坏情形运行时间是O(logN)，而插入操作平均花费常数时间。
二项队列不同于我们已经看到的所有优先队列的实现之处是，一个二项队列不是一颗堆序的树，而是堆序树的集合，称为森林。堆序树中的每一个树都是有约束的形式，叫二项树。每个高度上至多存在一颗二项树。高度为0的二项树是一颗单节点树；高度为k的二项树Bk通过一颗二项树Bk-1附接到另一颗二项树Bk-1的根上。下图显示了二项树B0，B1，B2，B3。
加载全部内容