【数据结构】堆和集合笔记

1. 自己写一个堆

首先，明确一下，为什么需要堆？

=>考虑插入，删除，查找的效率。

数组，查找，最快是二分查找O(lgN)。但查找完如果要做什么操作，比如删除，就要挪动元素了。所以合起来效率是O(lgN)+O(N)=O(N)

二叉树，看起来是O(lgN)，但之前写树的时候有说过，链表是不是树？是树的退化形态，每个结点都有小于等于一个的儿子。这个时候查找的效率是O(lgN)了。之前说，查找之后万一要做什么操作，树就可能不是完全二叉树，即查找效率为O(lgN)。

能不能试图用平衡二叉树？不能，rotate非常麻烦。

=>所以尝试保持一颗完全二叉树=>给这棵树起名堆。

接下来考虑需要用什么基础的数据结构存储。

需要指针吗？

完全二叉树是每一个结点要么没有儿子，要么有两个儿子，在堆里只有最后一个有儿子的父节点可以只有左儿子。所以完全可以用数组表示。

假如链表下标从1开始，2和3是它的子节点，2/2=1，3/2=1，父节点访问也很方便。

1. 初始化

表示这棵树需要几个数据：总容量，现在有多少元素，以及存放元素的数组。

初始化需要提供总容量。

2. 插入元素

为确保是一个完全二叉树，插在最后。

堆需要确保一件事情，小元素在上，大元素在下。所以需要向上进行一次数据交换，寻找插入值的最终位置。

注意，这里说的是寻找，不需要真的交换，只需要挪动不符合要求的元素，找到插入值的最终位置赋值即可。

3. 删除元素

删除一定是删最小的。其余和插入一样。

为确保是一个完全二叉树，将最后一个元素和被删除的第一个元素交换，然后向下寻找最终位置。

4. 一个数组的插入

为了保证堆的性质，插入数组后需要排序。

思考一下，哪些需要排序？

如果向下调整位置，则叶子结点不需要轮。如果向上调整位置，则根节点不需要轮。

效率为重，叶子结点最多，如果向上调整，则叶子结点需要轮的距离最远。而事实上，叶子结点又占了树结点的很大一部分。

所以我们选择向下调整。

完整代码（包括测试）

#include<iostream>
using namespace std;
class h{
private:int *nums;int capacity;int l;
public:h(){capacity=0;}void init(int c=1){capacity=c;l=0;nums=new int [c+1];}void printh(){for(int i=1;i<=l;i++){cout<<nums[i]<<" ";}cout<<endl;}int isfull(){if(capacity==l){return 1;}return 0;}void moveup(int k){int tempnum=nums[k];int i=k;for(i;tempnum<nums[i/2]&&i>1;i/=2){nums[i]=nums[i/2];}nums[i]=tempnum;}int insert(int n){if(isfull()){return 0;}nums[l+1]=n;l++;moveup(l);return 1;}int isempty(){if(l==0){return 1;}return 0;}void movedown(int k){int tempnum=nums[k];int i=k;while(i*2<=l){int child=i*2;if(child<l){if(nums[child]>nums[child+1]){child++;}}if(nums[child]<tempnum){nums[i]=nums[child];i=child;}else{nums[i]=tempnum;return ;}}nums[i]=tempnum;return ;}int remove(){if(isempty()){return 0;}nums[1]=nums[l];l--;movedown(1);return 1;}void buildheap(int *a,int len,int c=0){if(len>c){c=len;}init(c);l=len;for(int i=0;i<len;i++){nums[i+1]=a[i];}for(int i=len/2;i>=1;i--){movedown(i);}}
};
int main(){int a[6]={10,50,60,5,30,20};h h1;h1.buildheap(a,6);h1.printh();
}

2. c++的堆

堆在queue中，叫priority_queue，默认是大顶堆，即树根是最大的元素，可以执行一下验证。

所以插入是push，查看堆顶元素是top()，弹出堆顶是pop()。

#include<iostream>
#include<queue>
using namespace std;
int main(){priority_queue<int>q1;int a[6]={111,222,333,11,22};for(int i=0;i<5;i++){q1.push(a[i]);}cout<<q1.top()<<endl;q1.pop();cout<<q1.top()<<endl;
}

堆额外有一种方法让其变为小顶堆，即提供一个容器，前提是这个容器支持从小到大排序，比如vector。

可以借助以下程序验证。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){priority_queue<int,vector<int>,greater<int> >q1;int a[5]={111,222,333,11,22};for(int i=0;i<5;i++){q1.push(a[i]);}for(int i=0;i<5;i++){cout<<q1.top()<<endl;q1.pop();}
}

3. c++的集合

集合就是set嘛，之前刷题用了好多次了。

注意三点：

1. set默认从小到大排序（因为底层实现是红黑树，类似AVL树）

2. set.insert()也可以插入集合，方法详见下方实验代码

3. 对于力扣中要求返回vector但你用set做了，只要返回{set.begin(), set.end()}即可

可以用以下代码验证set

#include<iostream>
#include<set>
using namespace std;
int main(){set<int>s1;int a1[3]={333,222,111};for(int i=0;i<3;i++){s1.insert(a1[i]);}for(auto x:s1){cout<<x<<" ";}cout<<endl;set<int>s2;s2.insert(666);s2.insert(555);s1.insert(s2.begin(),s2.end());for(auto x:s1){cout<<x<<" ";}cout<<endl;
}