Как реализовать приоритет очереди, используя двоичную кучу с тай-брейкером?

Question

Я должен реализовать приоритетную очередь, используя двоичную кучу в C для университетского назначения. Программа должна получить n значений из ввода, когда значение равно 0, она должна напечатать идентификационный номер (таким образом, если задача, которая была добавлена ​​как 5-й элемент, имеет наивысший приоритет 7, вывести "5") и удалить задачу с наивысшим приоритетом из очереди, а при значении>0 следует добавить новый узел. Для реализации идентификаторов и приоритетов я использовал массивы структур.

Задача была бы довольно простой, если бы не тот факт, что она должна также печатать более низкие идентификаторы, если приоритет элементов одинаков... Я провел исследование, но единственный совет, который мне удалось найти, - это изменить фрагменты типичных функций кучи (insertkey, heapify) для поиска идентификатора элемента. Я пытался сделать это, но я понятия не имею, что пошло не так - элементы все еще не отсортированы так, как я хочу, чтобы они были. Буду благодарен за любые советы и подсказки!

Код:

#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

Вместо того, чтобы включать логику непосредственно в реализацию кучи, напишите функцию сравнения, которая рассматривает идентификатор, если приоритеты совпадают:

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

Эта функция возвращает true, если aприоритет меньше b"S. Если оба приоритета равны, он возвращает истину, если aИдентификатор меньше, чем b"S.

Теперь обновите свой код кучи. Где бы вы ни сравнивали приоритеты в исходном коде, теперь просто вызовите функцию:

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