头文件：#include<algorithm>

1.什么是堆：
堆是一种数组对象，其形式可以看做是一棵完全二叉树。二叉树的Node（或Vertex）
与数组（array）中的元素一一对应（也说明它的存储方式是数组）。通俗来讲，对就是一棵
存储数据相对有序的完全二叉树。
那么完全二叉树又是个啥玩意儿呢？众所周知，树是有深度的，假设一棵二叉树深度为X
（Root是第0层）则第X-1层的Node数量必须满足2^X个且最下面的节点都必须集中在这棵树的最
左边位置，即是完全二叉树（如图"A"）。
图片说明
了解了完全二叉树后，我们再回到堆。堆分为大根堆（Max-heap）与小根堆（Min-heap）
大根堆指父节点的值大于或等于子节点的值（即堆顶值是最大的）；
小根堆指父节点的值小于或等于子节点的值（即堆顶值是最小的）；

2.堆的存储：
既然Complete Binary Tree能够存储在数组之中，那么Heap也可以。
在数组中存储：第I个元素的父节点位置（下标）为 floor(i/2) ,其左子节点的位置（下标）
为 2I ,右子节点（如果有的话）的位置（下标）为 2I+1；（这个要牢牢地记住）（如图B
也可以推导出）（如图"B"）
注意：1.存储在数组中时，树根存在下标为1出上述规律才可成立
2.数组长度必须大于等于Node数量（用vector是个不错的选择）
图片说明

3.堆中数据的插入（以大根堆为例）：
步骤：

  • 1.在堆的末尾处（即数组末尾）加入元素*
  • 2.比较当前节点与其父节点的大小*
  • 3.若大于父节点则交换两节点的值，不大于则不动并结束*
  • 4.重复（2）步骤，直到结束*
    说明：
    为了不打断堆中数据的原有顺序（即完全二叉树）且降低时间复杂度，所以采用在堆
    末插入后交换元素，如果直接在堆中强行插入某一元素，不仅二叉树的条件不会满足，而且
    将元素后移的时间也会非常巨大。 
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
vector <int> a(1);
vector <int> b(1);//有效避免初始插入在a[0]or b[0]处（从a[1]or b[1]开始规律才成立）
int lenth;//堆元素数量(用STL则不必)
void get(int p) { //大根堆
    a.push_back(p);
    while(p>1) { //当前节点不是根节点
        if(p/2>=p)
            break;// 不要忘记循环出口条件
        else {
            swap(a[p/2],p);//不符合时进行交换
            p=p/2;//交换元素后，当前值的下标变成其父节点的下标
        }

    }
}
void getSTL(int p) {
    b.push_back(p);
    push_heap(b.begin()+1,b.end());//大根堆（1）
    push_heap(b.begin()+1,b.end(),less<int>());//大根堆（2）
    push_heap(b.begin()+1,b.end(),greater<int>());//小根堆

}
void dele(int p) { //大根堆
    a[1]=a[a.size()-1];//不要忘记最前端有一个a[0]
    a.pop_back();
    int now=1;
    int next;//子节点
    while(now*2>=a.size()) { //未到最底层或是最低层
        next=now*2;
        if(a[now]>=a[next]&&a[now]>=a[next++])
            break;
        if(next<=a.size()&&a[next+1]>a[next])next++;//当有右子节点且比当前元素大则转向右子节点
           swap(a[now],a[next]);//保证next是子节点中最大的
           now=next;//交换之后，在向前寻找是否有需要交换的元素 
    }
}
void deleSTL(int q)
{
    pop_heap(b.begin()+1,b.end());//大根堆
    pop_heap(b.begin()+1,b.end(),less<int>());//大根堆
    pop_heap(b.begin()+1,b.end(),greater<int>());//小根堆 
 } 
int main() {
    int a;
    cin>>a;
    get(a);
    getSTL(a);
    dele(a);
    deleSTL(a);

    return 0;
}

4.堆中数据的删除（以大根堆为例）：
说明:
1.每个元素（除底层）都可以视作是该元素与其子元素形成的小堆（如图B中框出的一小块）
故 我们不如已删除堆顶元素为例进行。
2.为满足完全二叉树的最左集中的特点，于是我们选取最底层最左侧的元素放到Root
步骤：

  • 1.将堆的最后一个元素覆盖到堆顶元素（达到删除目的） *
  • 2.查看此元素是否有子节点 *
  • 3.如果没有则结束，如果有则进行判断。*
  • 4.若当前元素比其子节点小，则将选择较大的元素进行两元素交换。若当前元素比其子节*
  • 点大，则结束。*
  • 5.若没有结束，则重复（2）步骤。*

图片说明