优先级队列

使用数据结构–堆 封装的优先级队列
可参考博客：https://blog.csdn.net/eric_qiushui/article/details/80488560

---

直接上代码

---

// Priority.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

typedef int DataType;

typedef int(*Compare)(const void *a, const void *b);

typedef struct PriorityQueue
{
    DataType* _array; // 数据块指针
    int _capacity;    // 容量
    int _size;        // 数组内已存数据元素个数
    Compare cmp;      // 比较方法
}PriorityQueue;

// 小堆
int Q_CompareAscending_order(const void *a, const void *b);

// 大堆
int Q_CompareDescending_order(const void *a, const void *b);
void PriorityQueueInit(PriorityQueue *Q, Compare cmp); // 初始化
void PriorityQueuePush(PriorityQueue *Q, DataType data); // 插入元素
void PriorityQueuePop(PriorityQueue *Q); // 删除元素
DataType PriorityQueueTop(PriorityQueue *Q); // 优先级最高的元素出队列
int PriorityQueueSize(PriorityQueue *Q); // 队列中元素个数
int PriorityQueueEmpty(PriorityQueue *Q); // 判断队列是否为空
void PriorityQueueDestory(PriorityQueue *Q); // 销毁队列

void Q_Print(PriorityQueue *Q);

---

 // Priority.c

#include "Priority.h"

 // 交换函数
void Q_swap(DataType *a, DataType *b)
{
    DataType temp = *a;
    *a = *b;
    *b = temp;
}

 // 优先级从高到低
int Q_CompareAscending_order(const void *a, const void *b)
{
    return *(DataType*)a - *(DataType*)b;
}

 // 优先级从低到高
int Q_CompareDescending_order(const void *a, const void *b)
{
    return *(DataType*)b - *(DataType*)a;
}

 // 向下调整法
void Q_AdjustDown(PriorityQueue *Q, int size, int(*cmp)(const void *a, const void *b))
{
    int parent = ((size - 1) - 1) / 2;
    int child = parent * 2 + 1;

    while (parent >= 0)
    {
        // 默认左孩子最小，如果右孩子存在，找出左右孩子中最小的
        if ((child + 1) < size && cmp(&Q->_array[child], &Q->_array[child + 1]) > 0)
        {
            child += 1;
        }

        if ((child + 1) < size && cmp(&Q->_array[parent], &Q->_array[child]) > 0)
        {
            Q_swap(&(Q->_array[parent]), &(Q->_array[child]));
            if ((parent * 2 + 1) * 2 + 1 < size)
            {
                parent = child;
                child = parent * 2 + 1;
            }
        }
        else
        {
            parent = parent - 1;
            child = parent * 2 + 1;
        }
    }
}

 // 队列初始化
void PriorityQueueInit(PriorityQueue *Q, Compare cmp)
{
    assert(Q);
    Q->_array = (DataType *)malloc(sizeof(DataType)* 3);
    if (Q->_array == NULL)
    {
        printf("内存申请失败！！！\n");
        assert(0);
        return;
    }
    else
    {
        Q->_capacity = 3;
        Q->_size = 0;
        Q->cmp = cmp;
    }
}

 // 检查队列容量，如果队列已满，就扩容为原来容量的二倍
void _Cheak_Capacity(PriorityQueue *Q)
{
    if (Q->_capacity == Q->_size)
    {
        Q->_array = (DataType*)realloc(Q->_array, sizeof(DataType)*(Q->_capacity) * 2);

        if (Q->_array == NULL)
        {
            printf("内存申请失败！！！\n");
            assert(0);
            return;
        }
        else
        {
            Q->_capacity = Q->_capacity * 2;
        }
    }
}

 // 遍历队列元素
void Q_Print(PriorityQueue *Q)
{
    int i = 0;
    assert(Q);

    for (i = 0; i < Q->_size; i++)
    {
        printf("%d ", Q->_array[i]);
    }

    printf("\n");
}

 // 向上调整法
void Q_AdjustUp(PriorityQueue *Q, int size, int(*cmp)(const void *a, const void *b))
{
    int parent = ((size - 1) - 1) / 2;
    int child = size - 1;
    while (parent >= 0)
    {
        if ((child < size) && cmp(&(Q->_array[parent]), &(Q->_array[child])) > 0)
        {
            Q_swap(&(Q->_array[parent]), &(Q->_array[child]));
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            return;
        }
    }
}


// 在队列中插入值为data的元素 
void PriorityQueuePush(PriorityQueue *Q, DataType data)
{
    assert(Q);

    _Cheak_Capacity(Q);
    Q->_array[Q->_size] = data;
    Q->_size++;

    Q_AdjustUp(Q, Q->_size, Q->cmp);
}

// 获取优先级最高的元素 
DataType PriorityQueueTop(PriorityQueue *Q)
{
    assert(Q);
    return Q->_size > 0 ? Q->_array[0] : 0;
}

// 检测一个队列是否为空队列 
int PriorityQueueEmpty(PriorityQueue *Q)
{
    assert(Q);
    return Q->_size > 0 ? 0 : 1;
}

// 获取队列中元素的个数 
int PriorityQueueSize(PriorityQueue *Q)
{
    assert(Q);
    return Q->_size;
}

// 删除队列优先级最高的元素 
void PriorityQueuePop(PriorityQueue *Q)
{
    assert(Q);

    Q_swap(&Q->_array[0], &Q->_array[Q->_size - 1]);
    Q->_size--;
    Q_AdjustDown(Q, Q->_size, Q->cmp);
}

// 销毁队列 
void PriorityQueueDestory(PriorityQueue *Q)
{
    assert(Q);

    free(Q->_array);
    Q->_capacity = 0;
    Q->_size = 0;
}

---

测试

#include "Priority.h"

void TestPriorityQueue()
{
    PriorityQueue Q; // 创建队列
    DataType ret_Top = 0;
    int ret_Size = 0;
    int ret_Empty = 0;

    PriorityQueueInit(&Q, Q_CompareAscending_order); // 初始化

    PriorityQueuePush(&Q, 53); // 插入元素
    PriorityQueuePush(&Q, 17);
    PriorityQueuePush(&Q, 78);
    PriorityQueuePush(&Q, 45);
    PriorityQueuePush(&Q, 65);
    PriorityQueuePush(&Q, 87);
    PriorityQueuePush(&Q, 23);
    PriorityQueuePush(&Q, 31);
    Q_Print(&Q);
    ret_Top = PriorityQueueTop(&Q);
    printf("Top = %d\n", ret_Top);
    ret_Size = PriorityQueueSize(&Q);
    printf("Size = %d\n", ret_Size);
    ret_Empty = PriorityQueueTop(&Q);
    if (ret_Empty == 0)
    {
        printf("不是空堆！！\n");
    }
    else
    {
        printf("空堆！！！\n");
    }

    PriorityQueuePop(&Q); // 删除元素
    Q_Print(&Q);
    ret_Top = PriorityQueueTop(&Q);
    printf("Top = %d\n", ret_Top);
    ret_Size = PriorityQueueSize(&Q);
    printf("Size = %d\n", ret_Size);
    ret_Empty = PriorityQueueTop(&Q);
    if (ret_Empty == 0)
    {
        printf("非空！！\n");
    }
    else
    {
        printf("空！！！\n");
    }

    PriorityQueueDestory(&Q); // 销毁队列
}

int main()
{
    TestPriorityQueue();
    system("pause");
    return 0;
}

测试结果：

---

不正指出还请指出，有劳！！！