成都网站建设987net,运维需要掌握哪些知识,网络技术服务是干什么的,昆明网站制作工具自己写一个堆首先#xff0c;明确一下#xff0c;为什么需要堆#xff1f;考虑插入#xff0c;删除#xff0c;查找的效率。数组#xff0c;查找#xff0c;最快是二分查找O(lgN)。但查找完如果要做什么操作#xff0c;比如删除#xff0c;就要挪动元素了。所以合…自己写一个堆首先明确一下为什么需要堆考虑插入删除查找的效率。数组查找最快是二分查找O(lgN)。但查找完如果要做什么操作比如删除就要挪动元素了。所以合起来效率是O(lgN)O(N)O(N)二叉树看起来是O(lgN)但之前写树的时候有说过链表是不是树是树的退化形态每个结点都有小于等于一个的儿子。这个时候查找的效率是O(lgN)了。之前说查找之后万一要做什么操作树就可能不是完全二叉树即查找效率为O(lgN)。能不能试图用平衡二叉树不能rotate非常麻烦。所以尝试保持一颗完全二叉树给这棵树起名堆。接下来考虑需要用什么基础的数据结构存储。需要指针吗完全二叉树是每一个结点要么没有儿子要么有两个儿子在堆里只有最后一个有儿子的父节点可以只有左儿子。所以完全可以用数组表示。假如链表下标从1开始2和3是它的子节点2/213/21父节点访问也很方便。初始化表示这棵树需要几个数据总容量现在有多少元素以及存放元素的数组。初始化需要提供总容量。插入元素为确保是一个完全二叉树插在最后。堆需要确保一件事情小元素在上大元素在下。所以需要向上进行一次数据交换寻找插入值的最终位置。注意这里说的是寻找不需要真的交换只需要挪动不符合要求的元素找到插入值的最终位置赋值即可。删除元素删除一定是删最小的。其余和插入一样。为确保是一个完全二叉树将最后一个元素和被删除的第一个元素交换然后向下寻找最终位置。4. 一个数组的插入为了保证堆的性质插入数组后需要排序。思考一下哪些需要排序如果向下调整位置则叶子结点不需要轮。如果向上调整位置则根节点不需要轮。效率为重叶子结点最多如果向上调整则叶子结点需要轮的距离最远。而事实上叶子结点又占了树结点的很大一部分。所以我们选择向下调整。完整代码包括测试#includeiostream
using namespace std;
class h{
private:int *nums;int capacity;int l;
public:h(){capacity0;}void init(int c1){capacityc;l0;numsnew int [c1];}void printh(){for(int i1;il;i){coutnums[i] ;}coutendl;}int isfull(){if(capacityl){return 1;}return 0;}void moveup(int k){int tempnumnums[k];int ik;for(i;tempnumnums[i/2]i1;i/2){nums[i]nums[i/2];}nums[i]tempnum;}int insert(int n){if(isfull()){return 0;}nums[l1]n;l;moveup(l);return 1;}int isempty(){if(l0){return 1;}return 0;}void movedown(int k){int tempnumnums[k];int ik;while(i*2l){int childi*2;if(childl){if(nums[child]nums[child1]){child;}}if(nums[child]tempnum){nums[i]nums[child];ichild;}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 c0){if(lenc){clen;}init(c);llen;for(int i0;ilen;i){nums[i1]a[i];}for(int ilen/2;i1;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()。#includeiostream
#includequeue
using namespace std;
int main(){priority_queueintq1;int a[6]{111,222,333,11,22};for(int i0;i5;i){q1.push(a[i]);}coutq1.top()endl;q1.pop();coutq1.top()endl;
}堆额外有一种方法让其变为小顶堆即提供一个容器前提是这个容器支持从小到大排序比如vector。可以借助以下程序验证。#includeiostream
#includequeue
#includevector
using namespace std;
int main(){priority_queueint,vectorint,greaterint q1;int a[5]{111,222,333,11,22};for(int i0;i5;i){q1.push(a[i]);}for(int i0;i5;i){coutq1.top()endl;q1.pop();}
}3. c的集合集合就是set嘛之前刷题用了好多次了。注意三点set默认从小到大排序因为底层实现是红黑树类似AVL树set.insert()也可以插入集合方法详见下方实验代码对于力扣中要求返回vector但你用set做了只要返回{set.begin(), set.end()}即可可以用以下代码验证set#includeiostream
#includeset
using namespace std;
int main(){setints1;int a1[3]{333,222,111};for(int i0;i3;i){s1.insert(a1[i]);}for(auto x:s1){coutx ;}coutendl;setints2;s2.insert(666);s2.insert(555);s1.insert(s2.begin(),s2.end());for(auto x:s1){coutx ;}coutendl;
}
