Concerning Priority Queue(With G

Listed below is an impl of priority queue(with generics, that is, the keys are of type void*).

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include "out.c"
#include <limits.h>
#include "type_wrapper.c"

#ifndef PRIORITY_QUEUE
#define PRIORITY_QUEUE
typedef struct PriorityQueueStruct {
    int capacity;
    int count;
    void **keys;
    int(*cmp)(void*, void*);
}*PriorityQueue;

void pq_exch(void **a, int i, int j) {
    void *t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int pq_max(void **a, int i, int j, int(*cmp)(void*, void*)) { return cmp(a[i], a[j]) > 0 ? i : j; }

void pq_swim(void **a, int k, int (*cmp)(void*, void*)) {
    int p = k / 2;
    while (k > 1 && cmp(a[k], a[p]) > 0) {
        pq_exch(a, k, p);
        k = p;
        p = k / 2;
    }
}

void pq_sink(void **a, int n, int k, int(*cmp)(void*, void*)) {
    while (2 * k <= n) {
        int j = 2 * k;
        if (j < n && cmp(a[j], a[j + 1]) < 0) j += 1;
        if (cmp(a[k], a[j]) >= 0) break;
        pq_exch(a, k, j);
        k = j;
    }
}

void PriorityQueueResize(PriorityQueue pq) {
    pq->capacity = pq->capacity == pq->count ? 2 * pq->capacity : pq->capacity / 2;
    void **a = malloc(sizeof(*a) * (pq->capacity + 1));
    for (int i = 1; i <= pq->count; i++) { a[i] = pq->keys[i]; }
    free(pq->keys);
    pq->keys = a;
}

PriorityQueue PriorityQueueCreate(int(*cmp)(void*, void*)) {
    PriorityQueue pq = (PriorityQueue)malloc(sizeof(*pq));
    pq->cmp = cmp;
    pq->capacity = 16;//initial capacity
    pq->count = 0;
    pq->keys = malloc((pq->capacity + 1) * sizeof(void*));
    return pq;
}

void PriorityQueueRelease(PriorityQueue pq) {
    free(pq->keys);
    free(pq);
}

bool PriorityQueueIsEmpty(PriorityQueue pq) { return pq->count == 0; }

void PriorityQueueInsert(PriorityQueue pq, void *k) {
    pq->keys[++pq->count] = k;
    pq_swim(pq->keys, pq->count, pq->cmp);
}

void* PriorityQueueDelete(PriorityQueue pq) {
    void *ret = pq->keys[1];
    pq->keys[1] = pq->keys[pq->count];
    pq->keys[pq->count] = NULL;
    pq->count--;
    pq_sink(pq->keys, pq->count, 1, pq->cmp);
    return ret;
}

void PriorityQueuePrint(PriorityQueue pq, void(*prt)(void*)) {
    printf("(\n");
    printf("count: %i\n", pq->count);
    for (int i = 0; i < pq->count; i++) { 
        printf("%i: ", i);
        prt(pq->keys[i]);
        printf("\n");
    }
    printf(")\n");
}
#endif

Another related ATD that is also useful is index priority queue:

/**
* Jan 31, 2021: revise ipq_cmp & sink, which is buggy.
*/
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <stdbool.h>
#ifndef INDEX_PRIORITY_QUEUE
#define INDEX_PRIORITY_QUEUE

typedef struct {
    int capacity;
    int count;
    int *indices;
    int *inverse;
    void **keys;
    int(*cmp)(void*, void*);
}*IndexPriorityQueue;

void ipq_exch(int *indices, int *inverse, int i, int j) {
    int t = indices[i];
    indices[i] = indices[j];
    indices[j] = t;

    inverse[indices[i]] = i;
    inverse[indices[j]] = j;
}

int ipq_cmp(void **keys, int *indices, int i, int j, int(*cmp)(void*, void*)) { return cmp(keys[indices[i]], keys[indices[j]]); }

int ipq_max(void **keys, int *indices, int i, int j, int(*cmp)(void*, void*)) { return ipq_cmp(keys, indices, i, j, cmp) > 0 ? i : j; }

void ipq_swim(void **keys, int *indices, int *inverse, int k, int (*cmp)(void*, void*)) {
    int p = k / 2;
    while (k > 1 && cmp(keys[indices[k]], keys[indices[p]]) > 0) {
        ipq_exch(indices, inverse, k, p);
        k = p;
        p = k / 2;
    }
}

void ipq_sink(void **keys, int *indices, int *inverse, int n, int k, int(*cmp)(void*, void*)) {
    while (2 * k <= n) {
        int j = 2 * k;
        if (j < n && ipq_cmp(keys, indices, j, j + 1, cmp) < 0) j += 1;
        if (ipq_cmp(keys, indices, k, j, cmp) >= 0) break;
        ipq_exch(indices, inverse, k, j);
        k = j;
    }
}

void IndexPriorityQueueResize(IndexPriorityQueue ipq) {
    ipq->capacity = ipq->capacity == ipq->count ? 2 * ipq->capacity : ipq->capacity / 2;
    void **keys = malloc(sizeof(*keys) * (ipq->capacity + 1));
    int *indices = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    int *inverse = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    
    for (int i = 1; i <= ipq->count; i++) { 
        keys[i] = ipq->keys[i]; 
        indices[i] = ipq->indices[i];
        inverse[i] = ipq->inverse[i];
    }

    free(ipq->keys);
    free(ipq->indices);
    free(ipq->inverse);
    
    ipq->keys = keys;
    ipq->indices = indices;
    ipq->inverse = inverse;
}

void IndexPriorityQueueRelease(IndexPriorityQueue ipq) {
    if (ipq == NULL) return;
    free(ipq->keys);
    free(ipq->indices);
    free(ipq->inverse);
    free(ipq);
}

IndexPriorityQueue IndexPriorityQueueCreate(int(*cmp)(void*, void*)) {
    IndexPriorityQueue ipq = (IndexPriorityQueue)malloc(sizeof(*ipq));
    ipq->cmp = cmp;
    ipq->capacity = 16;//initial capacity
    ipq->count = 0;
    ipq->keys = malloc((ipq->capacity + 1) * sizeof(void*));
    ipq->indices = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    ipq->inverse = (int*)malloc((ipq->capacity + 1) * sizeof(int));
    for (int i = 0; i < ipq->capacity; i++) { ipq->inverse[i] = -1; }
    return ipq;
}

bool IndexPriorityQueueIsEmpty(IndexPriorityQueue ipq) { return ipq->count == 0; }

bool IndexPriorityQueueContains(IndexPriorityQueue ipq, int idx) { return ipq != NULL && idx >= 0 && idx < ipq->capacity && ipq->inverse[idx] != -1; }

void IndexPriorityQueueInsert(IndexPriorityQueue ipq, int idx, void *key) {
    ipq->count++;
    ipq->keys[idx] = key;
    ipq->indices[ipq->count] = idx;
    ipq->inverse[idx] = ipq->count;
    ipq_swim(ipq->keys, ipq->indices, ipq->inverse, ipq->count, ipq->cmp);
}

int IndexPriorityQueueHPIndex(IndexPriorityQueue ipq) { return ipq != NULL ? ipq->indices[1] : -1; }

void* IndexPriorityQueueHPKey(IndexPriorityQueue ipq) { return ipq != NULL ? ipq->keys[ipq->indices[1]] : NULL; }

int IndexPriorityQueueDeleteHP(IndexPriorityQueue ipq) {
    int idx = ipq->indices[1];
    ipq_exch(ipq->indices, ipq->inverse, 1, ipq->count--);
    ipq_sink(ipq->keys, ipq->indices, ipq->inverse, ipq->count, 1, ipq->cmp);

    ipq->keys[idx] = NULL;
    ipq->inverse[idx] = -1;
    return idx;
}

int IndexPriorityQueueDelete(IndexPriorityQueue ipq, int idx) {
    return 0;
}

void IndexPriorityQueueChange(IndexPriorityQueue ipq, int idx, void *key) {
    if (ipq == NULL) return;
    ipq->keys[idx] = key;
    ipq_swim(ipq->keys, ipq->indices, ipq->inverse, ipq->inverse[idx], ipq->cmp);
    ipq_sink(ipq->keys, ipq->indices, ipq->inverse, ipq->count, ipq->inverse[idx], ipq->cmp);
}

void* IndexPriorityQueueKeyAtIndex(IndexPriorityQueue ipq, int idx) { return ipq->keys[idx]; }

void IndexPriorityQueuePrint(IndexPriorityQueue ipq, void(*prt)(void*)) {
    printf("(\n");
    printf("count: %i\n", ipq->count);
    for (int i = 0; i < ipq->count; i++) { 
        printf("%i: ", i);
        prt(ipq->keys[i]);
        printf("\n");
    }
    printf(")\n");
}
#endif