2023.7.27 学习笔记

常规
1

堆 & 堆排序

二叉堆删除：

  • 删除操作指删除堆中最大的元素， 即删除根节点
  • 但是如果直接删除， 则变成了两个堆， 难以处理
  • 所以不妨考虑插入删除的逆过程， 设法将根节点移到最后一个节点， 然后直接删掉。
  • 然而实际上不好做， 我们通常采用的方法是把根节点和最后一个节点直接交换。
  • 于是直接删掉（最后一个节点处的）根节点， 但是新的根节点不满足堆的性质。
  • 向下调整：找它儿子中最大的进行交换， 重复此过程直到最底层。
  • 可以证明：删除后没有其他节点不满足堆性质

实现

struct Priority_queue
{
	int heap[MAX];//定义一个数组来存堆
	int tot = 0;//堆大小
	void push(int k)
	{//要插入的数
		heap[++tot] = k;
		int u = tot;
		while(u)//还没到根节点，还能交换
		{
			int fa = u >> 1; //找到他的父亲
			if(heap[fa] < heap[u])
				swap(heap[fa], heap[u]);// 父亲比他小， 那就交换
			else break; // 如果比它父亲小就交换。
			u = fa;
		}
	}
	
	void push_down(int u)
	{
		while(ls(u) <= tot)
		
		if(heap[u] < max(heap[ls(u)], heap[rs(u)])) //ls(u) 即 u << 1，指左儿子，rs(u)为 u << 1 | 1
		{
			if(rs(u) <= tot && heap[rs(u)] > heap[ls(u)])
				swap(heap[u], heap[rs(u)]), u = rs(u);
			else 
				swap(heap[u], heap[ls(u)]), u = ls(u);
		}
		else break;
	}
	
	void pop()
	{
		swap(heap[tot], heap[1]);
		tot--;//交换堆顶和堆底， 然后直接弹出堆底
		push_down(1);
	}
	
	void build()
	{
		for(int i = N / 2;i;i--)
			push_down(i);//维护堆的性质
	}
}

二叉堆并不会完全被 priority_queue 所替代， 因为手写堆支持修改堆中任意位置的元素， 并保持堆的性质。但 priority_queue 不行， 直接修改优先队列中的元素并不会出发其自身的结构调整。

比如堆优化Dijkstra， 使用优先队列的复杂度是 $O(n \log(n + m))$， 手写堆只有 $n \log n$。

例题1:[最小函数值]
堆维护每组函数取值， 并一个一个取。

例题2:[序列合并]
a_1 + b_1 \le a_1 + b_2 \le ... \le a_1 + b_n
维护这样每行元素的队首， 从中一边取最小值一遍调整即可

O(n \log n)

例题3:[合并果子]

一眼贪心， 每次取最小的两堆合并后放回去即可。用我们强大的堆排（priority_queue）维护就可以过了。

感觉不如set

例题4:哈夫曼编码

提取出每个字母出现次数， 让出现次数最小的在深度最深的位置，
把编码树画出来。

例题5：堆排序

  • 使用堆进行排序
  • 先建立大根堆，然后每次把和堆顶和堆中最后一个元素交换（视做删除这个元素）
  • 调整堆
  • 这样子元素从大到小排序即可。

并查集

删除：局限性高， 只能删叶子结点， 把爹变成自己即可

移动：直接换爹。

并查集的复杂度：

  • 空间复杂度显然为 O(n)
  • 时间复杂度在用了路径压缩和启发式合并后可以到反阿克曼函数级别。

应用：Kruskal.

例题：[星球大战]

反向思维， 删边改为加边， 方便并查集判断联通。

STL

  • sort(cmp函数或重载运算符)
    (重载运算符可以视为一种特殊的函数运算， 可以更加连贯、舒服)
  • pair：一个存储二元组的结构， 可以作为基本数据单元放到map， set里。而且自带双关键字比较操作， 第一关键字高于第二关键字
    ，可以通过嵌套实现多元组结构，并且拥有灵活的优先级设定。用.first、.second查询。
  • vector, 一个可增长数组， 可以直接使用数组访问， 任意位置插入时间为 O(n) ， 末尾插入为 O(1).
    语法：
vector<int> v;//初始为空
v.push_back(233);
v.pop_back();
v.size();
v.capacity();//返回能容纳的元素个数 capacity>=size
v.resize(10);//将size改为10
v.reserve(20);将capacity改为20
cout << v[2]; v[3] == 666;
cin >> v.at(2);v.at(3) = 666;// at访问， 会自动检查越界。
v.clear();//清空vector
vector<vector<int> > vv;//vector 套 vector（一定要有空格）
  • queue:一个封装好的队列。
  • priority_queue:一个封装好的优先队列(堆)
priority_queue<int> heap;
heap.push(233)
heap.top();
heap.pop();
  • map;一个映射， 第一个参数是关键字， 第二个是关键字的值，可被认为是一个下标无限大的数组， 内有一棵红黑树， 元素默认按关键字非降序排列。可以通过迭代器.first获取关键字,迭代器.second获取值。
  • unordered_map:几乎和map一样， 不过不需要排序， 时间复杂度O(1)，但不能存重复元素。
  • set 懂的都懂。
  • multiset 比起set可以重复。可以用count()统计同一个值出现多少次

pb_ds库 红黑树：

#include <ext/pb_ds/tree_policy.hpp>

#intlude <ext/pb_ds/assoc_container.hpp>

tree<int, null_type, less, rb_tree_tag, tree_order_statistics_node_update> T;

T.insert(9);T.erase(9);T.order_of_key(9);（排名）

T.find_by_order(k);（第k大）T.lower_bound(9);

小组成员：邵品渊， 邵品砚， 蒋佳成， 顾天泽， 马天翔， 陈继禹

2 个赞