C - 如何使用带决胜局的二进制堆实现优先级队列？

Question

我必须在 C 语言中使用二叉堆实现优先级队列以完成大学作业。程序应该从输入中获取 n 个值，当值为 0 时，它应该打印 ID 号(因此，如果作为第 5 个元素添加的任务具有最高优先级 7，则打印“5”)并从中删除最高优先级任务队列，当 value>0 时，它应该添加新节点。为了实现 ID 和优先级，我使用了结构数组。

任务会很简单，如果元素的优先级相同，它也应该打印较低的 ID... 我已经完成了研究，但我设法找到的唯一建议是修改典型堆函数(insertkey、heapify)的片段以同时查找元素的 ID。我试过这样做，但我不知道出了什么问题 - 元素仍然没有按照我希望的方式排序。如果有任何建议和提示，我将不胜感激!

代码:

#include <stdio.h>

#define SIZE 99999

int heapsize = 0;
int count = 0;

struct pqueue
{
    int priority;
    int id;
};

struct pqueue A[SIZE];


void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}


void initializearray()
{
    for(int i=0; i<SIZE; i++)
    {
        A[i].priority = 0;
        A[i].id = 0;
    }
}

void printheap(); //prototype of debugging function



int left(int i)
{
    return (i * 2) + 1;
}



int right(int i)
{
    return (i * 2) + 2;
}

int parent(int i)
{
    return ((i - 1) / 2);
}


void insertkey(int z)
{
    heapsize++;
    int i = heapsize - 1;
    A[i].priority = z;
    count++;
    A[i].id = count;

    while (i != 0 && A[parent(i)].priority < A[i].priority)
    {
        swap(&A[i].priority, &A[parent(i)].priority);
        swap(&A[i].id, &A[parent(i)].id);
        i = parent(i);
    }


    i = heapsize-1;
    while(i != 0 && A[parent(i)].priority == A[i].priority && A[parent(i)].id > A[i].id )
        {
        swap(&A[i].priority, &A[parent(i)].priority);
        swap(&A[i].id, &A[parent(i)].id);
        i = parent(i);
        }

     //   printheap();
}



void maxheapify(int i)
{
    int l = left(i);
    int r = right(i);
    int largest;

    if (l <= heapsize && A[l].priority >= A[i].priority)
    {
        largest = l;

        if(A[l].priority == A[i].priority)
        {
            if(A[l].id < A[i].id)
            {
                largest = l;
            }

            else
            {
                largest = i;
            }
        }

    }

    else
    {
        largest = i;
    }

    if (r <= heapsize && A[r].priority >= A[largest].priority)
    {
        largest = r;

        if(A[r].priority == A[largest].priority)
        {
            if(A[r].id < A[largest].id)
            {
                largest = r;
            }
        }
    }

    if (largest != i)
    {
        swap(&A[i].priority, &A[largest].priority);
        swap(&A[i].id, &A[largest].id);
        maxheapify(largest);
    }
}

int extractmax()
{
    int max = A[0].id;
    A[0].priority = A[heapsize-1].priority;
    A[0].id = A[heapsize-1].id;
    heapsize--;
    //printheap();
    maxheapify(0);
    return max;
}

void printheap() // debug function
{
    for(int i = 0; i < heapsize; i++)
    {
        printf("prio %d id %d \n", A[i].priority, A[i].id);
    }
}


int main()
{
    int n;
    int z;

    initializearray();
    scanf("%d", &n);

    for(int i=0; i<n; i++)
    {
        scanf("%d", &z);

        if(z != 0)
        {
            insertkey(z);
        }

        else
        {
            int local = extractmax();

            if(local != 0 && heapsize+1 != 0)
            {
                printf("%d\n", local);
                // printheap();
            }
        }
    }

    return 0;
}

示例输入:

7

3 0 0 2 8 8 0

输出:

1

3

示例输入(问题来了:)

10

1 1 1 1 2 0 0 0 0 0

输出:

5

3

2

4

1

预期输出:

5

1

2

3

4

感谢您的宝贵时间!

Answer 1

与其将逻辑直接合并到堆实现中，不如编写一个比较函数，在优先级相同的情况下考虑 id:

int pqless(const struct pqueue *a, const struct pqueue *b)
{
    if (a->priority < b->priority) return 1;
    if (a->priority > b->priority) return 0;

    return (a->id > b->id);
}

如果 a 的优先级低于 b，则此函数返回 true。如果两个优先级相等，如果 a 的 id 小于 b 的，则返回 true。

现在更新您的堆代码。无论您在原始代码中比较优先级，现在只需调用该函数即可:

void insertkey(int z)
{
    int i = heapsize++;

    A[i].priority = z;
    A[i].id = ++count;

    while (i != 0 && pqless(&A[parent(i)], &A[i])) {
        swap(&A[i].priority, &A[parent(i)].priority);
        swap(&A[i].id, &A[parent(i)].id);
        i = parent(i);
    }
}

void maxheapify(int i)
{
    int l = left(i);
    int r = right(i);
    int largest = i;

    if (l <= heapsize && !pqless(&A[l], &A[i])) largest = l;
    if (r <= heapsize && !pqless(&A[r], &A[largest]))largest = r;

    if (largest != i) {
        swap(&A[i].priority, &A[largest].priority);
        swap(&A[i].id, &A[largest].id);
        maxheapify(largest);
    }
}