C语言升序优先队列堆优先级排序异常问题求助

我的课程作业C语言优先队列程序，元素插入、删除功能正常，存储逻辑符合预期，但输出结果异常：值与预期列不匹配，数据顺序混乱。怀疑问题出在pq_insert函数的优先级分配上，多次重写该函数仍无法实现正确的上浮（percolate up）排序逻辑。

预期输出示例（数值为随机生成） #

1 /    1 /    1 (   1)
1 /    1 /    1 (   1)
2 /    2 /    2 (   2)
14 /   14 /   14 (  14)
14 /   14 /   14 (  14)
25 /   25 /   25 (  25)
26 /   26 /   26 (  26)
26 /   26 /   26 (  26)

格式说明：first/removed/priority (expected)

实际输出示例 #

2/2/2 (1)
1/1/1 (4)
4/4/4 (3)
3/3/3 (2)

优先队列实现代码 #

#include <stdlib.h>

#include "pq.h"
#include "dynarray.h"

/*
 * 表示优先队列的结构体，需定义实现优先队列所需的数据
 */
struct pq {
    struct dynarray* array;
};
struct pq_node 
{
    int priority;
    void* value;
};


/*
 * 分配并初始化一个空的优先队列，返回其指针
 */
struct pq* pq_create() {
    struct pq* new_pq = malloc(sizeof(struct pq));

    // 内存分配检查
    if (new_pq == NULL) {
        exit(EXIT_FAILURE);
    }

    new_pq->array = dynarray_create();

    return new_pq;
}


/*
 * 释放给定优先队列的内存，注意：此函数不应释放优先队列中存储的单个元素，这是调用者的责任
 *
 * 参数：
 *   pq - 要销毁的优先队列，不能为NULL
 */
void pq_free(struct pq* pq) {
    dynarray_free(pq->array);
    free(pq);
    return;
}


/*
 * 如果指定的优先队列为空则返回1，否则返回0
 *
 * 参数：
 *   pq - 要检查是否为空的优先队列，不能为NULL
 *
 * 返回值：
 *   若pq为空返回1，否则返回0
 */
int pq_isempty(struct pq* pq) {
    return dynarray_size(pq->array) == 0;
}


/*
 * 将给定元素插入优先队列，并指定优先级值。注意：在此实现中，**更小的优先级值对应更高的优先级**，即优先队列中优先级值最小的元素应最先被返回
 *
 * 参数：
 *   pq - 要插入元素的优先队列，不能为NULL
 *   value - 要插入pq的值
 *   priority - 分配给新插入元素的优先级值。注意：在此实现中，更小的优先级值对应更高的优先级，即优先队列中优先级值最小的元素应最先被返回
 */
void pq_insert(struct pq* pq, void* value, int priority) {
    int index = 0;

    // 内存分配
    struct pq_node* new_node = malloc(sizeof(struct pq_node));
    if (new_node == NULL) {
        exit(EXIT_FAILURE);
    }

    new_node->value = value;
    new_node->priority = priority;
    while (index < dynarray_size(pq->array) && ((struct pq_node*)dynarray_get(pq->array, index))->priority <= priority) {
        index++;
    }
    dynarray_insert(pq->array, new_node, index);
}


/*
 * 返回优先队列中第一个元素的值，即优先级值最小的元素
 *
 * 参数：
 *   pq - 要获取值的优先队列，不能为NULL或空
 *
 * 返回值：
 *   返回pq中第一个元素的值，即优先级值最小的元素
 */
void* pq_first(struct pq* pq) {
    if (pq_isempty(pq)) 
    {
        return NULL;
    }
    return ((struct pq_node*)dynarray_get(pq->array, 0))->value;
}


/*
 * 返回优先队列中第一个元素的优先级值，即优先级值最小的元素的优先级
 *
 * 参数：
 *   pq - 要获取优先级值的优先队列，不能为NULL或空
 *
 * 返回值：
 *   返回pq中第一个元素的优先级值，即优先级值最小的元素的优先级
 */
int pq_first_priority(struct pq* pq) {
    if (pq_isempty(pq)) 
    {   
        return 0;
    }

    return ((struct pq_node*)dynarray_get(pq->array, 0))->priority;
}


/*
 * 返回优先队列中第一个元素的值（优先级值最小的元素），并将该元素从队列中移除
 *
 * 参数：
 *   pq - 要移除元素的优先队列，不能为NULL或空
 *
 * 返回值：
 *   返回pq中第一个元素的值，即优先级值最小的元素
 */
void* pq_remove_first(struct pq* pq) {
    if (pq_isempty(pq)) 
    {
        return NULL;
    }

    struct pq_node* first_node = dynarray_get(pq->array, 0);
    dynarray_remove(pq->array, 0);
    void* value = first_node->value;
    free(first_node); 
    return value;
}

测试程序代码 #

/*
 * 用于测试优先队列实现的小程序
 */

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

#include "pq.h"

/*
 * 用于qsort()的比较函数，将整数数组按升序排序
 */
int ascending_int_cmp(const void * a, const void * b) {
  return ( *(int*)a - *(int*)b );
}


