Untitled

#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;
}