C 语言实现的优先级队列-CSDN博客

本文链接：https://blog.csdn.net/ubuntu64fan/article/details/143958283
C 语言实现的优先级队列

pqueue.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 pqueue.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  2024-12-04 23:51:20
**
** @note
**   see: http://btechsmartclass.com/data_structures/max-heap.html
*/
#ifndef PQUEUE_H_
#define PQUEUE_H_


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

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>


#define PQUEUE_BLK_ELEMS   32  // A block has 32 PQElem_t

typedef struct
{
    int  (*comp)(const void*, const void*);
    void (*swap)(void*, void*);
    void (*copy)(void*, const void*);
    void (*dtor)(void*);
} PQCallback_t;


typedef struct
{
    PQCallback_t callback;

    size_t elemsize;
    size_t capacity;    
    size_t length;
    unsigned char *elems;
} PQueue_t;


static int PQ_Int64MaxHeapComp(const void* _elt1, const void* _elt2)
{
    int64_t elt1 = *(int64_t*)_elt1;
    int64_t elt2 = *(int64_t*)_elt2;

    if (elt2 > elt1) {
        return -1;
    }
    else if (elt2 < elt1) {
        return 1;
    }
    else {
        return 0;
    }
}

static int PQ_Int64MinHeapComp(const void* _elt1, const void* _elt2)
{
    int64_t elt1 = *(int64_t*)_elt1;
    int64_t elt2 = *(int64_t*)_elt2;

    if (elt2 > elt1) {
        return 1;
    }
    else if (elt2 < elt1) {
        return -1;
    }
    else {
        return 0;
    }
}

static void PQ_Int64ValueSwap(void* _elt1, void* _elt2)
{
    int64_t *elt1 = (int64_t*)_elt1;
    int64_t *elt2 = (int64_t*)_elt2;

    int64_t elt = *elt1;
    *elt1 = *elt2;
    *elt2 = elt;
}

static void PQ_Int64ValueCopy(void* dst, const void* src)
{
    *((int64_t*) dst) = *((const int64_t*) src);
}

static void PQ_DummyDtor(void* elt)
{
    // do nothing
}


static PQCallback_t PQ_Int64MaxCallback = { &PQ_Int64MaxHeapComp, &PQ_Int64ValueSwap, &PQ_Int64ValueCopy, &PQ_DummyDtor };

static PQCallback_t PQ_Int64MinCallback = { &PQ_Int64MinHeapComp, &PQ_Int64ValueSwap, &PQ_Int64ValueCopy, &PQ_DummyDtor };


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

        if (l < size && pq->callback.comp(&pq->elems[l * elemsize], &pq->elems[largest * elemsize]) > 0) {
            largest = l;
        }
        if (r < size && pq->callback.comp(&pq->elems[r * elemsize], &pq->elems[largest * elemsize]) > 0) {
            largest = r;
        }

        // Swap and continue heapifying if root is not largest
        if (largest != i) {
            pq->callback.swap(&pq->elems[i * elemsize], &pq->elems[largest * elemsize]);
            pqBuildHeap(pq, size, largest, elemsize);
        }
    }
}


static bool PQ_Init(PQueue_t* pq, size_t capacity, size_t elemsize, const PQCallback_t *callback)
{
    pq->capacity = ((capacity + PQUEUE_BLK_ELEMS - 1) / PQUEUE_BLK_ELEMS) * PQUEUE_BLK_ELEMS;
    pq->elems = (unsigned char *) malloc(elemsize * pq->capacity);
    pq->length = 0;
    if (! pq->elems) {
        // Error: out of mem
        return false;
    }
    pq->elemsize = elemsize;
    if (!callback) {
        pq->callback = PQ_Int64MaxCallback;
    }
    else {
        pq->callback = *callback;
    }
    return true;
}


static bool PQ_AddCapacity(PQueue_t* pq)
{
    pq->capacity += PQUEUE_BLK_ELEMS;

    void * newElems = realloc(pq->elems, pq->elemsize * pq->capacity);
    if (!newElems) {
        // Error: out of mem
        pq->capacity -= PQUEUE_BLK_ELEMS;
        return false;
    }

    // success
    pq->elems = (unsigned char*) newElems;
    return true;
}


static const void* PQ_Top(const PQueue_t* pq)
{
    if (pq->length) {
        return (void *)pq->elems;
    }
    return 0;
}



// PQ_Push
// Function to insert an element into the tree
//   returns:
//     1: success push
//    -1: out of memory
static int PQ_Push(PQueue_t* pq, const void *elt)
{
    if (! pq->length) {
        pq->callback.copy(pq->elems, elt);

        pq->length++;

        // success
        return 1;
    }
    else if (pq->length != pq->capacity) {
        pq->callback.copy(&pq->elems[pq->length * pq->elemsize], elt);

        pq->length++;

        for (int i = (int) pq->length / 2 - 1; i >= 0; i--) {
            pqBuildHeap(pq, (int) pq->length, i, pq->elemsize);
        }
        // success
        return 1;
    }
    else {
        // overflow
        if (PQ_AddCapacity(pq)) {
            return PQ_Push(pq, elt);
        }
        else {
            // out of memory
            return -1;
        }
    }
}

// PQ_PushUnique
//   returns:
//     1: success push
//     0: ignore dup
//    -1: out of memory
static int PQ_PushUnique(PQueue_t* pq, const void *elt)
{
    int i = 0;
    for (; i != pq->length; i++) {
        if (! pq->callback.comp(&pq->elems[i * pq->elemsize], elt)) {
            // find duplicates: i != pq->length
            break;
        }
    }
    if (i == pq->length) {
        // empty or no duplicates found
        return PQ_Push(pq, elt);
    }
    // ignore duplicates
    return 0;
}


// Function to delete an element from the tree
static void * PQ_Pop(PQueue_t* pq, const void *eltp)
{
    int i = 0;
    if (eltp) {
        for (; i != pq->length; i++) {
            if (!pq->callback.comp(&pq->elems[i * pq->elemsize], eltp)) {
                break;
            }
        }
    }

    if (i != pq->length) {
        // found existed one or eltp is null
        pq->callback.swap(&pq->elems[i * pq->elemsize], &pq->elems[(pq->length - 1) * pq->elemsize]);

        pq->length--;

        for (i = (int) pq->length / 2 - 1; i >= 0; i--) {
            pqBuildHeap(pq, (int) pq->length, i, pq->elemsize);
        }

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

    // no element pop
    return 0;
}


static void PQ_Reset(PQueue_t* pq)
{
    if (pq->callback.dtor) {
        while (pq->length-- > 0) {
            pq->callback.dtor(&pq->elems[pq->elemsize * pq->length]);
        }
    }
    pq->length = 0;
}


static void PQ_Done(PQueue_t* pq)
{
    PQ_Reset(pq);
    pq->capacity = 0;
    free(pq->elems);
}

#ifdef __cplusplus
}
#endif
#endif /* PQUEUE_H_ */