C语言实现优先队列：基于二叉堆的数据结构与核心算法

核心数据结构设计

为了实现类型通用的优先队列，首先定义一个键值对结构体 KeyValue。其中 _key 用于存储表示优先级的整数值，_value 为泛型指针，指向实际承载的业务数据。

// key_value.h
struct key_value_struct {
    int _key;      // 优先级
    void *_value;  // 业务数据指针
};

// 工厂函数：创建键值对
KeyValue *key_value_new(int key, void *value);
// 析构函数：释放内存，需传入用户自定义的数据释放回调
void key_value_free(KeyValue *kv, void (*freevalue)(void *));

接下来是核心的 PriorityQueue 结构体，它内部维护了一个指向 KeyValue 指针数组的 _nodes，这本质上就是一个完全二叉树的顺序存储结构。此外还包含当前节点数量 _size、容量 _capacity 以及优先级模式枚举（PRIORITY_MAX 或 PRIORITY_MIN）。

#define PRIORITY_MAX 1
#define PRIORITY_MIN 2

struct priority_queue_struct {
    KeyValue **_nodes;
    int _size;
    int _capacity;
    int _priority;
};

关键操作接口说明

• 初始化与销毁：priority_queue_new 分配默认容量并设置优先级模式；priority_queue_free 遍历释放所有节点并清理自身内存。
• 查看顶部：priority_queue_top 仅返回根节点，不修改队列状态。根节点即为优先级最高的元素。
• 入队 (Enqueue) ：将新元素置于数组末尾，并通过“向上浮动”算法恢复堆秩序。
• 出队 (Dequeue) ：取出根节点后，将数组最后一个元素移至根部，并通过“向下沉潜”算法恢复堆秩序，最后缩小 size。

第1步：入队操作的堆调整（向上上浮）

目的：保证新加入的元素处于符合优先级规则的父/子关系位置。

入口：调用 priority_queue_enqueue(pq, kv)。

1. 将新节点暂存至 pq->_nodes[pq->_size]。
2. 令当前索引 i = pq->_size - 1，计算父节点索引 parent = (i - 1) / 2。
3. 若子节点优先级高于父节点，交换两者位置，并将 i 更新为父节点索引继续比较，直到无法交换或到达根节点。
4. 完成状态：新元素已下沉至正确层级，且容量不足时触发扩容。

static void priority_queue_adjust_tail(PriorityQueue *pq) {
    int i = pq->_size - 1;
    pq->_size++; // 预留位置
    while (i > 0) {
        int child = i;
        int parent = (child - 1) / 2;
        if (priority_queue_compare(pq, parent, child) > 0) {
            priority_queue_swap(pq->_nodes, child, parent);
            i = parent;
        } else break;
    }
}

第2步：出队操作的堆调整（向下下沉）

目的：移除最高优先级元素后，填补空缺并保持堆性质。

入口：调用 priority_queue_dequeue(pq)。

1. 保存根节点 pq->_nodes[0] 作为返回值。
2. 将尾部元素 pq->_nodes[pq->_size-1] 移至根节点 pq->_nodes[0]。
3. 执行 pq->_size-- 减少计数。
4. 从根节点开始，找出左右子节点中优先级较高者，若其优先级高于当前父节点则交换，并沿路径继续下移；否则循环结束。
5. 完成状态：堆结构重新平衡，返回被移出的最高优先级元素。

static void priority_queue_adjust_head(PriorityQueue *pq) {
    int i, j, parent, left, right;
    i = 0;
    // 交换根节点与末尾节点
    priority_queue_swap(pq->_nodes, 0, pq->_size - 1);
    pq->_size--;
    
    while (i < (pq->_size - 1) / 2) {
        parent = i;
        left = i * 2 + 1;
        right = left + 1;
        j = left;
        // 选择较大的子节点
        if (priority_queue_compare(pq, left, right) > 0) j++;
        // 如果父节点小于较大的子节点，则交换并下沉
        if (priority_queue_compare(pq, parent, j) > 0) {
            priority_queue_swap(pq->_nodes, i, j);
            i = j;
        } else break;
    }
}

测试用例验证

在 main.c 中创建一个最大优先队列，依次插入一组无序整数作为优先级 Key，然后打印队列内容并逐个出队。正确的输出顺序应是从大到小排列的序列。

int main() {
    PriorityQueue *pq = priority_queue_new(PRIORITY_MAX);
    int a[] = {1, 9, 7, 8, 5, 4, 3, 2, 1, 100, 50, 17};
    
    for(int i=0; i<sizeof(a)/sizeof(int); ++i) {
        KeyValue *kv = key_value_new(a[i], NULL);
        priority_queue_enqueue(pq, kv);
    }
    
    priority_queue_print(pq);
    priority_queue_free(pq, NULL);
    return 0;
}

以上就是关于C语言利用二叉堆实现priority_queue优先队列的详细代码解析与方法总结。如果想进一步了解其他高级数据结构如红黑树或跳跃表，欢迎持续关注本站后续的技术分享文章！