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

本片将包括:

(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.操作

操作 作用
\(qu.push(x)\) 将元素 \(x\) 加入优先队列
\(qu.pop()\) 弹出队首
\(qu.top()\) 返回队首元素(不弹出)
\(qu.size()\) 返回队列长度
\(qu.empty()\) 队列是否为空

(3.例题

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

热门相关:血战天下   纨绔仙医   神医娘亲之腹黑小萌宝   恐怖复苏   我的学姐会魔法