企业做网站需要注意事项,网站实现留言功能吗,怀化网站优化公司哪家好,网站alexa排名查询本篇博客介绍如何使用C合并k个有序链表#xff0c;在代码中会用到std::priority_queue#xff0c;首先需要介绍一下std::priority_queue的用法#xff0c;介绍完std::priority_queue后将介绍如何使用std::priority_queue来辅助合并k个有序链表。
一、C priority_queue用法介…本篇博客介绍如何使用C合并k个有序链表在代码中会用到std::priority_queue首先需要介绍一下std::priority_queue的用法介绍完std::priority_queue后将介绍如何使用std::priority_queue来辅助合并k个有序链表。
一、C priority_queue用法介绍
1.1 priority_queue基本用法
C 中的 priority_queue 是标准模板库STL中的一种数据结构它是一个基于堆默认为最大堆的实现用于自动排序插入的元素。在 priority_queue 中元素被按优先级取出这意味着最大的元素总是第一个被取出如果你想要一个最小堆你需要在声明时指定比较函数。
priority_queue 在 queue 头文件中定义通常用于需要按特定顺序处理元素的场景如任务调度、带权路径搜索如 Dijkstra 算法等。
下面是一些 priority_queue 的基本用法示例
包含头文件和创建 priority_queue
#include iostream
#include queueint main() {// 默认是一个最大堆std::priority_queueint pq;// 创建一个最小堆需要提供比较函数std::priority_queueint, std::vectorint, std::greaterint min_pq;return 0;
}向 priority_queue 添加元素
pq.push(30);
pq.push(20);
pq.push(50);
pq.push(40);访问 priority_queue 的顶部元素
std::cout The top element is: pq.top() std::endl; // 输出最大元素此处为 50移除 priority_queue 的顶部元素
pq.pop(); // 移除最大元素此处为 50检查 priority_queue 是否为空
if (pq.empty()) {std::cout The priority queue is empty. std::endl;
} else {std::cout The priority queue is not empty. std::endl;
}获取 priority_queue 的大小
std::cout The priority queue size is: pq.size() std::endl;1.2 priority_queue使用自定义类型
如果你想在 priority_queue 中使用自定义类型则需要定义比较方式。例如如果你有一个结构体 Point 并希望根据点的距离原点的远近来排序可以这样做
#include queue
#include vector
#include iostreamstruct Point {double x, y;Point(double _x, double _y) : x(_x), y(_y){} double distance() const { return x * x y * y; }
};// 定义比较函数
struct Compare {bool operator()(const Point a, const Point b) {return a.distance() b.distance(); // 更远的点优先级更高}
};int main() {std::priority_queuePoint, std::vectorPoint, Compare pq;pq.push(Point(1, 2));pq.push(Point(3, 4));pq.push(Point(0, 0));while (!pq.empty()) {Point top pq.top();std::cout Point with highest priority (farthest): ( top.x , top.y ) std::endl;pq.pop();}return 0;
}在这个例子中我们定义了一个比较结构体 Compare它重载了 () 运算符来允许 priority_queue 判断哪个点应该先出列。这里我们让距离原点更远的点有更高的优先级。
1.3 问题 std::priority_queuePoint, std::vector, Compare pq;为什么要填3个参数
在C中std::priority_queue是一个容器适配器它提供常数时间的最大元素查找以及对数时间的插入与删除。std::priority_queue默认使用std::vector作为其底层容器并使用std::less作为比较函数来构造一个最大堆。
在你的例子中
std::priority_queuePoint, std::vectorPoint, Compare pq;这里的三个参数分别是
Point: 这是队列中要存储的元素类型。std::vectorPoint: 这指定了底层容器类型。在这里是std::vector它将被用来存储Point类型的元素。Compare: 这是一个比较类或者函数对象用于定义优先队列中元素的优先级。
Compare参数需要是一个可以比较两个Point对象的函数或者函数对象。在std::priority_queue中这个比较函数决定了队列中元素的排序方式。具体地Compare定义了一个严格的弱序当你想要从队列中取出元素时队列会根据这个比较函数给出的优先级提供最高优先级的元素。
默认情况下如果不提供Compare类型std::priority_queue使用std::less这会创建一个最大堆其中最大元素首先被移除。如果你想要创建一个最小堆你可以传递std::greater作为Compare类型参数。
例如如果你的Point类有一个x坐标和一个y坐标你可能想根据x值或者y值的大小来比较Point对象。你可以定义一个比较类如下所示
struct Compare {bool operator()(const Point p1, const Point p2) {// 假设我们根据x坐标来比较两个点return p1.x p2.x;}
};使用这个Compare类priority_queue会根据Point对象的x坐标进行排序x值最大的点将会是队列中的第一个元素如果你希望队列为最小堆则应该将比较运算符改为。
在模板编程中提供这种灵活性是非常有用的因为这允许程序员自定义数据结构的行为以满足特定需求。
二、C合并K个有序链表
C合并K个有序链表要求合并后链表依然有序。
代码
#include iostream
#include vector
#include queuestruct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(nullptr) {}
};struct compare {bool operator()(const ListNode* l1, const ListNode* l2) {return l1-val l2-val;}
};ListNode* mergeKLists(std::vectorListNode* lists) {std::priority_queueListNode*, std::vectorListNode*, compare pq;for (auto list : lists) {if (list) {pq.push(list); // 这里push的是链表的头节点而不是链表本身因为链表本身是一个指针都是较小的值}}ListNode* dummy new ListNode(0);ListNode* tail dummy;while (!pq.empty()) {tail-next pq.top();pq.pop();tail tail-next;if (tail-next) {pq.push(tail-next); // next值再push到链表比较大小再pop出来}}ListNode* merged dummy-next;delete dummy;return merged;
}// 辅助函数创建链表
ListNode* createList(const std::vectorint vals) {ListNode* dummy new ListNode(0);ListNode* current dummy;for (int val : vals) {current-next new ListNode(val);current current-next;}ListNode* head dummy-next;delete dummy;return head;
}// 辅助函数打印链表
void printList(ListNode* head) {while (head) {std::cout head-val ;head head-next;}std::cout std::endl;
}int main() {// 创建一些链表std::vectorListNode* lists;lists.push_back(createList({1, 4, 5}));lists.push_back(createList({1, 3, 4}));lists.push_back(createList({2, 6}));// 合并链表ListNode* mergedList mergeKLists(lists);// 打印合并后的链表std::cout Merged List: ;printList(mergedList);// 清理内存while (mergedList ! nullptr) {ListNode* temp mergedList;mergedList mergedList-next;delete temp;}return 0;
}运行结果 Merged List: 1 1 2 3 4 4 5 6
mergeKLists函数说明
mergeKLists这个函数的目的是将 k 个有序链表合并成一个有序链表。下面是逐步的解释 初始化优先队列最小堆 std::priority_queueListNode*, std::vectorListNode*, compare pq;这行代码创建了一个最小堆用于存储链表的节点。这里使用了一个自定义的比较函数 compare确保队列总是按照节点的值从小到大排列。 将所有链表的头节点加入优先队列 for (auto list : lists) { if (list) pq.push(list); }这个循环遍历每个链表并将每个链表的头节点如果存在加入优先队列。这样队列中始终保存着当前未合并链表中最小的几个节点。 合并链表 创建一个虚拟头节点 ListNode* dummy new ListNode(0); 和一个尾指针 ListNode* tail dummy; 用于构建新的合并后的链表。然后进入一个循环此循环会持续直到优先队列为空 while (!pq.empty()) { ... }在循环内部从优先队列中取出最小的节点即队列顶部的节点并将其加入到合并后的链表中。tail-next pq.top(); pq.pop();将 tail 指针移动到新加入的节点上。tail tail-next;如果新加入的节点有后续节点即 tail-next 不为空则将这个后续节点加入优先队列中以便在后续的迭代中考虑。 返回合并后的链表 最后函数返回合并后链表的头节点即 dummy-next。ListNode* merged dummy-next;在返回之前删除虚拟头节点以避免内存泄漏。delete dummy;
总之这个函数通过使用优先队列来有效地找到每次应该添加到结果链表中的最小节点。 每次从队列中取出一个节点后将其下一个节点如果存在加入队列确保队列始终包含所有链表当前的最小节点。这样就可以按顺序合并所有链表。
如何获取合并后的头结点
在代码 ListNode* merged dummy-next; 中merged 是一个 ListNode 类型的指针它被赋值为 dummy-next。这里的 dummy 是一个虚拟哨兵头节点它不包含实际的数据而是作为合并链表过程中的辅助节点。
让我们详细解释一下这个过程 虚拟头节点 (dummy) 的作用 在合并链表的过程中为了方便处理边界情况如空链表通常会使用一个虚拟头节点。这个节点在开始时被创建但它的值不被使用在这个例子中它被初始化为 0。虚拟头节点的主要作用是提供一个统一的起始点无论是否有实际的数据节点。这样可以简化代码避免处理特殊情况。 构建合并后的链表 在函数中新的合并后的链表是通过不断地将节点添加到 dummy 节点之后构建的。这是通过移动 tail 指针来完成的它始终指向当前合并链表的最后一个节点。 设置 merged 指针 当所有的链表都被合并后dummy 的下一个节点 (dummy-next) 实际上是合并后链表的第一个真实数据节点。通过 ListNode* merged dummy-next;我们将 merged 指针设置为指向这个第一个真实数据节点。这样merged 就成为了合并后链表的头节点而 dummy 节点已经完成了它的任务。 返回合并后的链表 函数最终返回 merged即指向合并后链表的头节点的指针。 删除虚拟头节点 在返回 merged 之前代码中删除了 dummy 节点delete dummy;这是为了避免内存泄漏。由于 merged 已经指向了合并后链表的实际起始位置dummy 节点就不再需要了。
总结来说ListNode* merged dummy-next; 这行代码的目的是将 merged 指针设置为指向合并后链表的实际起始节点从而可以返回正确的链表头部同时避免包含不必要的虚拟头节点。
