堆

堆可以理解成一种很想树的数据结构

它可以分为两类

小顶堆
大顶堆

简单介绍一下小顶堆堆特点

每一个父节点满足值小于两个左右子结点

这样保证了根结点保存的就是最小的值

堆的左右子结点

假如父节点是1，那么左结点为2，右结点为3

同理父亲为2，左右分别为4和5

所以我们可以得出结论父节点为n ，父节点的左结点为2 * n，右结点为2 * n + 1

针对堆这种数据结构，主要用来处理以下问题

如何添加元素

heap[++size] = res

如何删除元素

堆和链表不同，如果我们想要删除头结点，是很不方便的，但是如果想要删除尾部结点很容易，于是我们可以通过heap[1] = heap[size] size--; down[i]的方式来解决该问题

如何获取最小值

heap[1]

Down函数

down函数遵循上面的小顶堆的规则

将插入的元素(比较大的)，通过down函数放入到这个堆中的指定位置

示例代码

void down(int u) {
		int t = u;
  	if(heap[t] > heap[u * 2]) t = u * 2; //比较左结点
  	if(heap[t] > heap[u * 2 + 1]) t = u * 2 + 1; //比较右结点
  	//u != t说明左右结点有比当前结点小的情况
  	if(u != t) {
      	//交换最小值和当前结点，接着这种情况递归
      	swap(heap[u],heap[t]);
     		down(t);
    }
}

Up函数

将插入的元素(比较小的)，通过up函数向上面进行传递到堆的指定位置

示例代码

void up(int u) {
		while(u / 2 > 0 && heap[u / 2] > heap[u]) {
				swap(heap[u / 2],heap[u]);
				u /= 2;
		}
}

如何通过给出的一组数去构建小顶堆呢？

相当于是我们对所有插入的数进行一个down操作或者是up操作

代码模版

const int N = 1000010;
int heap[N],sz;
int main(){
		int n;
		cin >> n;
		for(int i = 1;i <= n;i++) cin >> heap[i];
		sz = n;
		for(int i = n / 2;i;i--) down[i];
		return 0;
}

为什么我们i会从n / 2开始进行呢？

因为假如我们想象一个三层的满二叉树，我们总共有4 + 3个结点，因为叶子结点是没有左右子结点的所以不需要down，我们只需要处理上面三个结点，将这三个结点放入到合适的位置即可

堆排序进阶

除了上面堆情况之外，题目中还会出现对第n个数字进行操作的可能，这个时候就需要我们去维护两个全新的数组hp和ph

hp(heap -> point) 用来获取堆中的第n个元素是第几个插入的元素

ph(point -> heap) 用来获得第几个插入的元素在堆中是第几个元素

添加元素

sz++; //用来记录堆中元素的位置
m++; //用来标记第几个元素被插入
hp[sz] = m;ph[m] = sz;h[sz] = t;
up(sz);

交换两个堆中的元素

void heap_swap(int a,int b) {
		swap(ph[hp[a]],ph[hp[b]]); //交换堆中的位置
		swap(hp[a],hp[b]); //交换插入的次序
		swap(h[a],h[b]); //交换值
}

删除第n个元素

k = ph[n];
heap_swap(k,sz);
sz--;
down(k);up(k);

修改第n个元素

k = ph[n];
h[k] = t;
down(k);up(k);

注意：最后两种操作，操作后是不满足小顶堆的条件的，我们同时调用down和up本质上只会执行其中的一个