$$\Huge{二叉堆}$$

$简介$

$二叉堆是一种常见的数据结构$

$基本操作有$插入$,$删除$以及$查找最值

$二叉堆满足堆的性质,即父节点比子节点更加优秀,也被称为优先队列$

$每次只要弹出最优秀的根节点,从而快速取出所需的答案$

$二叉堆一般分为两种,小跟堆维护最小值,大根堆维护最大值$

$因为二叉堆是一颗满足堆性质的二叉树,所以可按照二叉树的存储方法$

$对于节点p,p / 2 是其父节点编号,p \times 2是其左儿子编号,p \times 2+1是其右儿子编号$

$维护堆性质$

$对于一个堆,如果想要让它通过等价交换后满足堆性质,那么就需要对节点进行上下调整$

$具体来说,对于一个不满足对性质的点,让他和相邻的点交换,直到满足堆性质为止$

$即对节点向上调整,向下调整$

$时间复杂度 O(log\ n)$

$Code$

void up(int p)//向上调整
{
    while (p > 1)
    {
        if (heap[p] < heap[p >> 1])//不满足性质,根据题意选择性质
        {
            swap(heap[p], heap[p >> 1]);//交换
            p >>= 1;
        }
        else break;
    }
}

void down(int p)//向下调整
{
    int s = p * 2;
    while (s <= n)
    {
        if (s + 1 <= n && heap[s] > heap[s + 1])s ++ ;//选择左儿子或右儿子
        if (heap[p] > heap[s])//不满足性质,根据题意选择性质
        {
            swap(heap[p], heap[s]);//交换
            p = s, s = p * 2;
        }
        else break;
    }
}

$插入$

$在二叉堆中插入一个节点$

$可以先把它插入在叶子结点$

$再根据所需堆的性质,不断与其父节点交换,直到不能换了为止$

$时间复杂度最坏O(log\ n)$

$Code$

void insert(int val)
{
    heap[++ n] = val;//加入堆
    up(n);//调整
}

$删除$

$二叉堆的删除操作支持删除堆中任意节点$

$可以先把要删的节点与堆底元素交换,删除堆底元素后不会改变堆性质$

$删除了需要删除的节点后,新换上去的点需要上下调整直到找到适合自己的位置$

$时间复杂度O(log\ n)$

$Code$

void Remove(int p)
{
    heap[p] = heap[n -- ];
    up(p), down(p);
}

$查询最值$

$查询最值,即弹出二叉堆中最优秀的节点,也就是heap[1]$

$时间复杂度O(1)$

$Code$

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

$二叉堆模版$

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n;
int heap[N];

void up(int p)//向上调整
{
    while (p > 1)
    {
        if (heap[p] < heap[p >> 1])
        {
            swap(heap[p], heap[p >> 1]);
            p >>= 1;
        }
        else break;
    }
}

void down(int p)//向下调整
{
    int s = p * 2;
    while (s <= n)
    {
        if (s + 1 <= n && heap[s] > heap[s + 1])s ++ ;
        if (heap[p] > heap[s])
        {
            swap(heap[p], heap[s]);
            p = s, s = p * 2;
        }
        else break;
    }
}

void insert(int val)//插入
{
    heap[++ n] = val;
    up(n);
}

void Remove(int p)//删除节点
{
    heap[p] = heap[n -- ];
    up(p), down(p);
}

int GetTop()//查找最值
{
    return heap[1];
}

int main()
{


    return 0;
}

$二叉堆STL$

$二叉堆在STL中使用同样快捷$

$支持$插入,查找最值$和$删除根节点$操作,但不能$删除节点

$STL版二叉堆Code$

priority_queue<int> heap;// 定义大根堆
priority_queue<int, vector<int>, greater<int>> heap;//定义小根堆
heap.push();//插入
heap.top();//查找最值
heap.pop();//弹出根节点