C 语言实现的优先级队列

priorityqueue.h

/*******************************************************************************
* Copyright © 2024-2025 Light Zhang <mapaware@hotmail.com>, MapAware, Inc.     *
* ALL RIGHTS RESERVED.                                                         *
*                                                                              *
* PERMISSION IS HEREBY GRANTED, FREE OF CHARGE, TO ANY PERSON OR ORGANIZATION  *
* OBTAINING A COPY OF THE SOFTWARE COVERED BY THIS LICENSE TO USE, REPRODUCE,  *
* DISPLAY, DISTRIBUTE, EXECUTE, AND TRANSMIT THE SOFTWARE, AND TO PREPARE      *
* DERIVATIVE WORKS OF THE SOFTWARE, AND TO PERMIT THIRD - PARTIES TO WHOM THE  *
* SOFTWARE IS FURNISHED TO DO SO, ALL SUBJECT TO THE FOLLOWING :               *
*                                                                              *
* THE COPYRIGHT NOTICES IN THE SOFTWARE AND THIS ENTIRE STATEMENT, INCLUDING   *
* THE ABOVE LICENSE GRANT, THIS RESTRICTION AND THE FOLLOWING DISCLAIMER, MUST *
* BE INCLUDED IN ALL COPIES OF THE SOFTWARE, IN WHOLE OR IN PART, AND ALL      *
* DERIVATIVE WORKS OF THE SOFTWARE, UNLESS SUCH COPIES OR DERIVATIVE WORKS ARE *
* SOLELY IN THE FORM OF MACHINE - EXECUTABLE OBJECT CODE GENERATED BY A SOURCE *
* LANGUAGE PROCESSOR.                                                          *
*                                                                              *
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR   *
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,     *
* FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON - INFRINGEMENT.IN NO EVENT   *
* SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE    *
* FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,  *
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER  *
* DEALINGS IN THE SOFTWARE.                                                    *
*******************************************************************************/
/*
** @file priorityqueue.h
** @brief Priority Queue implementation in C
**
** @author mapaware@hotmail.com
** @copyright © 2024-2030 mapaware.top All Rights Reserved.
** @version 1.0.0
**
** @since 2024-11-21 21:54:30
** @date
**
** @note
**   see: http://btechsmartclass.com/data_structures/max-heap.html
* 
* Usage:

    // same as: PQueueNew(256, PQMaxHeapComp, PQElemSwap)
    PQueue_t* pq = PQueueNew(256, 0, 0);

    PQueuePush(pq, (PQElem_t)40);
    PQueuePush(pq, (PQElem_t)10);
    PQueuePush(pq, (PQElem_t)60);
    PQueuePush(pq, (PQElem_t)50);
    PQueuePush(pq, (PQElem_t)20);
    PQueuePush(pq, (PQElem_t)20);

    const PQElem_t* elt = PQueueTop(pq);
    printf(">>top=%lld\n", (int64_t)(*elt)); // >>top=60

    PQueuePop(pq, 0);  // drop the toppest element(=60) here
    elt = PQueueTop(pq);
    printf(">>top=%lld\n", (int64_t)(*elt)); // >>top=50

    int64_t n = 50;
    PQueuePop(pq, (const PQElem_t*)&n);    // drop the element(=50) here
    elt = PQueueTop(pq);
    printf(">>top=%lld\n", (int64_t)(*elt)); // >>top=40

    PQueueFree(pq, 0);
* 
*/
#ifndef PRIORITY_QUEUE_H_
#define PRIORITY_QUEUE_H_


