堆

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

本片将包括：

目录

• 堆
  • （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：

void push(int x){
    heap[len++]=x;
    int i=len;
    while(i>1&&heap[i]<heap[i/2]){
        swap(heap[i],heap[i/2]);
        i=i/2;
	}
}

2.下沉

某个节点的优先级下降，或将根节点替换为为一个优先级更高的元素（弹出堆顶），此时需要从上到下维护堆的顺序。

如下图：

code：

void pop(){
    heap[1]=heap[len--];
    int i=1;
    while(2*i<n){
        int son=2*n;
        if(son<len&&heap[son+1]<heap[son])
            son++;
        if(heap[son]<heap[i]){
            swap(heap[son],heap[i]);
            i=son;
        }
        else 
            break;
    }
}

3.查询堆顶

根据上述内容可知， \(heap[1]\) 即为堆顶

int top(){
    return heap[1];
}

4.查询大小

即判断 \(len\) 是否为0。

int size(){
   return len; 
}

5.判断是否为空

bool empty(){
    if(len==0) return true;
    return false;
}

（3.堆与priority_queue

STL中的优先队列（priority_queue）是用堆实现的。

1.初始化

在STL中优先队列的初始化：

priority_queue<int>                                //默认为大根堆
priority_queue<int,vector<int>,less<int> >s1;      //大顶堆
//vector是存放的容器，less为优先级
priority_queue<int,vector<int>,greater<int> >s2;   //小顶堆

2.操作

（3.例题

1. P3378 【模板】堆（模版题，没什么好说的）
2. P1090 合并果子（比起用数组，堆更加简单）
3. P1631 序列合并