核工业华南建设集团网站珠海seo海网站建设

核工业华南建设集团网站,珠海seo海网站建设,杭州网站建设外包,做网站需要的大图1. 堆的基本原理 堆是一棵完全二叉树。 大根堆#xff1a;任意节点的值 $\ge$ 其子节点的值#xff08;堆顶最大#xff09;。 小根堆#xff1a;任意节点的值 $\le$ 其子节点的值#xff08;堆顶最小#xff09;。 存储方式 我们使用一个数组 heap[] 来存储堆…1. 堆的基本原理堆是一棵完全二叉树。大根堆任意节点的值 $\ge$ 其子节点的值堆顶最大。小根堆任意节点的值 $\le$ 其子节点的值堆顶最小。存储方式我们使用一个数组heap[]来存储堆索引从1开始这样对于任意节点now父节点now / 2(或now 1)左子节点now * 2(或now 1)右子节点now * 2 1(或now 1 | 1)2. 核心操作详解2.1 入堆 (Push) —— 上浮操作思路将新元素插入到堆的末尾(heapsize)。将该元素与其父节点比较。如果新元素 父节点则交换两者swap并继续向上比较。直到无法交换满足堆性质或到达堆顶。void h_push(int k){ heap[heapsize]k;//插入末尾 int nowheapsize; while(now1){ int parentsnow1;//寻找父节点 if(heap[now]heap[parents]){//子大则交换 swap(heap[now],heap[parents]); nowparents;//继续向上 }else break;//满足性质退出 } }2.2 出堆 (Pop) —— 下沉操作思路取出堆顶元素即最大值。为了保持完全二叉树的形态将堆底元素移动到堆顶并将堆长度减 1。从新的堆顶开始与其左右子节点中较大的那个进行比较。如果当前节点 较大的子节点则交换并继续向下比较。直到无法交换或沉到底部。注意在判断左右儿子大小时要确保逻辑独立先选出最大的儿子再和父节点比较。int h_pop(){ int ansheap[1];//记录最大值 swap(heap[1],heap[heapsize]);//堆尾移至堆顶 heapsize--;//长度减1 int now1; while(now*2heapsize){//只要有左儿子 int nxtnow*2;//默认较大的儿子是左儿子 //如果右儿子存在且右儿子左儿子则较大的儿子是右儿子 if(nxt1heapsizeheap[nxt1]heap[nxt]) nxt; //比较如果当前节点较大的儿子则下沉 if(heap[now]heap[nxt]){ swap(heap[now],heap[nxt]); nownxt;//继续向下 }else break;//满足堆性质停止 } return ans; }3. 完整代码实现#includeiostream #includealgorithm using namespace std; const int MAXN100;//适当扩大数组防止越界 int heap[MAXN]; int heapsize0; //打印堆调试用 void print(){ for(int i1;iheapsize;i)coutheap[i] ; coutendl; } //入堆上浮 void h_push(int k){ heap[heapsize]k; int nowheapsize; while(now1){ int parentsnow1; if(heap[now]heap[parents]){ swap(heap[now],heap[parents]); nowparents; }else break; } } //出堆下沉 int h_pop(){ if(heapsize0)return -1;//空堆保护 int ansheap[1]; swap(heap[1],heap[heapsize]); heapsize--; int now1; while(now*2heapsize){ int nxtnow*2;//左儿子 //判断是否存在右儿子且右儿子更大 if(nxt1heapsizeheap[nxt1]heap[nxt]) nxt; //与较大的儿子比较 if(heap[nxt]heap[now]){ swap(heap[nxt],heap[now]); nownxt; }else break; } return ans; } int main(){ //模拟输入9个数字 coutPlease enter 9 integers:endl; for(int i1;i9;i){ int tmp; cintmp; h_push(tmp); } coutCurrent Heap: ; print(); coutPopped Max Element: h_pop()endl; coutHeap after Pop: ; print(); return 0; }4. 复杂度分析时间复杂度h_push: 最坏情况是从叶子浮到根高度为 log N所以是 O(log N)。h_pop: 最坏情况是从根沉到叶子高度为 log N所以是 O(log N)。空间复杂度O(N)用于存储数组。5. 总结手动实现堆的关键在于理解“完全二叉树”的数组映射关系。上浮 (Up)用于插入确保新来的“大将”能坐到正确的高位。下沉 (Down)用于删除旧王退位选出的新王可能能力不足需要退居到合适的位置。掌握这套逻辑后不仅能手写优先队列还能轻松解决“Top K 问题”或手写“堆排序”。附原始代码/* //手动实现堆操作 堆的增加 大根堆 #include iostream using namespace std; int heap[10];//堆 int heapsize;//堆长度 void print(){ for(int i1;i9;i) coutheap[i] ; } void h_push(int k){ heap[heapsize]k; int nowheapsize;//当前存入元素在堆的末尾 int parents; while(now1){//当now1时已经没有父节点 parentsnow/2; if(heap[now]heap[parents])//当now节点大于父节点就交换彼此位置 { swap(heap[now],heap[parents]); nowparents; } else break;//当不大于父节点时就直接退出循环了 } } int main() { for(int i1;i9;i){ int tmp; cintmp; h_push(tmp);//每次给堆增加一个元素 } print(); return 0; } */ //手动实现堆操作 堆的删除 大根堆 先创建堆然后再删除堆顶元素删除堆顶元素需要先把堆顶和堆底交换然后heapsize--就删除了原始堆顶接下来需要把堆下沉,即把堆顶元素和子节点比较如果子节点大于当前元素就交换递归下去如果大于等于就结束每次输出被弹出的元素 #include iostream using namespace std; int heap[10]; int heapsize; int h_pop(){//删除堆顶元素 int ansheap[1]; swap(heap[1],heap[heapsize]);//先把堆顶和堆底交换 heapsize--;//删除堆底元素 //接下来从堆顶now节点开始与儿子节点进行比较因为是大根堆所以与儿子中较大值进行交换如果now节点小于now儿子较大值 int now1;//堆顶 while(now*2heapsize){//左儿子小于堆长 int nxtnow*2;//now节点左儿子 if(nxt1heapsize heap[nxt1]heap[nxt]){//如果右儿子也小于等于堆长且右儿子大于左儿子 nxt;//那么较大值为右儿子 否则较大值就还是左儿子 } if(heap[nxt]heap[now]){//如果儿子大于now节点 swap(heap[nxt],heap[now]); nownxt; } else break;//now节点大于儿子中较大值结束循环 } return ans; } void print(){ for(int i1;iheapsize;i) coutheap[i] ; } void h_push(int k){ heap[heapsize]k; int nowheapsize; while(now1){ int parentsnow1; if(heap[now]heap[parents]){ swap(heap[now],heap[parents]); nowparents; } else break; } } int main(){ for(int i1;i9;i){ int tmp; cintmp; h_push(tmp); } print(); coutendl; couth_pop()endl;//删除堆顶元素 print(); }