Untitled
unknown
plain_text
a year ago
8.0 kB
3
Indexable
#include <stdio.h> #include <stdlib.h> typedef struct BinomialHeapNode { long long priority; // 优先级 long long jobId; // 工作ID long long degree; // 此节点在二项树中的度数 struct BinomialHeapNode *parent; struct BinomialHeapNode *child; struct BinomialHeapNode *sibling; } BinomialHeapNode; typedef struct BinomialHeap { long long jobCount; BinomialHeapNode *head; // 指向最小度数的二项树的根 } BinomialHeap; BinomialHeapNode* createNode(long long priority, long long jobId) { BinomialHeapNode *newNode = (BinomialHeapNode *)malloc(sizeof(BinomialHeapNode)); if (newNode == NULL) { printf("Memory allocation error\n"); exit(1); } newNode->priority = priority; newNode->jobId = jobId; newNode->degree = 0; newNode->parent = newNode->child = newNode->sibling = NULL; return newNode; } BinomialHeap* createHeap() { BinomialHeap *heap = (BinomialHeap *)malloc(sizeof(BinomialHeap)); if (heap == NULL) { printf("Memory allocation error\n"); exit(1); } heap->jobCount = 0; heap->head = NULL; return heap; } BinomialHeapNode* binomialLink(BinomialHeapNode *a, BinomialHeapNode *b) ; BinomialHeap* binomialHeapUnion(BinomialHeap *heap, BinomialHeap *tempHeap) ; BinomialHeapNode* mergeHeaps(BinomialHeapNode *heap, BinomialHeapNode *tempHeap) ; // 合并两个度数相同的二项树 BinomialHeapNode* binomialLink(BinomialHeapNode *a, BinomialHeapNode *b) { b->parent = a; b->sibling = a->child; a->child = b; a->degree++; return a; } // 插入一个节点到堆中 void binomialHeapInsert(BinomialHeap *heap, long long priority, long long jobId) { BinomialHeapNode *node = createNode(priority, jobId) ; BinomialHeap *tempHeap = createHeap(); tempHeap->head = node; BinomialHeap *newHeap = binomialHeapUnion(heap, tempHeap); heap->head = newHeap->head; heap->jobCount++; free(newHeap); // 清理临时堆的空间 } BinomialHeap* binomialHeapUnion(BinomialHeap *heap, BinomialHeap *tempHeap) { if (heap->head == NULL) { return tempHeap; } if(tempHeap->head == NULL) { return heap ; } BinomialHeap *newHeap = createHeap(); newHeap->head = mergeHeaps(heap->head, tempHeap->head); BinomialHeapNode *prev = NULL, *current = newHeap->head; BinomialHeapNode *next = current->sibling; while (next != NULL) { if ((current->degree != next->degree) || (next->sibling != NULL && next->sibling->degree == current->degree)) { prev = current; current = next;} else { if (current->priority <= next->priority) { current->sibling = next->sibling; binomialLink(current, next); } else { if (prev == NULL) { newHeap->head = next; } else { prev->sibling = next; } binomialLink(next, current); current = next; } } next = current->sibling; } return newHeap; } BinomialHeapNode* mergeHeaps(BinomialHeapNode *heap, BinomialHeapNode *tempHeap) { if (heap == NULL) return tempHeap; if (tempHeap == NULL) return heap; BinomialHeapNode *head; BinomialHeapNode *tail; // 初始化头部,确保 head 指向度数较小的树的根 if (heap->degree <= tempHeap->degree) { head = heap; heap = heap->sibling;} else { head = tempHeap;tempHeap = tempHeap->sibling; } tail = head; // 遍历两个堆,按度数顺序合并链表 while (heap && tempHeap) { if (heap->degree <= tempHeap->degree) { tail->sibling = heap; heap = heap->sibling; } else { tail->sibling = tempHeap; tempHeap = tempHeap->sibling; } tail = tail->sibling; } // 将剩余部分链表连接到合并后的链表尾部 tail->sibling = (heap != NULL) ? heap : tempHeap; return head; } BinomialHeapNode* binomialHeapExtractMax(BinomialHeap *H) { // 1. 找到具有最大键值的二项树 BinomialHeapNode *maxNode = NULL; BinomialHeapNode *maxNodePrev = NULL; BinomialHeapNode *current = H->head; BinomialHeapNode *prev = NULL; while (current != NULL) { if (maxNode == NULL || current->priority > maxNode->priority) { maxNode = current; maxNodePrev = prev; } prev = current; current = current->sibling; } if (maxNode == NULL) { return NULL;} // 2. 从根链表中移除最大二项树 if (maxNodePrev == NULL) { H->head = maxNode->sibling; } else { maxNodePrev->sibling = maxNode->sibling ; } // 3. 逆转最大二项树的子节点链表并删除父指针 BinomialHeapNode *child = maxNode->child; // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! BinomialHeapNode *reversedChildren = NULL; while (child != NULL) { BinomialHeapNode *next = child->sibling; child->sibling = reversedChildren; child->parent = NULL; // 删除父指针 reversedChildren = child; child = next; } // 4. 创建一个新堆,其中只包含最大节点的子节点 BinomialHeap *newHeap = createHeap(); newHeap->head = reversedChildren; // 5. 将新堆与原堆合并 H = binomialHeapUnion(H, newHeap); free(newHeap); // 清理新堆结构,但子节点已合并进原堆 // 6. 返回提取出的最大节点 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! H->jobCount--; return maxNode; } void freeBinomialTree(BinomialHeapNode *node) { if (node == NULL) { return; } // 递归地释放所有子节点 freeBinomialTree(node->child); // 递归地释放所有兄弟节点 freeBinomialTree(node->sibling); // 最后释放当前节点 free(node); } void freeBinomialHeap(BinomialHeap *heap) { if (heap == NULL) { return; } // 释放堆中的每棵二项树 freeBinomialTree(heap->head); // 释放堆结构本身 free(heap); } int main() { //representing the number of printers long long printer_num, operation_num; scanf("%lld %lld", &printer_num, &operation_num); BinomialHeap **printers = (BinomialHeap **)malloc(printer_num * sizeof(BinomialHeap *)); for (long long i = 0; i < printer_num; i++) { printers[i] = createHeap(); } for (long long i = 0; i < operation_num; i++) { int operation; scanf("%d", &operation); if (operation == 1) { // 添加操作 long long jobId, priority, printerId; scanf("%lld %lld %lld", &jobId, &priority, &printerId); binomialHeapInsert(printers[printerId - 1], priority, jobId); printf("%lld jobs waiting on printer %lld\n", printers[printerId - 1]->jobCount, printerId); // 输出队列中的作业数 } else if (operation == 2) { // 打印操作 long long printerId; scanf("%lld", &printerId); BinomialHeapNode *maxNode = binomialHeapExtractMax(printers[printerId - 1]); if (maxNode != NULL) { printf("%lld printed\n", maxNode->jobId); free(maxNode); } else { printf("no documents in queue\n"); } } else if (operation == 3) { // 移动操作 int printerId1, printerId2; scanf("%lld %lld", &printerId1, &printerId2); BinomialHeap *newHeap = binomialHeapUnion(printers[printerId1 - 1], printers[printerId2 - 1]); printers[printerId2 - 1]->head = newHeap->head; printers[printerId1 - 1]->head = NULL; // 输出移动后队列中的作业数 printf("%lld jobs waiting on printer %lld after moving\n", printers[printerId2 - 1]->jobCount, printerId2); } } // 清理分配的内存 for (long long i = 0; i < printer_num; i++) { freeBinomialHeap(printers[i]); } free(printers); return 0; }
Editor is loading...
Leave a Comment