堆结构

1.堆结构是用数组实现的完全二叉树结构
2.大根堆：每棵子树的最大值都在顶部（大根堆的根就是整棵树的最大值）
3.小根堆：每棵子树的最小值都在顶部（小根堆的根就是整棵树的最小值）
4.对任意i位置的节点，左孩子节点位置：2+i+1，右孩子节点位置：2i+2，父节点位置：(i-1)/2
================================================================================
C++(STL)中的堆结构是通过算法的形式提供的，包括以下几个函数(需要包含头文件algorithm)：
make_heap:根据指定的迭代器区间以及一个可选的比较函数，来创建一个heap.[O(N)]
push_heap:把指定区间的最后一个元素插入到heap中. [O(logN)]
pop_heap:弹出heap顶元素, 将其放置于区间末尾. [O(logN)]
sort_heap:堆排序算法，通常通过反复调用pop_heap来实现. [O(NlogN)]
C++11新加函数：
is_heap:判断给定区间是否是一个heap. [O(N)]
is_heap_until:找出区间中第一个不满足heap条件的位置. [O(N)]

具体操作：

创建堆make_heap

默认创建的是大根堆，在创建时指定比较函数为greater<int>()就可以创建小根堆</int>

vector<int> v;
    v.push_back(6);
    v.push_back(1);
    v.push_back(2);
    v.push_back(5);
    v.push_back(3);
    v.push_back(4);
    vector<int>v1 = v;                   //v1:6,1,2,5,3,4
    make_heap(v1.begin(), v1.end());    //默认是大根堆(默认比较函数是:less<int>()) v1: 6,5,4,1,3,2
    cout << endl;
    vector<int>v2 = v;
    make_heap(v2.begin(), v2.end(),greater<int>());   //v2: 1,3,2,5,6,4

插入push_heap

先在容器末尾追加元素后再用push_heap进行调整（和make_heap一样，默认是大根堆，加greater<int>()可以调整为小根堆）
[内部怎么调整：新加入的节点，往上看（看它的父节点），比父亲大就换，再继续往上看，直到不比父亲大了或者已经到了最上面就停止]
注意：在用push_heap的时候一定要保证前面的n-1个已经是一个堆结构了！！！</int>

    v1.push_back(20);       //v1: 6,5,4,1,3,2,20
    push_heap(v1.begin(), v1.end());   //v1:20,6,5,4,1,3,2
    vector<int>v2 = v;
    make_heap(v2.begin(), v2.end(),greater<int>());  
    v2.push_back(0);                                //v2: 1,3,2,5,6,4,0
    push_heap(v2.begin(), v2.end(), greater<int>());//v2: 0,1,3,2,5,6,4

删除pop_heap

pop_heap的操作：把堆中第一个元素和最后一个交换，然后把前面n-1个元素调整为新的堆（默认是大根堆）
[内部怎么调整：最后一个元素换上去后，依次往下进行pk，俩孩子先pk，大的再和父亲pk，直到父亲比俩孩子都大或者已经到底部了]
然后把容器的最后一个元素删除（如果需要记录这个数就要用v.back()保存一下）
注意：pop_heap使用的时候一定要保证原来已经是个堆结构了！！！

    make_heap(v1.begin(), v1.end());       
    pop_heap(v1.begin(), v1.end());         //v1: 5,3,4,1,2(,6)
    cout << v1.back()<<endl;     //6
    v1.pop_back();            //v1: 5,3,4,1,2
    vector<int>v2 = v;
    make_heap(v2.begin(), v2.end(),greater<int>());   
    pop_heap(v2.begin(), v2.end(), greater<int>());  //v2: 2,3,4,5,6(,1)
    cout << v2.back() << endl;    //1
    v2.pop_back();      //v2: 2,3,4,5,6

注意：heap里面的插入和删除都需要在之前或之后用容器进行插入和删除，并且需要保证在插入和删除之前的结构是堆结构！并且，push_heap和pop_heap后的比较函数需要与创建堆时即make_heap保持一致！

排序sort_heap

大根堆的排序是从小到大，小根堆的排序是从大到小
使用的时候也要确保原来的结构是个堆结构

    make_heap(v1.begin(), v1.end());        //v1:6,1,2,5,3,4
    sort_heap(v1.begin(), v1.end());    //v1:1,2,3,4,5,6
    vector<int>v2 = v;
    make_heap(v2.begin(), v2.end(),greater<int>());   //v2: 6,1,2,5,3,4
    sort_heap(v2.begin(), v2.end(), greater<int>());   //v2:6.5.4.3.2.1

堆排序的时间复杂度为O(N*logN)