二项最大堆 C語言 找最大

Question

这是我参考各种假码写出来的 二项最大堆 但找最大那个函式不知道为什么有问题 我插入0 to 49 应该要从印49 to 0

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题：为什么二项最大堆的"找最大"函数没有按预期工作？

解决方案：

1. 分析问题所在。根据问题描述，当插入0和49这两个元素后，应该从小到大依次打印出490。然而，实际运行中发现打印的顺序有问题。

2. 检查代码中关于最大堆的部分。代码中的函数extract_max应该是找出优先级最高的节点进行打印，但可能存在问题。

3. 分析代码中的问题：

   • 在函数extract_max中，找到优先级最高的节点后，先将其打印出来，然后将其从堆中移除。然而，在移除节点后，没有重新调整堆的结构，导致堆结构紊乱。

4. 修改代码的解决方案：

   • 在函数extract_max中，当找到优先级最高的节点后，需要重新调整堆的结构，使其保持最大堆的性质。

   • 在调整堆的结构时，可以先使用递归方法将当前节点的子节点都翻转，并将翻转后的链表保存在last数组中。然后将翻转后的链表连接到当前节点的兄弟节点之后。

   • 最后，需要更新堆的根节点，即将原先最大的节点移除后，新的最大节点应为原先最大节点的兄弟节点或子节点（如果有的话）。

5. 修改后的代码如下：

void reverse_list(Node* node, Node* last[], int printer)
{
    if(node->sibling != NULL)
    {
        reverse_list(node->sibling, last, printer);
        node->sibling->sibling = node;
    }
    else
    {
        last[printer] = node;
    }
}

Node* extract_max(Node* heap, Node* last[], int printer)
{
    int max = INT_MIN;
    int job = 0;
    Node* temp = NULL;
    Node* current = heap;
    Node* Hr = NULL;
    Node* p = NULL;
    if(current == NULL)
    {
        printf("no documents in queue\n");
        return NULL;
    }
    p = current;
    max = p->priority;
    job = p->job_id;

    while(p->sibling != NULL)
    {
        if(p->sibling->priority > max)
        {
            max = p->sibling->priority;
            job = p->sibling->job_id;
            temp = p;
            current = p->sibling;
        }
        p = p->sibling;
    }
    
    if(temp == NULL && current->sibling == NULL)
    {
        heap = NULL;
    }
    else if(temp == NULL)
    {
        heap = current->sibling;
    }
    else if(temp->sibling == NULL)
    {
        temp = NULL;
    }
    else
    {
        temp->sibling = current->sibling;
    }
    
    printf("%d printed\n", job);
    count[printer]--;

    if(current->child != NULL)
    {
        reverse_list(current->child, last, printer);
        current->child->sibling = NULL;
    }

    for(int i=1; last[i]!=NULL; i++)
    {
        heap = insert(heap, last[i]);
    }
    
    return heap;
}

希望以上解决方案能帮到你！如果还有其他问题，请随时提问。