堆

堆

堆是一种树形结构，树的根是堆顶，堆顶始终保持为所有元素中优先级最高的元素，如小根堆与大根堆，小根堆的堆顶始终为最小的元素，大根堆的堆顶始终保持为最大的元素。堆一般用二叉树实现，称为二叉堆。二叉堆的典范应用有堆排序和优先队列。
本片将包括：

目次

• 堆
  
  
  
  • （1.二叉堆的概念
    
  • （2.二叉堆的使用
    
    
    
    • 1.上浮
      
    • 2.下沉
      
    • 3.查询堆顶
      
    • 4.查询大小
      
    • 5.判断是否为空
      
    
    
  • （3.堆与priority_queue
    
    
    
    • 1.初始化
      
    • 2.使用
      
    
    
  • （3.例题
    
  
  

（1.二叉堆的概念

二叉堆是一棵完全二叉树。用数组实现的二叉树堆，树中每个节点与数组存放的元素对应。如图所示，用数组实现一棵二叉堆。

二叉堆中的每个节点，都是以它为父节点的子树的最小值。
​        用数组存储完全二叉树，节点数量为 \(n\) ， \(a[1]\) 为根，通过上图不难发现如下性质：
​        (1) 对于所有 \(i>1\) 的节点，其父节点为 \(i/2\) ;
​        (2) 若 \(2i>n\) ,则 \(i\) 节点无子节点；若  \(2i+1>n\) 则 \(i\) 无右节点；
​        (3) 若 \(i\) 节点有子节点，则左子节点在 \(2i\) ，右子节点在 \(2i+1\) ;
（2.二叉堆的使用

堆的使用有两种：上浮与下沉；
1.上浮

某个节点的优先级上升，或在堆底新到场一个元素(建堆，把新元素到场堆)，此时需要从上到下恢复堆的次序。
如下图：

code：
[code]void push(int x){    heap[len++]=x;    int i=len;    while(i>1&&heap