当前位置：首页 > ds >正文

数据结构精解：优先队列、哈希表与树结构

ds 2025/5/11 5:31:44

优先队列：给生活中的"急事优先"排序

在我们的日常生活中，经常会遇到需要按照优先级处理任务的情况。比如医院的急诊室，病情严重的患者需要优先就诊；又如操作系统中的进程调度，高优先级的进程会优先获得CPU资源。这些场景都可以用优先队列来模拟。

优先队列是一种特殊的队列，它的特点是每次出队的元素都是当前队列中优先级最高的。与普通的先进先出队列不同，优先队列会根据元素的优先级进行动态排序。

优先队列的实现方式

优先队列通常有三种实现方式：

无序数组：入队O(1)，出队O(n)
有序数组：入队O(n)，出队O(1)
堆：入队和出队都是O(log n)

其中，堆是最常用的实现方式，因为它在时间复杂度上达到了很好的平衡。

堆的结构与操作

堆是一种完全二叉树，根据性质可分为最大堆和最小堆：

最大堆：每个节点的值都大于或等于其子节点的值

最小堆：每个节点的值都小于或等于其子节点的值

堆的基本操作包括：

push：向堆中插入一个新元素

pop：删除堆顶元素

top：获取堆顶元素（不删除）

实际应用举例

想象你是一家餐厅的经理，每天收到大量的外卖订单，这些订单有不同的优先级（例如VIP客户、预订客户、普通客户）。使用优先队列，你可以确保厨师按照订单的重要性来处理，而不仅仅是按照到达的时间顺序。


struct Order {int id;int priority;string customer;};// 定义比较函数struct CompareOrder {bool operator()(const Order& a, const Order& b) {return a.priority < b.priority; // 大的优先级先出队}};void process_orders() {// 创建一个基于最大堆的优先队列priority_queue<Order, vector<Order>, CompareOrder> orderQueue;// 添加订单orderQueue.push({1, 2, "普通客户"});orderQueue.push({2, 3, "VIP客户"});orderQueue.push({3, 1, "普通客户"});// 处理订单(优先级高的先处理)while (!orderQueue.empty()) {Order current = orderQueue.top();orderQueue.pop();cout << "处理订单: " << current.id << " 客户: " << current.customer << endl;}}

哈希表：生活中的快速查询

哈希表是我们日常生活中经常使用的数据结构，尽管我们可能没有意识到。想想你的手机通讯录，当你想打电话给某人时，你不需要从A开始一个个查找，而是直接输入名字就能找到对应的电话号码。这就是哈希表的实际应用。

哈希表的原理

哈希表的核心思想是通过哈希函数将键(key)映射到数组的特定位置，从而实现O(1)时间复杂度的查找、插入和删除操作。

但是，由于不同的键可能会映射到同一位置，这就产生了冲突。解决冲突主要有两种方法：

链式法：在冲突位置维护一个链表
开放寻址法：寻找下一个空位置

实际应用举例

想象你在管理一个大型图书馆。每本书都有唯一的ISBN号码，你需要快速找到某本书的位置。使用哈希表，你可以将ISBN号码作为键，书的位置作为值，这样就能在常数时间内找到任何一本书。

struct Book {string title;string author;string location; // 书在图书馆中的位置};unordered_map<string, Book> library;void setup_library() {// 添加书籍library["978-3-16-148410-0"] = {"C++编程思想", "Bruce Eckel", "A区-3架-15层"};library["978-7-302-12260-9"] = {"算法导论", "Thomas H. Cormen", "B区-1架-7层"};// 查找书籍string isbn = "978-3-16-148410-0";if (library.find(isbn) != library.end()) {Book book = library[isbn];cout << "找到书籍: " << book.title << "，位置: " << book.location << endl;} else {cout << "未找到该书" << endl;}}

树结构：层次关系的完美表达

在现实生活中，树结构无处不在 - 从公司的组织架构、家族谱系到文件系统的目录结构，都可以用树来表示。

二叉树及其变种

二叉树是每个节点最多有两个子节点的树结构。根据不同的性质，二叉树有多种变种：

满二叉树：除叶子节点外，每个节点都有两个子节点
完全二叉树：除最后一层外，其他层的节点数都达到最大，且最后一层的节点都靠左排列
二叉搜索树(BST)：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值
平衡二叉树(AVL)：任何节点的两个子树的高度差不超过1
红黑树：一种自平衡的二叉搜索树，通过颜色标记维持平衡

树的遍历方式

前序遍历：根-左-右

中序遍历：左-根-右

后序遍历：左-右-根

层序遍历：按层从上到下，每层从左到右

实际应用举例

想象你正在开发一个家谱管理系统，每个家庭成员可以有多个子女。树结构非常适合表示这种关系。


struct FamilyMember {string name;vector<FamilyMember*> children;};void print_family_tree(FamilyMember* root, int level = 0) {if (!root) return;// 打印当前成员string indent(level * 2, ' ');cout << indent << root->name << endl;// 递归打印所有子女for (auto child : root->children) {print_family_tree(child, level + 1);}}void setup_family_tree() {// 创建家族树FamilyMember* grandfather = new FamilyMember{"张国强"};FamilyMember* father1 = new FamilyMember{"张明"};FamilyMember* father2 = new FamilyMember{"张亮"};FamilyMember* son1 = new FamilyMember{"张小明"};FamilyMember* son2 = new FamilyMember{"张小亮"};FamilyMember* daughter = new FamilyMember{"张丽"};// 建立关系grandfather->children.push_back(father1);grandfather->children.push_back(father2);father1->children.push_back(son1);father1->children.push_back(daughter);father2->children.push_back(son2);// 打印家族树print_family_tree(grandfather);}