首页 > 代码库 > 《啊哈！算法》第7章 神奇的树
《啊哈！算法》第7章 神奇的树
第3节 堆排序
把n个元素建立一个堆，首先将这n个结点以自顶向下、从左到右的方式从1到n编码，这样可以把n个结点转换成一颗完全二叉树
紧接着从最后一个非叶子结点（结点编号为n/2）开始到根节点（结点编号为1），逐个扫描所有结点，根据需要将当前结点向下调整，直到以当前结点为根结点的子树符合堆的特性。
#include <iostream>#include <vector>#include <algorithm>using namespace std;//向下调整函数void shiftdown(vector<int>& a, int n,int index){ while(index*2<= n ){ int t = index; if(a[t] > a[2*index]) t = 2*index; if( 2*index+1 <= n && a[t] > a[2*index+1] ) t = 2*index+1; if(t!=index) {swap(a[t],a[index]); index = t;} else break; }}//删除最大的元素int deletemax(vector<int>& a , int& n){ int res = a[1]; swap(a[1],a[n]); n--; shiftdown(a,n,1); return res;}//向上调整函数void shiftup(vector<int>& a, int n, int index){ if(index == 1) return; while(index!=1){ if(a[index] < a[index/2]) swap(a[index],a[index/2]); else break; index/=2; }}// 创建堆void make_heap(vector<int>& a, int n){ //注意索引是从0开始的 for(int i = n/2; i> 0; -- i){ shiftdown(a,n,i); } }void heap_sort(vector<int>& a){ int n =a.size()-1; while( n > 1){ swap(a[1],a[n]); n--; shiftdown(a,n,1); }}int main(){ int n; cin >> n; vector<int> a(n+1,0); for(int i = 1 ; i <= n; ++ i){ cin >> a[i]; } //建堆 make_heap(a,n); heap_sort(a); for(int i = 1 ; i <= n; ++ i){ cout<<a[i]<<" "; } cout<<endl; int num = n; for(int i = 1; i <= n; ++ i){ cout<<deletemax(a,num)<<endl; }}
第4节 并查集
并查集的优化有两种，一种是路径压缩，一种是按秩合并，具体的可以参考《算法导论》
/* *并查集操作 */#include <iostream>#include <vector>#include <algorithm>using namespace std;int f[1000]={0};void make_set(int size){ for(int i =1; i <= size; ++ i ) f[i] = i;}//采用路径压缩的方法查找元素int find_set(int x){ if(f[x] == x) return x; else{ f[x] = find_set(f[x]); //查找x元素所在的集合，回溯时压缩路径 return f[x]; }}void union_set(int x, int y){ int t1 = find_set(x), t2 = find_set(y); if(t1 != t2){ f[t2] = t1; }}int main(){ int n, m; cin >> n >> m; make_set(n); for(int i = 1; i<=m; ++ i){ int x,y; cin >> x >> y; union_set(x,y); } int sum = 0; for(int i = 1; i<= n; ++ i){ if(f[i] == i) sum++; } cout<<sum<<endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。