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 now=heapsize; while(now>1){ int parents=now>>1;//寻找父节点 if(heap[now]>heap[parents]){//子大则交换 swap(heap[now],heap[parents]); now=parents;//继续向上 }else break;//满足性质，退出 } }2.2 出堆 (Pop) —— 下沉操作
思路：
取出堆顶元素（即最大值）。
为了保持完全二叉树的形态，将堆底元素移动到堆顶，并将堆长度减 1。
从新的堆顶开始，与其左右子节点中较大的那个进行比较。
如果当前节点 < 较大的子节点，则交换，并继续向下比较。
直到无法交换或沉到底部。
注意：在判断左右儿子大小时，要确保逻辑独立，先选出最大的儿子，再和父节点比较。
int h_pop(){ int ans=heap[1];//记录最大值 swap(heap[1],heap[heapsize]);//堆尾移至堆顶 heapsize--;//长度减1 int now=1; while(now*2<=heapsize){//只要有左儿子 int nxt=now*2;//默认较大的儿子是左儿子 //如果右儿子存在，且右儿子>左儿子，则较大的儿子是右儿子 if(nxt+1<=heapsize&&heap[nxt+1]>heap[nxt]) nxt++; //比较：如果当前节点<较大的儿子，则下沉 if(heap[now]<heap[nxt]){ swap(heap[now],heap[nxt]); now=nxt;//继续向下 }else break;//满足堆性质，停止 } return ans; }3. 完整代码实现
#include<iostream> #include<algorithm> using namespace std; const int MAXN=100;//适当扩大数组防止越界 int heap[MAXN]; int heapsize=0; //打印堆（调试用） void print(){ for(int i=1;i<=heapsize;i++)cout<<heap[i]<<" "; cout<<endl; } //入堆：上浮 void h_push(int k){ heap[++heapsize]=k; int now=heapsize; while(now>1){ int parents=now>>1; if(heap[now]>heap[parents]){ swap(heap[now],heap[parents]); now=parents; }else break; } } //出堆：下沉 int h_pop(){ if(heapsize==0)return -1;//空堆保护 int ans=heap[1]; swap(heap[1],heap[heapsize]); heapsize--; int now=1; while(now*2<=heapsize){ int nxt=now*2;//左儿子 //判断是否存在右儿子且右儿子更大 if(nxt+1<=heapsize&&heap[nxt+1]>heap[nxt]) nxt++; //与较大的儿子比较 if(heap[nxt]>heap[now]){ swap(heap[nxt],heap[now]); now=nxt; }else break; } return ans; } int main(){ //模拟输入9个数字 cout<<"Please enter 9 integers:"<<endl; for(int i=1;i<=9;i++){ int tmp; cin>>tmp; h_push(tmp); } cout<<"Current Heap: "; print(); cout<<"Popped Max Element: "<<h_pop()<<endl; cout<<"Heap 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 i=1;i<=9;i++) cout<<heap[i]<<" "; } void h_push(int k){ heap[++heapsize]=k; int now=heapsize;//当前存入元素在堆的末尾 int parents; while(now>1){//当now=1时，已经没有父节点 parents=now/2; if(heap[now]>heap[parents])//当now节点大于父节点就交换彼此位置 { swap(heap[now],heap[parents]); now=parents; } else break;//当不大于父节点时就直接退出循环了 } } int main() { for(int i=1;i<=9;i++){ int tmp; cin>>tmp; h_push(tmp);//每次给堆增加一个元素 } print(); return 0; } */ //手动实现堆操作 堆的删除 大根堆 先创建堆，然后再删除堆顶元素，删除堆顶元素需要先把堆顶和堆底交换然后heapsize--，就删除了原始堆顶，接下来需要把堆下沉,即把堆顶元素和子节点比较，如果子节点大于当前元素就交换，递归下去，如果大于等于就结束，每次输出被弹出的元素 #include <iostream> using namespace std; int heap[10]; int heapsize; int h_pop(){//删除堆顶元素 int ans=heap[1]; swap(heap[1],heap[heapsize]);//先把堆顶和堆底交换 heapsize--;//删除堆底元素 //接下来从堆顶now节点开始与儿子节点进行比较，因为是大根堆，所以与儿子中较大值进行交换（如果now节点小于now儿子较大值） int now=1;//堆顶 while(now*2<=heapsize){//左儿子小于堆长 int nxt=now*2;//now节点左儿子 if(nxt+1<=heapsize && heap[nxt+1]>heap[nxt]){//如果右儿子也小于等于堆长，且右儿子大于左儿子 nxt++;//那么较大值为右儿子 否则较大值就还是左儿子 } if(heap[nxt]>heap[now]){//如果儿子大于now节点 swap(heap[nxt],heap[now]); now=nxt; } else break;//now节点大于儿子中较大值结束循环 } return ans; } void print(){ for(int i=1;i<=heapsize;i++) cout<<heap[i]<<" "; } void h_push(int k){ heap[++heapsize]=k; int now=heapsize; while(now>1){ int parents=now>>1; if(heap[now]>heap[parents]){ swap(heap[now],heap[parents]); now=parents; } else break; } } int main(){ for(int i=1;i<=9;i++){ int tmp; cin>>tmp; h_push(tmp); } print(); cout<<endl; cout<<h_pop()<<endl;//删除堆顶元素 print(); }
