堆
堆堆是一种树形结构，树的根是堆顶，堆顶始终保持为所有元素中优先级最高的元素，如小根堆与大根堆，小根堆的堆顶始终为最小的元素，大根堆的堆顶始终保持为最大的元素。堆一般用二叉树实现，称为二叉堆。二叉堆的典范应用有堆排序和优先队列。
本片将包括：
目次
[*]堆
[*]（1.二叉堆的概念
[*]（2.二叉堆的使用
[*]1.上浮
[*]2.下沉
[*]3.查询堆顶
[*]4.查询大小
[*]5.判断是否为空
[*]（3.堆与priority_queue
[*]1.初始化
[*]2.使用
[*]（3.例题
（1.二叉堆的概念
二叉堆是一棵完全二叉树。用数组实现的二叉树堆，树中每个节点与数组存放的元素对应。如图所示，用数组实现一棵二叉堆。
https://file.uhsea.com/2403/8d94743deca542644f5263eefeb18d5b4X.png
二叉堆中的每个节点，都是以它为父节点的子树的最小值。
用数组存储完全二叉树，节点数量为 \(n\) ， \(a\) 为根，通过上图不难发现如下性质：
(1) 对于所有 \(i>1\) 的节点，其父节点为 \(i/2\) ;
(2) 若 \(2i>n\) ,则 \(i\) 节点无子节点；若\(2i+1>n\) 则 \(i\) 无右节点；
(3) 若 \(i\) 节点有子节点，则左子节点在 \(2i\) ，右子节点在 \(2i+1\) ;
（2.二叉堆的使用
堆的使用有两种：上浮与下沉；
1.上浮
某个节点的优先级上升，或在堆底新到场一个元素(建堆，把新元素到场堆)，此时需要从上到下恢复堆的次序。
如下图：
https://file.uhsea.com/2403/4f6f45bea96d7d57f4cc354eda40f602RG.jpg
code：
void push(int x){ heap=x; int i=len; while(i>1&&heap
页:
[1]