模拟堆
堆就是一个完全二叉树
对于小根堆来说 一个结点的孩子都比自身大（大根堆就是孩子都小于当前结点）
可以看出一种关系
对于结点1来说（n=1） 左孩子为2(2n) 右孩子为3(2n+1)
对于结点2来说 (n=2) 左孩子为4(2n) 右孩子为5(2n+1)
所以完全可以使用数组下标的n，2n，2n+1的关系去模拟这样的结构
当然 是从下标1开始使用才有意义（从0开始的话 2n还是0 没意义）
就有两种方式
如果无需管当前数是第几个数 就直接在数组中存放值（数不作对应 就简单值排序）
如果需要知道当前数是第几个数 就需要类似于模拟链表那样 用一个数组存值 另一个数组维护他们之间的物理关系（数与插入在数组时的位置仍一一对应 主要是找第k位置用）
对于堆来说 一般就是进行五个操作
（1）插入一个数
（2）求集合中该点最小值
（3）删除最小值
（4）删除任意一个元素
（5）修改任意一个元素
两个实现
down(){……}
up(){……}
核心就是在于堆的调整 使其永远保持最值在上的特性
不论是操作还是构建 都是一个调整的过程
看看调整的思路（小根堆）
down:
这个1号位置的9 比2、3（2n,2n+1）位置的值都要大 所以要想办法沉下去
那么 就从是三个点里找到一个最小值 把他们位置交换一下
然后9换到了3号位置 与2n的6号位置去比（2n+1位置不存在） 还是更大 所以还要换
当交换到不能交换的时候 整颗树就又满足小根堆的性质了
void down(int u){
int t = u;//记录最值
if (2 * u <= Size && h[t] > h[2 * u])
t = 2 * u;
if (2 * u + 1 <= Size && h[t] > h[2 * u + 1])
t = 2 * u + 1;
if (u != t){
swap(h[u], h[t]);
down(t);
}
}
up:
up就简单很多 只需要与父节点去比 如果更小就与父节点换一下（还是小根堆为例）
5号位置的4不符合小根堆性质 需要调整
5/2=2的位置的点 也就是6去比 4<6 交换位置
（很巧妙的就是 不论是左孩子还是右孩子 都可以使用/2的方式找到父结点 ）
再继续往上调整
2/2=1 去与1中的5比 4<5 交换位置
这样一来 就满足了小根堆的性质
void up(int u){
if(u/2>0&&h[u]<h[u/2])
{
swap(h[u],h[u/2]);
up(u>>1);
}
}
五种操作
对于那五种操作其实就是变相的使用down、up进行调整
插入一个数
就在堆的最后一个位置（数组的可用位置处）加上一个x
heap[++size]=x;
然后不断对它进行调整
up(size);
即可
求集合当中的最小值
其实就是堆形成后的堆顶元素
heap[1];
删除第一个元素
考虑两个问题 删除后 堆可能就发生了变化可能性质就没满足 需要调整
其二 用的是数组存储 删除元素当然还是删末尾的容易 这样无需挪动元素
所以 把最后一个元素 替换掉第一个元素 然后size-- 把最后一个元素删掉 再不断对这个n挪上来的元素进行down调整
heap[1]=heap[size];
size--;
down(1);
删除任意一个元素
同理
把最后一个元素挪过来 但是这里情况有点不一样 它可能往上调整也可能往下调整
不像前面一定是向下调整 所以可能还需要判断一下是进行up还是down
实际可以不用 因为down up内部都是有判断的 所以完全可以直接调用两个 它自己会选择一个进去
heap[k]=heap[size];
size--;
down[k];up[k];//只会执行一个
修改任意一个元素
heap[k]=x;
down[k];
up[k];
💬 评论