is there a way to implement priority queue with binary heap but the values are structs themselves?

Question

I have an assignment that asks me to implement a priority queue with binary heap in c. I have a problem because basically, the input data that we get looks like this:

7 - number of occurences

3 4 0 5 8 0 0 - occurences, if the number is 0 that means the number with highest priority is removed (or if priorities are the same, the one thats been there the longest - i guess just basic priority queue)

however, whats important is that the output needs to be the numbers of the assignments, not the priorities, so in the example above it would be 2, 4, 3

im a beginner so the only way i can think of to do this is using structs for each of the assignments, with two ints - one for number of assignment, one for its priority

the problem im having is with the input, if all i get is numbers then how can i make each struct recognizable and be able to sort it into a heap later? i thought of maybe creating temporary structs and then adding them to a list, but how can i pass the values to the temporary structs?

this is the code i have by now, i didnt do all the functions yet because first i want to be able to store and access the values properly

#include <stdio.h>

struct zadanie
{
 int nr;
 int priorytet;
 };



int main()
{
int events;
scanf("%d", &events);

//struct zadanie heap[events];

int n = 1;

for (int i=0; i<events; i++)
{
    int x;
    scanf("%d", &x);
    if (x != 0)
    {
        struct zadanie tmp;
        &tmp.nr = n;
        &tmp.priorytet = x;
        n += 1;
    }
    else
    {
        
    }
    
}
}

i tried using these questions as a guide: Using scanf for multiple data with structures How do i assign a value using scanf to a member of a Struct type variable whose array is created dynamically but i couldnt work out how to make the answers work for me

*edit: i got the code to work for inserting the values, right now im having a problem with passing the structs inside of the array to a heapify function i know its probably something to do with pointers, but i played around with it for a bit and all i got was a "request for member ‘priorytet’ in something not a structure or union" error code

my code so far:

#include <stdio.h>

int size = 0;

struct zadanie
{
 int nr;
 int priorytet;
};

void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}

void kopcenie(int heap[], int size, int i)
{
if (size == 1){
    return;
}
else
{
    int max = i;
    int l = 2*i;
    int p = 2*i+1;
    if (l < size && heap[l].priorytet > heap[max].priorytet)
        max = l;
    if (p < size && heap[p].priorytet > heap[max].priorytet)
        max = p;
    if (max != i) 
    {
        swap(&heap[i], &heap[max]);
        kopcenie(heap, size, max);
    }
}
}

int main()
{
int events;
scanf("%d", &events);

struct zadanie heap[events];

int n = 1;

for (int i=0; i<events; i++)
{
    int x;
    scanf("%d", &x);
    if (x != 0)
    {
        struct zadanie tmp;
        tmp.nr = n;
        tmp.priorytet = x;
        heap[n] = tmp;
        n += 1;
        
    }
}

}

**another edit - i got it to work, Passing an array of structs in C helped me a lot

Answer 1

i got some things working, however the answer is not right on some data, for example for 10 1 1 1 1 2 0 0 0 0 0 the answer should be 5 1 2 3 4 but for me its 1 5 2 3 4, any idea what might be wrong? here's my finished code:

#include <stdio.h>


struct zadanie
{
  int nr;
  int priorytet;
};

void swap(struct zadanie *a, struct zadanie *b)
{
struct zadanie temp = *b;
*b = *a;
*a = temp;
}

void kopcenie(struct zadanie heap[], int size, int i)
{
if (size == 1){
    return;
}
else
{
    int max = i;
    int l = 2*i;
    int p = 2*i+1;
    if ((l < size) && (heap[l].priorytet > heap[max].priorytet || 
(heap[l].priorytet == heap[max].priorytet && heap[l].nr < heap[max].nr)))
        max = l;
    if ((p < size) && (heap[p].priorytet > heap[max].priorytet) || 
(heap[p].priorytet == heap[max].priorytet && heap[p].nr < heap[max].nr)))
        max = p;
    if (max != i) 
    {
        swap(&heap[i], &heap[max]);
        kopcenie(heap, size, max);
    }
}
}

void wstaw(struct zadanie heap[], int *size, struct zadanie i)
{
if (*size == 0) {
heap[0] = i;
*size = 1;
} 
else 
{
heap[*size] = i;
*size += 1;
for (int i = *size / 2 - 1; i >= 0; i--) 
{
  kopcenie(heap, *size, i);
}
}
}