int main(int argc, char** argv) {
  struct pq* pq;
  int* first, * removed;
  int i, k, p;
  const int n = 16, m = 16;
  int vals[16 + 16], sorted[16 + 16];

  /*
   * 用常量值初始化随机数生成器，确保每次运行程序时生成相同的伪随机序列
   */
  srand(0);

  /*
   * 创建优先队列，将伪随机整数值的指针插入队列，优先级与值相同
   */
  pq = pq_create();
  printf("== 向PQ插入一些值\n");
  for (int i = 0; i < n; i++) {
    vals[i] = rand() % 64;
    pq_insert(pq, &vals[i], vals[i]);
  }

  /*
   * 复制随机值数组并按升序排序。此处复制是为了保持原数组顺序，确保优先队列中存储的指针始终指向相同的整数值
   */
  memcpy(sorted, vals, n * sizeof(int));
  qsort(sorted, n, sizeof(int), ascending_int_cmp);

  /*
   * 查看并移除PQ中一半的值
   */
  k = 0;
  printf("\n== 从PQ移除一些值：first / removed / priority (expected)\n");
  while (k < n / 2) {
    p = pq_first_priority(pq);
    first = pq_first(pq);
    removed = pq_remove_first(pq);
    if (first && removed) {
      printf("  - %4d / %4d / %4d (%4d)\n", *first, *removed, p, sorted[k]);
    } else {
      printf("  - (NULL) / (NULL) / %4d (%4d)\n", p, sorted[k]);
    }
    k++;
  }

  /*
   * 将第二组伪随机整数值添加到数组末尾，并将这些值的指针插入优先队列，优先级与值相同
   */
  printf("\n== 向PQ插入更多值\n");
  for (i = n; i < n + m; i++) {
    vals[i] = rand() % 64;
    pq_insert(pq, &vals[i], vals[i]);
  }

  /*
   * 将第二组随机值复制到排序数组末尾，并重新排序排序数组中除已检查的k个值之外的所有元素（因为它们已从PQ中移除，不会再出现）。再次复制是为了保持原数组顺序，确保优先队列中存储的指针始终指向相同的整数值
   */
  memcpy(sorted + n, vals + n, m * sizeof(int));
  qsort(sorted + k, n - k + m, sizeof(int), ascending_int_cmp);

  printf("\n== 从PQ移除剩余值：first / removed / priority (expected)\n");
  while (k < n + m && !pq_isempty(pq)) {
    p = pq_first_priority(pq);
    first = pq_first(pq);
    removed = pq_remove_first(pq);
    if (first && removed) {
      printf("  - %4d / %4d / %4d (%4d)\n", *first, *removed, p, sorted[k]);
    } else {
      printf("  - (NULL) / (NULL) / %4d (%4d)\n", p, sorted[k]);
    }
    k++;
  }

  printf("\n== PQ是否为空（预期1）？%d\n", pq_isempty(pq));
  printf("== 是否看到了所有预期值（预期1）？%d\n", k == m + n);

  pq_free(pq);
  return 0;
}

问题分析与修复 #

你的pq_insert函数当前逻辑是将新元素插入到第一个优先级大于当前元素的位置，这实际上维护了一个降序排列的数组，但题目要求优先级值越小越先被取出，队列头部应是优先级最小的元素，数组需维护升序排列（从小到大）。

当前循环条件((struct pq_node*)dynarray_get(pq->array, index))->priority <= priority会跳过所有优先级小于等于当前元素的位置，最终插入到第一个优先级更大的位置，导致数组降序，取出的第一个元素是最大优先级，与预期相反。

修复方案1：调整有序数组插入逻辑 #

修改pq_insert的循环条件，维护升序数组：

void pq_insert(struct pq* pq, void* value, int priority) {
    int index = 0;

    struct pq_node* new_node = malloc(sizeof(struct pq_node));
    if (new_node == NULL) {
        exit(EXIT_FAILURE);
    }

    new_node->value = value;
    new_node->priority = priority;
    // 找到第一个优先级大于当前元素的位置，插入后保持数组升序
    while (index < dynarray_size(pq->array) && ((struct pq_node*)dynarray_get(pq->array, index))->priority < priority) {
        index++;
    }
    dynarray_insert(pq->array, new_node, index);
}

修复方案2：实现堆结构的上浮逻辑 #

如果要使用堆结构（更高效的优先队列实现），需将元素插入数组末尾后与父节点比较上浮：

void pq_insert(struct pq* pq, void* value, int priority) {
    struct pq_node* new_node = malloc(sizeof(struct pq_node));
    if (new_node == NULL) {
        exit(EXIT_FAILURE);
    }
    new_node->value = value;
    new_node->priority = priority;

    // 插入到数组末尾
    int index = dynarray_size(pq->array);
    dynarray_insert(pq->array, new_node, index);

    // 上浮操作：当前节点优先级小于父节点则交换
    while (index > 0) {
        int parent_idx = (index - 1) / 2;
        struct pq_node* parent = dynarray_get(pq->array, parent_idx);
        if (new_node->priority < parent->priority) {
            // 交换当前节点与父节点
            dynarray_set(pq->array, index, parent);
            dynarray_set(pq->array, parent_idx, new_node);
            index = parent_idx;
        } else {
            break;
        }
    }
}

注意：此方案需要dynarray支持dynarray_set接口修改指定索引的元素。

修复后，队列会按优先级升序维护，每次取出的第一个元素就是优先级最小的元素，输出将与预期一致。

内容的提问来源于stack exchange，提问作者Clark LaBella