当前位置 博文首页 > CrazyCatJack：《数据结构与算法分析》学习笔记-第六章-优先队列
队列中的某些成员有更高的优先级，需要优先执行或者尽快执行完毕
优先队列允许至少有两种操作的数据结构：
堆具有结构性和堆序性，而对堆的一次操作可能会破坏这两个性质，因此堆的操作必须要到堆的所有性质都被满足时才能停止
typedef struct PriorityQueueNode {
int Capacity;
int Size;
ElementType *Elements;
} PriorityQueueNode_T;
typedef PriorityQueueNode_T *PtrToPriorityQueue;
PtrToPriorityQueue
Initialize(int MaxElements)
{
PtrToPriorityQueue Q = NULL;
Q = (PtrToPriorityQueue)malloc(sizeof(struct PriorityQueueNode));
if (Q == NULL) {
printf("Q malloc failed\n");
return NULL;
}
memset(Q, 0, sizeof(struct PriorityQueueNode));
Q->Capacity = MaxElements;
Q->Size = 0;
Q->Elements = (ElementType *)malloc(sizeof(ElementType) * (Q->Capacity + 1));
if (Q->Elements == NULL) {
if (Q != NULL) {
printf("Q->Elements malloc failed\n");
free(Q);
}
}
memset(Q->Elements, 0, sizeof(ElementType) * (Q->Capacity + 1));
Q->Elements[0] = MINKEYVALUE;
return Q;
}
void
Insert(PtrToPriorityQueue Q, ElementType X)
{
if (IsFull(Q)) {
printf("PtrToPriorityQueue is full\n");
return;
}
int cnt;
for (cnt = ++Q->Size; Q->Elements[cnt / 2] > X; cnt /= 2) {
Q->Elements[cnt] = Q->Elements[cnt / 2];
}
Q->Elements[cnt] = X;
}
ElementType
DeleteMin(PtrToPriorityQueue Q)
{
if (IsEmpty(Q)) {
printf("PtrToPriorityQueue is empty\n");
return Q->Elements[0];
}
int cnt, Child;
ElementType MinKeyValue = Q->Elements[1];
ElementType LastKeyValue = Q->Elements[Q->Size--];
for (cnt = 1; 2 * cnt <= Q->Size; cnt = Child) {
Child = 2 * cnt;
if (Child < Q->Size && Q->Elements[Child] > Q->Elements[Child + 1]) {
Child++;
}
if (LastKeyValue > Q->Elements[Child]) {
Q->Elements[cnt] = Q->Elements[Child];
} else {
break;
}
}
Q->Elements[cnt] = LastKeyValue;
return MinKeyValue;
}
for (i = N / 2; i > 0; i--) {
PercolateDown(i);
}
优先队列可以有效地用于几个图论算法的实现中
如果有C个顾客（2C个事件）和k个出纳员，那么模拟的运行时间将会是O(Clog(k + 1))，因为计算和处理每个事件花费O(logH)，其中H = K + 1为堆的大小
对左式堆的基本操作是合并。插入只是合并的特殊情形，因此我们可以把插入看成是单节点堆与一个大的堆的Merge。
struct TreeNode {
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
}
左式堆和斜堆每次操作花费O(logN)实践。有效的支持了合并、插入和DeleteMin。因为二叉堆每次操作花费常数平均时间支持插入。二项队列支持所有这三种操作，每次操作的最坏情形运行时间为O(logN)，而插入操作花费常数时间
DeleteMin操作需要快速找出根的所有子树的能力，因此，需要一般树的表示方法：每个结点的儿子都存在一个链表中，而且每个节点都有一个指向它的第一个儿子（如果它有的话）的指针。还要求，诸儿子按照它们的子树的大小排序。需要保证能够很容易的合并两棵树。当两棵树被合并时，其中一棵树作为儿子被加到另一棵树上。由于这棵新树将是最大的子树，因此，以大小递减的方式保持这些子树事有意义的。只有这时，我们才能有效地合并两颗二项树，从而合并两个二项队列。二项队列将是二项树的数组。总之，二项树的每一个节点将包含数据、第一个儿子以及右兄弟。二项树中的诸儿子以递减次序排列
typedef struct BinNode *Position;
typedef struct Collection *BinQueue;
struct BinNode
{
ElementType Element;
Position LeftChild;
Position NextSibling;
}
struct Collection
{
int CurrentSize;
BinTree TheTrees[MaxTrees];
}
BinTree
Merge(BinTree T1, BinTree T2)
{
if (T1->Element > T2->Element) {
return Merge(T2, T1);
}
T2->NextSibling = T1->LeftChild;
T1->LeftChild = T2;
return T1;
}
BinQueue
Merge(BinQueue H1, BinQueue H2)
{
BinTree T1, T2, Carry = NULL;
int i, j;
if (H1->CurrentSize + H2->CurrentSize > Capacity) {
printf("Merge would exceed capacity\n");
}
H1->CurrentSize += H2->CurrentSize;
for (i = 0; j = 1; j <= H1->CurrentSize; i++, j*= 2) {
T1 = H1->TheTrees[i];
T2 = H2->TheTrees[i];
switch(!!T1 + 2 * !!T2 + 4 * !!Carry) {
case 0: /* No trees */
case 1: /* Only H1 */
break;
case 2: /* Only H2 */
H1->TheTrees[i] = T2;
H2->TheTrees[i] = NULL;
break;
case 4: /* Only Carry */
H1->TheTrees[i] = Carry;
Carry = NULL;
break;
case 3: /* H1 and H2 */
Carry = CombineTrees(T1, T2);
H1->TheTrees[i] = H2->TheTrees[i] = NULL;
break;
case 5: /* H1 and Carry */
Carry = CombineTrees(T1, Carry);
H1->TheTrees[i] = NULL;
break;
case 6: /* H2 and Carry */
Carry = CombineTrees(T2, Carry);
H2->TheTrees[i] = NULL;
break;
case 7: /* All three */
H1->TheTrees[i] = Carry;
Carry = CombineTrees(T1, T2);
H2->TheTrees[i] = NULL;
break;
}
}
return H1;
}
ElementType
DeleteMin(BinQueue H)
{
int i, j;
int MinTree;
BinQueue DeletedQueue;
Position DeletedTree, OldRoot;
ElementType MinItem;
if (IsEmpty(H)) {
printf("Empty binomial queue\n");
return -Infinity;
}
MinTtem = Infinity;
for (i = 0; i < MaxTrees; i++) {
if (H->TheTrees[i] && H->TheTrees[i]->Element < MinItem) {
/* Update minimum */
MinItem = H->TheTrees[i]->Element;
MinTree = i;
}
}
DeletedTree = H->TheTrees[MinTree];
OldRoot = DeletedTree;
DeletedTree = DeletedTree->LeftChild;
free(OldRoot);
DeletedQueue = Initialize();
DeletedQueue->CurrentSize = (1 << MinTree) - 1;
for (j = MinTree - 1; j >= 0; j--)
{
DeletedQueue->TheTrees[j] = DeletedTree;
DeletedTree = DeletedTree->NextSibling;
DeletedQueue->TheTrees[j]->NextSibling = NULL;
}
H->TheTrees[MinTree] = NULL;
H->CurrentSize -= DeletedQueue->CurrentSize + 1;
Merge(H, DeletedQueue);
return MinItem;
}
本文作者: CrazyCatJack
本文链接: https://www.cnblogs.com/CrazyCatJack/p/13340038.html
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
关注博主:如果您觉得该文章对您有帮助，可以点击文章右下角推荐一下，您的支持将成为我最大的动力！