void usun(struct zadanie heap[], int *size) {
if (*size == 0)
    return;

printf("%d\n", heap[0].nr);
swap(&heap[0], &heap[*size - 1]);
*size -= 1;
for (int i = *size / 2 - 1; i >= 0; i--) {
    kopcenie(heap, *size, i);
}

}

int main()
{

int size = 0;
int events;
scanf("%d", &events);

struct zadanie heap[events];

int n = 1;

for (int i=0; i<events; i++)
{
    int x;
    scanf("%d", &x);
    if (x != 0)
    {
        struct zadanie tmp;
        tmp.nr = n;
        tmp.priorytet = x;
        wstaw(heap, &size, tmp);
        n+=1;
        
    }
    else
    {
        usun(heap, &size);
    }
}

}

Answer 2

I have an assignment that asks me to implement a priority queue
with binary heap in c. I have a problem because basically, the
input data that we get looks like this...

This 1st paragraph is already a sign of problems. There is no relation between the 2 sentences: priority queue implemented via binary heap is one thing.

The particular form of input data has nothing to do with the task and is other thing.

You should not mix them. Do it only leads to problems.

TL;DR;: I will write below a possible implementation for this. Since I will be coding along this can be a log post. Yes, full code is at the end.

*

the input for the problem

7 - number of occurences

3 4 0 5 8 0 0 - occurences, if the number is 0 that means the number
with highest priority is removed (or if priorities are the same, the
one thats been there the longest - i guess just basic priority queue)

Ian Abbott, kindly left an interpretation of this and this post is based on that.

So the input seems to be a file of nunmbers, where the first value is the number of inputs, followed by them. It is a simple queue and a 0 means to extract the first client in queue. Any non-zero number means to add a new element with that priority to the queue.

The order of arrival is used as an id of the element.

3 4 0 5 8 0 0 interpreted

So the 7 commands goes as

• client 1 enters the queue with priority 3: (1,3)
• client 2 enters the queue with priority 4 and gets the first place (2,4) (1,3)
• 0: client 2 is extracted
• client 3 enter the queue with priority 5 so queue has (3,5) (1,3)
• client 4 enters the queue with priority 8 so queue is (4,8) (3,5) (1,3)
• 0: client 4 is extracted
• 0: client 3 is extracted
• service ends with client 1 left in queue

A priority queue

Let us use some definition:

A priority queue is a data structure for maintaining a set S of x elements, each with an associated value called a key k. A max-priority queue supports the following operations:

INSERT( S, x )

MAXIMUM( S )

EXTRACT-MAX( S )

INCREASE-KEY( S, x, k )

From Cormen et al - Introduction to Algorithms, 3rd edition ISBN 978 0 262 03384 8 , page 162

A priority queue as a heap

Let us consider a heap as an array of pointers, so we can use a heap of anything: ints, structs et. al. And consider these functions, with the obvious meanings:

typedef int(F_compare)(const void*, const void*);

typedef struct
{                     // heap: as a vector of pointers
    void**     H;     // the heap itself
    unsigned   size;  // current size
    unsigned   capacity;
    unsigned   increment;
    unsigned   limit;
    F_compare* f_cmp;  // Max_Heap? Min_Heap?
} Heap;

Heap* hp_destroy(Heap*);
int   hp_build_max_heap(Heap*);
Heap* hp_create(
    unsigned initial, unsigned increment, unsigned limit,
    F_compare* f);

void* hp_extract_max(Heap* heap);
int   hp_insert(void* elem, Heap* heap);
int   hp_is_max_heap(Heap* heap, unsigned root);
int   hp_max_heapify(Heap* heap, unsigned index);
int   hp_heapSort(Heap* heap);

So our heap is extensible, from an initial size up to a limit in steps of increment.

For computing order we use a compare function, like qsort does. The usual way.

our heap element is a simple struct

typedef struct
{
    unsigned id;
    unsigned priority;
} Element;

int f_cmp_el(const void* a, const void* b);

The compare function is trivial:

