Untitled

#include <stdio.h>
#include <stdlib.h>

typedef struct BinomialTree {
    long long priority;
    long long degree;
    long long jobID ; 
    struct BinomialTree *parent;
    struct BinomialTree *child;
    struct BinomialTree *sibling;
} BinomialTree;

typedef struct BinomialHeap {
    long long jobCount;
    BinomialTree *root;  // 指向最高階的二項樹
} BinomialHeap;

BinomialTree* createTree(long long priority, long long jobId) {
    BinomialTree *newTree = (BinomialTree *)malloc(sizeof(BinomialTree));
    if (newTree == NULL) { printf("Memory allocation error\n"); exit(1); }
    newTree->priority = priority; newTree->jobID = jobId;
    newTree->degree = 0; newTree->parent = newTree->child = newTree->sibling = NULL;
    return newTree;
}

BinomialHeap* createHeap() {
    BinomialHeap *heap = (BinomialHeap *)malloc(sizeof(BinomialHeap));
    if (heap == NULL) { printf("Memory allocation error\n"); exit(1); }
    heap->jobCount = 0; heap->root = NULL;
    return heap;
}

BinomialHeap* mergeHeaps(BinomialHeap *h1, BinomialHeap *h2);

void insert(BinomialHeap **heap, long long jobID, long long key) {
    // Increment job count in the actual heap.
    // Create a new tree with the given job and priority.
    BinomialTree* newTree = createTree(key, jobID);

    // Create a temporary heap and set its root to the new tree.
    BinomialHeap *tempHeap = createHeap();
    tempHeap->root = newTree;

    // Merge the new heap with the existing heap pointed to by heap.
    *heap = mergeHeaps(*heap, tempHeap);

    printf("(*heap)->root %lld %lld\n", (*heap)->root->jobID, (*heap)->root->priority);
}

BinomialHeap* mergeHeaps(BinomialHeap *h1, BinomialHeap *h2) {

    if (h1->root==NULL) {return h2;} 
    if (h2->root==NULL) return h1;

printf("Merging heaps...\n"); 
    BinomialTree *prev = NULL, *next = NULL, *t1 = h1->root, *t2 = h2->root;
    
    BinomialHeap *mergedHeap = createHeap();

    // 先將 root 指向較小階數的樹
    if (t1->degree <= t2->degree) { mergedHeap->root = t1; t1 = t1->sibling; }
    else { mergedHeap->root = t2; t2 = t2->sibling; }

    if(mergedHeap->root != NULL) next = mergedHeap->root;

    // 合併階數相同的樹
    while (t1 && t2) {
        if (t1->degree <= t2->degree) {
            next->sibling = t1;
            t1 = t1->sibling;
        } else {
            next->sibling = t2;
            t2 = t2->sibling;
        }
        next = next->sibling;
    }

    // 將剩餘的樹接到最後
    if (t1) next->sibling = t1; 
    if (t2) next->sibling = t2;

    // 處理潛在的進位
    next = mergedHeap->root;
    while (next && next->sibling) {

        if (next->degree == next->sibling->degree) {

            BinomialTree *sib = next->sibling;
            if (sib->sibling && sib->degree == sib->sibling->degree) {next = next->sibling;} 

            else {
                if (next->priority > sib->priority) {
                    next->sibling = sib->sibling;
                    sib->parent = next;
                    sib->sibling = next->child;
                    next->child = sib;
                    next->degree++;
                } else {
                    if (prev) {prev->sibling = sib;}
                    else { mergedHeap->root = sib; }
                    
                    next->parent = sib;
                    next->sibling = sib->child;
                    sib->child = next;
                    sib->degree++;
                    next = sib;
                }
            }
        } else {
            prev = next;
            next = next->sibling;
        }
    }
    mergedHeap->jobCount = h1->jobCount + h2->jobCount;
    return mergedHeap;
}

BinomialTree* binomialHeapExtractMax(BinomialHeap *H) {
    if (!H || !H->root) return NULL;  // 确保堆存在且非空

    // 查找具有最大优先级的根节点
    BinomialTree *maxTree = NULL, *maxPrev = NULL, *current = H->root, *prev = NULL;
    long long maxPriority = -1;  // 你可以根据实际情况调整最小值

    while (current != NULL) {
        if (current->priority > maxPriority) {
            maxPriority = current->priority;
            maxTree = current;
            maxPrev = prev;
        }
        prev = current;
        current = current->sibling;
    }

    if (maxTree == NULL) return NULL;

    // 如果最大节点是第一个节点
    if (maxPrev == NULL) {
        H->root = maxTree->sibling;
    } else {
        maxPrev->sibling = maxTree->sibling;  // 移除最大根节点的二项树
    }

    // 反转最大根节点的子树，准备合并
    BinomialTree *child = maxTree->child;
    BinomialTree *temp = NULL;
    BinomialHeap *newHeap = createHeap();
    newHeap->root = NULL;
    BinomialTree *sibling;

    while (child != NULL) {
        sibling = child->sibling;
        child->sibling = newHeap->root;
        child->parent = NULL;  // 清除父指针
        newHeap->root = child;
        child = sibling;
    }

    // 合并剩余的堆和新的堆
    H = mergeHeaps(H, newHeap);
    H->jobCount--;

    return maxTree;  // 返回被删除的最大节点
}

void freeBinomialTree(BinomialTree *node) {
    if (node == NULL) {
        return;
    }
    // 递归地释放所有子节点
    freeBinomialTree(node->child);
    // 递归地释放所有兄弟节点
    freeBinomialTree(node->sibling);
    // 最后释放当前节点
    free(node);
}

void freeBinomialHeap(BinomialHeap *heap) {
    if (heap == NULL) {
        return;
    }
    // 释放堆中的每棵二项树
    freeBinomialTree(heap->root);
    // 释放堆结构本身
    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);

            insert(&printers[printerId - 1], jobId, priority);

            printf("%lld jobs waiting on printer %lld\n", printers[printerId - 1]->jobCount, printerId); // 输出队列中的作业数
        }  

        // else if (operation == 2) { // 打印操作
        //     long long printerId;
        //     scanf("%lld", &printerId);
        //     BinomialTree *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;
}