堆

堆结构
完全二叉树和数组前缀范围来对应，大小，单独的变量size来控制
i的父亲节点：​i/2，i的左孩子：​i*2，i的右孩子：​i*2 + 1(根节点为​1)
堆的定义（大根堆、小根堆）
大根堆：每一颗子树的根节点都比子节点“大”（可以是数值上的，也可以自己定义）
堆的调整：modiup（向上调整）、modidown（向下调整）
时间复杂度​O(log n)，完全二叉树的结构决定的

堆排序
A. 从顶到底建堆，时间复杂度​O(n * log n)，​log1 +​log2 +​log3 + … + ​logn4 -> ​O(n*logn)
或者用增倍分析法：建堆的复杂度分析+子矩阵数量的复杂度分析
B. 从底到顶建堆，时间复杂度​O(n)，总代价就是简单的等比数列关系
C. 建好堆之后的调整阶段，从最大值到最小值依次归位，时间复杂度​O(n * log n)
时间复杂度​O(n * log n)，不管以什么方式建堆，调整阶段的时间复杂度都是这个，所以整体复杂度也是这个
额外空间复杂度是​O(1)，因为堆直接建立在了要排序的数组上，所以没有什么额外空间

[[堆排序]]
每次把根节点（1）和最后一个节点交换，然后向下调整堆
如果是升序，则采用大根堆，降序用小根堆

stl里的优先队列也是用堆实现的
但是cmp重载需要提供类或者struct(不如直接在结构体里重载)

struct node{
	int val,rnd;
    bool operator < (const node&x) const {
		return rnd<x.rnd;
	}
}a[100];

Dijkstra堆优化[[Dijkstra]]