int f_cmp_el(const void* a, const void* b)
{ 
    const Element* one   = a;
    const Element* other   = b;`
    if (one->priority > other->priority) return -1;
    if (one->priority == other->priority) return 0;
    return 1;
}

since we just need to compare the priorities.

building the example program

If we have this heap implemented, then the program is just a matter of building a heap with the values, and extracting the first in queue at each 0.

consuming the numbers

#include <stdio.h>

int process(const char* input);

int main(void)
{
    const char in_file[] = "in.txt";
    int res = process(in_file);
    printf("main(): %d commands processed from \"%s\"\n", res,in_file);
    return 0;
}

int process(const char* input)
{
    static int size = 0;
    FILE*      in   = fopen(input, "r");
    if (in == NULL) return -1;
    int res   = 0;
    int value = 0;
    res       = fscanf(in, "%d", &value);
    if (res != 1)
    {
        fclose(in);
        return -2;
    }
    printf("%d commands in \"%s\"\n", value,input);
    int ok = 0;
    while (value > ok)
    {
        int cmd = 0;
        res = fscanf(in, "%d", &cmd);
        if (res < 0) break;
        if (res != 1) continue;
        printf("  command: %d\n", cmd);
        ++ok;
    }
    return ok;
    fclose(in);
    return 0;
}

For in.txt as the input in the original post

7
3 4 0 5 8 0 0

this code shows

7 commands in "in.txt"
  command: 3
  command: 4
  command: 0
  command: 5
  command: 8
  command: 0
  command: 0
main(): 7 commands processed from "in.txt"

using the numbers as commands

A change in process can check for the command and call the heap functions as needed.

This program does that:

#include <stdio.h>

#include "aheap.h"

typedef struct
{
    unsigned id;
    unsigned priority;
} Element;

int f_cmp_el(const void* a, const void* b);

int process(const char* input);

int main(void)
{
    const char in_file[] = "in.txt";
    int        res       = process(in_file);
    printf(
        "main(): %d commands processed from \"%s\"\n", res,
        in_file);
    return 0;
}

int process(const char* input)
{
    FILE* in = fopen(input, "r");
    if (in == NULL) return -1;
    int res   = 0;
    int value = 0;
    res       = fscanf(in, "%d", &value);
    if (res != 1)
    {
        fclose(in);
        return -2;
    }
    printf("%d commands in \"%s\"\n", value, input);
    Heap* my_heap = hp_create(100, 100, 
        1000, f_cmp_el);
    if (my_heap == NULL)
    { 
        fprintf(stderr, "Error creating queue! Aborting\n");
        fclose(in);
        return -3;
    }
    int ok = 0;
    Element* next = NULL;
    int      nsu  = 0;

    while (value > ok)
    {
        int cmd = 0;
        res     = fscanf(in, "%d", &cmd);
        if (res < 0) break;
        if (res != 1) continue;
        switch (cmd)
        {
            case 0: // serve one client
                next = (Element*) hp_extract_max(my_heap);
                if (next == NULL)
                {
                    printf(
                        "    No element in queue\n");
                    break;
                }
                printf(
                    "    %d removed from the queue. Priority is %d\n",
                    next->id, next->priority);
                break;
            default:
                next = malloc(sizeof(Element));
                if (next == NULL) { break; }
                next->id = ++nsu;
                next->priority = cmd;
                res = hp_insert(next, my_heap);
                printf("    %d entered the queue. Priority %d\n", next->id, next->priority);
                break;
        };  // case
        ++ok;
    }
    hp_destroy(my_heap);
    return ok;
    fclose(in);
    return 0;
}

int f_cmp_el(const void* a, const void* b)
{
    const Element* one   = a;
    const Element* other = b;
    if (one->priority > other->priority) return -1;
    if (one->priority == other->priority) return 0;
    return 1;
}

There is not much logic in it:

• if the command is 0 then calls hp_extract_max(). It is a priority queue so that is all we need.
• if the command is a number then it is a new client with such priority so an Element is build and passed to hp_insert().

output

7 commands in "in.txt"
    1 entered the queue. Priority 3
    2 entered the queue. Priority 4
    2 removed from the queue. Priority is 4
    3 entered the queue. Priority 5
    4 entered the queue. Priority 8
    4 removed from the queue. Priority is 8
    3 removed from the queue. Priority is 5
main(): 7 commands processed from "in.txt"

an implementation for the heap

the header aheap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "memory.h"

typedef int(F_compare)(const void*, const void*);

typedef struct
{                     // heap: as a vector of pointers
    void**     H;     // the heap itself
    unsigned   size;  // current size
    unsigned   capacity;
    unsigned   increment;
    unsigned   limit;
    F_compare* f_cmp;  // Max_Heap? Min_Heap?
} Heap;

Heap* hp_create(
    unsigned initial, unsigned increment, unsigned limit,
    F_compare* f);
Heap* hp_destroy(Heap*);
int   hp_build_max_heap(Heap*);

int   hp_empty(Heap*);
void* hp_extract_max(Heap* heap);
int   hp_insert(void* elem, Heap* heap);
int   hp_is_max_heap(Heap* heap, unsigned root);
int   hp_max_heapify(Heap* heap, unsigned index);
int   hp_heap_sort(Heap* heap);

a possible implementation in aheap.c

#include <stdio.h>
#include "aheap.h"


Heap* hp_destroy(Heap* heap)
{
    free(heap->H);
    free(heap);
    return NULL;
};

int hp_build_max_heap(Heap* heap)
{
    for (unsigned i = heap->size / 2; i > 0; i -= 1)
        hp_max_heapify(heap, i);
    return 0;
};

Heap* hp_create(
    unsigned init, unsigned inc, unsigned lim, F_compare* f)
{
    if (init == 0) return NULL;  // for sanity
    if (lim == 0) return NULL;
    if (lim < init) lim = init;
    Heap* novo = (Heap*)malloc(sizeof(Heap));
    if (novo == NULL) return NULL;
    novo->f_cmp     = f;
    novo->capacity  = init;  // sure
    novo->limit     = lim;
    novo->increment = inc;
    novo->size      = 0;
    novo->H = (void*)malloc((1 + init) * sizeof(void*));
    for (unsigned i = 0; i <= init; i += 1)
        novo->H[i] = NULL;
    return novo;
}

int hp_empty(Heap* heap)
{ 
    if (heap == NULL) return 0;
    return heap->size == 0;
}

void* hp_extract_max(Heap* heap)
{
    if (heap->size <= 0) return NULL;
    // index 0 is not used
    heap->H[0] = heap->H[1];
    heap->H[1] = heap->H[heap->size];
    heap->size -= 1;
    hp_build_max_heap(heap);
    return heap->H[0];
};

int hp_insert(void* element, Heap* heap)
{
    // full?
    if (heap->size >= heap->limit) return -1;
    // can it grow?
    if (heap->size >= heap->capacity)
    {
        if (heap->increment == 0) return -1;
        if ((heap->increment + heap->capacity) >
            heap->limit)
            return -1;
        // ok:
        unsigned n_atual = heap->capacity;
        unsigned n_novo  = n_atual + heap->increment;
        // alloc new block
        void* novo =
            realloc(heap->H, (1 + n_novo) * sizeof(void*));
        if (novo == NULL) return -2;
        heap->H        = (void**)novo;
        heap->capacity = n_novo;
    }
    heap->size += 1;
    heap->H[heap->size] = element;
    return hp_build_max_heap(heap);
};

int hp_is_max_heap(Heap* heap, unsigned root)
{
    unsigned esq = root + root;  // 2n
    unsigned dir = 1 + esq;      // 2n + 1
    if (esq > heap->size) return 1;
    if (dir > heap->size) return 1;
    // violation
    if (heap->f_cmp(heap->H[esq], heap->H[root]) == -1)
        return 0;
    // violation
    if (heap->f_cmp(heap->H[dir], heap->H[root]) == -1)
        return 0;
    return (hp_is_max_heap(heap, esq) +
            hp_is_max_heap(heap, dir)) == 2;
};

int hp_max_heapify(Heap* heap, unsigned root)
{
    unsigned maior = root;
    void*    temp;
    unsigned esq = root + root;  // 2n
    unsigned dir = 1 + esq;      // 2n + 1
    if (esq > heap->size) return 0;
    maior = (heap->f_cmp(heap->H[esq], heap->H[root]) == -1)
              ? esq
              : root;
    if (esq != (heap->size))
    {
        if (heap->f_cmp(heap->H[dir], heap->H[maior]) == -1)
            maior = dir;
    }

    if (maior != root)
    {
        temp           = heap->H[root];
        heap->H[root]  = heap->H[maior];
        heap->H[maior] = temp;
        hp_max_heapify(heap, maior);
    }  // end if
    return 0;
};

int hp_heap_sort(Heap* heap)
{
    while (heap->size > 1)
    {
        void* greatest = hp_extract_max(heap);
        // poe de volta no final
        heap->H[1 + heap->size] = greatest;
    }
    return 0;
}