#if defined(__cplusplus)
extern "C"
{
#endif

#include <stdio.h>
#include <stdint.h>


typedef void* PQElem_t;


typedef struct
{
    int (*compfunc)(const PQElem_t *, const PQElem_t *);
    void (*swapfunc)(PQElem_t*, PQElem_t*);

    size_t capcity;
    size_t length;
    PQElem_t elems[0];
} PQueue_t;

static void _PQBuildHeap(PQueue_t* pq, ssize_t size, ssize_t i)
{
    if (size > 1) {
        // Find the largest among root, left child and right child
        ssize_t largest = i;
        ssize_t l = 2 * i + 1;
        ssize_t r = 2 * i + 2;

        if (l < size && pq->compfunc(&pq->elems[l], &pq->elems[largest]) > 0) {
            largest = l;
        }
        if (r < size && pq->compfunc(&pq->elems[r], &pq->elems[largest]) > 0) {
            largest = r;
        }

        // Swap and continue heapifying if root is not largest
        if (largest != i) {
            pq->swapfunc(&pq->elems[i], &pq->elems[largest]);
            _PQBuildHeap(pq, size, largest);
        }
    }
}


static int PQMaxHeapComp(const PQElem_t* elt1, const PQElem_t* elt2)
{
    PQElem_t v1 = (PQElem_t)(*elt1);
    PQElem_t v2 = (PQElem_t)(*elt2);
    return (v1 > v2 ? 1 : (v1 < v2 ? -1 : 0));
}

static int PQMinHeapComp(const PQElem_t* elt1, const PQElem_t* elt2)
{
    PQElem_t v1 = (PQElem_t)(*elt1);
    PQElem_t v2 = (PQElem_t)(*elt2);
    return (v1 > v2 ? -1 : (v1 < v2 ? 1 : 0));
}


static void PQElemSwap(PQElem_t * elt1, PQElem_t * elt2)
{
    PQElem_t elt = *elt1;
    *elt1 = *elt2;
    *elt2 = elt;
}


static PQueue_t * PQueueNew(size_t capcity, int (*comp)(const PQElem_t*, const PQElem_t*), void (*swap)(PQElem_t*, PQElem_t*))
{
    PQueue_t * pq = (PQueue_t *) malloc(sizeof(PQueue_t) + sizeof(PQElem_t) * capcity);
    if (pq) {
        pq->capcity = capcity;
        pq->length = 0;
        pq->compfunc = comp? comp: PQMaxHeapComp;
        pq->swapfunc = swap? swap: PQElemSwap;
    }
    return pq;
}


static const PQElem_t * PQueueTop(const PQueue_t* pq)
{
    if (pq->length) {
        return &pq->elems[0];
    }
    return 0;
}


// Function to insert an element into the tree
static int PQueuePush(PQueue_t* pq, const PQElem_t elt) {
    if (! pq->length) {
        pq->elems[0] = elt;
        pq->length++;
        // success
        return 1;
    }
    else if (pq->length != pq->capcity) {
        pq->elems[pq->length++] = elt;
        for (ssize_t i = pq->length / 2 - 1; i >= 0; i--) {
            _PQBuildHeap(pq, pq->length, i);
        }
        // success
        return 1;
    }
    else {
        // overflow
        return 0;
    }
}


// Function to delete an element from the tree
static PQElem_t * PQueuePop(PQueue_t* pq, const PQElem_t* eltp)
{
    ssize_t i = 0;
    if (eltp) {
        for (; i != pq->length; i++) {
            if (!pq->compfunc(&pq->elems[i], eltp)) {
                break;
            }
        }
    }
    if (i != pq->length) {
        pq->swapfunc(&pq->elems[i], &pq->elems[pq->length - 1]);
        pq->length--;

        for (i = (ssize_t) pq->length / 2 - 1; i >= 0; i--) {
            _PQBuildHeap(pq, pq->length, i);
        }

        return &pq->elems[pq->length];
    }

    // no element pop
    return 0;
}


static void PQueueFree(PQueue_t* pq, void (*elemdtor)(PQElem_t*))
{
    if (pq) {
        if (elemdtor) {
            ssize_t i = 0;
            PQElem_t* elt = pq->elems;
            while (i++ != pq->length) {
                elemdtor(elt++);
            }
        }
        free(pq);
    }
}

#ifdef __cplusplus
}
#endif
#endif /* PRIORITY_QUEUE_H_ */