在百度上建网站自媒体运营主要做什么
小根堆排序与合并 K 个有序链表的实现
1. 介绍
本技术文档详细介绍了如何使用 小根堆（Min Heap） 实现 K 个有序链表的合并。
核心思想是：
- 使用 小根堆 维护当前最小的节点。
- 每次取出堆顶元素（最小值）加入合并链表，并插入新的最小节点。
- 直至所有链表合并完成。
2. 代码结构
本实现包括以下关键部分：
- 交换函数 (
swap)：用于交换两个链表节点的指针。 - 调整堆 (
min_down和min_up)：维护小根堆的性质。 - 堆排序 (
min_heap_sort)：对链表数组进行初始堆化。 - 链表比较函数 (
int_compare)：比较链表节点的val值。 - 合并 K 个链表 (
mergeKLists)：主函数，使用小根堆合并链表。
3. 代码实现
3.1 交换函数
/* 交换两个指针变量的值 */
static void swap(void *a, void *b, size_t size) {struct ListNode* tmp = NULL;tmp = *((struct ListNode**)a);*((struct ListNode**)a) = *((struct ListNode**)b);*((struct ListNode**)b) = tmp;
}
3.2 小根堆调整
3.2.1 min_down - 下滤调整堆
static void min_down(void *base, size_t nmemb, size_t size, size_t root, compare_func cmp) {size_t smallest = root;size_t left = 2 * root + 1;size_t right = 2 * root + 2;char *arr = (char *)base;if (left < nmemb && cmp(arr + left * size, arr + smallest * size) < 0) {smallest = left;}if (right < nmemb && cmp(arr + right * size, arr + smallest * size) < 0) {smallest = right;}if (smallest != root) {swap(arr + root * size, arr + smallest * size, size);min_down(base, nmemb, size, smallest, cmp);}
}
3.2.2 min_up - 上滤调整堆
static void min_up(void *base, size_t size, size_t root, compare_func cmp) {size_t smallest = root;size_t parent = (root - 1) / 2;char *arr = (char *)base;if (root == 0) return;if (cmp(arr + parent * size, arr + smallest * size) > 0) {smallest = parent;}if (smallest != root) {swap(arr + root * size, arr + smallest * size, size);min_up(base, size, smallest, cmp);}
}
3.3 小根堆排序
void min_heap_sort(void *base, size_t nmemb, size_t size, compare_func cmp) {if (nmemb < 2) return;for (int i = (nmemb / 2) - 1; i >= 0; i--) {min_down(base, nmemb, size, i, cmp);}
}
3.4 比较函数
int int_compare(const void *a, const void *b) {return (*(struct ListNode **)a)->val - (*(struct ListNode **)b)->val;
}
3.5 合并 K 个有序链表
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {int leave_size = 0;struct ListNode *result = NULL;struct ListNode *tail = NULL;for (int i = 0; i < listsSize; i++) {if (lists[i] != NULL) {lists[leave_size] = lists[i];leave_size++;}}if (leave_size < 1) return NULL;if (leave_size == 1) return lists[0];min_heap_sort(lists, leave_size, sizeof(struct ListNode *), int_compare);while (leave_size > 1) {min_down(lists, leave_size, sizeof(struct ListNode *), 0, int_compare);if (result == NULL) {result = lists[0];lists[0] = lists[0]->next;tail = result;} else {tail->next = lists[0];lists[0] = lists[0]->next;tail = tail->next;tail->next = NULL;}if (lists[0] == NULL) {lists[0] = lists[leave_size - 1];leave_size--;}}if (lists != NULL && lists[0] != NULL) {tail->next = lists[0];tail = tail->next;}return result;
}
4. 复杂度分析
- 堆化过程: 复杂度为
O(n) - 每次插入或删除节点: 复杂度为
O(log k) - 总操作数:
O(n log k)
其中，n 是所有链表节点总数，k 是链表个数。
5. 结论
该算法利用 小根堆 维护 K 个链表的最小值，每次取出最小值并合并，使得整体时间复杂度达到 O(n log k)，远优于直接合并（O(nk)）。
适用于 大规模链表合并 任务，在 合并排序 或 优先队列 相关应用场景中有重要应用。