【数据结构】堆和集合笔记
自己写一个堆
首先，明确一下，为什么需要堆？
=>考虑插入，删除，查找的效率。
数组，查找，最快是二分查找O(lgN)。但查找完如果要做什么操作，比如删除，就要挪动元素了。所以合起来效率是O(lgN)+O(N)=O(N)
二叉树，看起来是O(lgN)，但之前写树的时候有说过，链表是不是树？是树的退化形态，每个结点都有小于等于一个的儿子。这个时候查找的效率是O(lgN)了。之前说，查找之后万一要做什么操作，树就可能不是完全二叉树，即查找效率为O(lgN)。
能不能试图用平衡二叉树？不能，rotate非常麻烦。
=>所以尝试保持一颗完全二叉树=>给这棵树起名堆。
接下来考虑需要用什么基础的数据结构存储。
需要指针吗？
完全二叉树是每一个结点要么没有儿子，要么有两个儿子，在堆里只有最后一个有儿子的父节点可以只有左儿子。所以完全可以用数组表示。
假如链表下标从1开始，2和3是它的子节点，2/2=1，3/2=1，父节点访问也很方便。
初始化
表示这棵树需要几个数据：总容量，现在有多少元素，以及存放元素的数组。
初始化需要提供总容量。
插入元素
为确保是一个完全二叉树，插在最后。
堆需要确保一件事情，小元素在上，大元素在下。所以需要向上进行一次数据交换，寻找插入值的最终位置。
注意，这里说的是寻找，不需要真的交换，只需要挪动不符合要求的元素，找到插入值的最终位置赋值即可。
删除元素
删除一定是删最小的。其余和插入一样。
为确保是一个完全二叉树，将最后一个元素和被删除的第一个元素交换，然后向下寻找最终位置。
4. 一个数组的插入
为了保证堆的性质，插入数组后需要排序。
思考一下，哪些需要排序？
如果向下调整位置，则叶子结点不需要轮。如果向上调整位置，则根节点不需要轮。
效率为重，叶子结点最多，如果向上调整，则叶子结点需要轮的距离最远。而事实上，叶子结点又占了树结点的很大一部分。
所以我们选择向下调整。
完整代码（包括测试）
#include
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<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(childnums[child+1]){child++;}}if(nums[child]c){c=len;}init(c);l=len;for(int i=0;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
#include
using namespace std;
int main(){priority_queueq1;int a[6]={111,222,333,11,22};for(int i=0;i<5;i++){q1.push(a[i]);}cout< 堆额外有一种方法让其变为小顶堆，即提供一个容器，前提是这个容器支持从小到大排序，比如vector。
可以借助以下程序验证。
#include
#include
#include
using namespace std;
int main(){priority_queue,greater >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< 3. c++的集合
集合就是set嘛，之前刷题用了好多次了。
注意三点：
set默认从小到大排序（因为底层实现是红黑树，类似AVL树）
set.insert()也可以插入集合，方法详见下方实验代码
对于力扣中要求返回vector但你用set做了，只要返回{set.begin(), set.end()}即可
可以用以下代码验证set
#include
#include
using namespace std;
int main(){sets1;int a1[3]={333,222,111};for(int i=0;i<3;i++){s1.insert(a1[i]);}for(auto x:s1){cout<s2;s2.insert(666);s2.insert(555);s1.insert(s2.begin(),s2.end());for(auto x:s1){cout<