大兴网站建设推广,中国菲律宾商会,怎么推广网站,泰安网站建设公司哪家好小根堆排序与合并 K 个有序链表的实现
1. 介绍
本技术文档详细介绍了如何使用 小根堆#xff08;Min Heap#xff09; 实现 K 个有序链表的合并。
核心思想是#xff1a;
使用 小根堆 维护当前最小的节点。每次取出堆顶元素#xff08;最小值#xff09;加入合并链表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)。
适用于 大规模链表合并 任务在 合并排序 或 优先队列 相关应用场景中有重要应用。
