6. 堆与优先队列

习题

#30008

⚡4⏳4

实现不透明的整数小根堆：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct IntMinHeap IntMinHeap;

IntMinHeap *int_min_heap_create(void);
void int_min_heap_destroy(IntMinHeap *heap);
bool int_min_heap_push(IntMinHeap *heap, int64_t value);
bool int_min_heap_peek(
    const IntMinHeap *heap,
    int64_t *out_value
);
bool int_min_heap_pop(
    IntMinHeap *heap,
    int64_t *out_value
);
size_t int_min_heap_size(const IntMinHeap *heap);

要求：

1. 数组表示必须保持小根堆不变式；重复值按普通元素处理。
2. 堆拥有自己的存储；扩容失败或容量计算溢出时 push 返回 false，堆保持不变。
3. 空堆或参数无效时 peek、pop 返回 false，不得修改输出对象。
4. destroy(NULL) 安全，size(NULL) 返回 0。
5. push 和 pop 的时间复杂度为 $O(\log n)$，peek 为 $O(1)$。

#30009

⚡4⏳3

实现从整数数组中选出最小的前 k 个元素：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool smallest_k_i64(
    const int64_t *items,
    size_t count,
    size_t k,
    int64_t *out_items
);

要求：

1. out_items 必须按非递减顺序保存结果；相等值可以来自任意对应位置。
2. k == 0 时操作成功，此时两个数组都可以为空；k > count 时返回 false。
3. 输入数组不得修改；参数无效、分配失败或大小计算溢出时，输出数组保持不变。
4. 使用大小为 k 的堆，将时间复杂度控制在 $O(n\log k)$，额外空间复杂度为 $O(k)$。

#30010

⚡5⏳4

合并多条已经按非递减顺序排列的整数序列：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool merge_sorted_i64(
    const int64_t *const *sequences,
    const size_t *counts,
    size_t sequence_count,
    int64_t *out_items,
    size_t capacity,
    size_t *out_count
);

要求：

1. out_items 按所有输入序列的整体非递减顺序保存结果，并保持每条序列内部的先后顺序。
2. sequence_count == 0 时结果长度为 0；非空序列的指针必须有效，空序列指针可以为 NULL。
3. 总长度计算溢出、容量不足或参数无效时返回 false，不得修改输出数组和 *out_count。
4. 使用最小堆维护每条序列的当前首元素，时间复杂度为 $O(N\log k)$，其中 $N$ 为总元素数、$k$ 为序列数。