堆

一、定义

堆一般用于优先队列的实现（默认情况使用大顶堆）
大顶堆：父亲结点的值大于等于孩子结点的值，每个结点的值都是以它为根结点的子树的最大值。
小顶堆：父亲结点的值小于等于孩子结点的值，每个结点的值都是以它为根结点的子树的最小值。

const int maxn=100;
int heap[maxn],n=10;

二、建堆过程--向下调整

思路：总是将当前结点V与它的左右孩子比较（如果存在），加入孩子中存在权值比结点V的权值大的，就将其中权值最大的那个孩子结点与结点V交换；
交换完毕后继续让结点V和孩子比较，直到结点V的孩子的权值都比结点V的权值小或是结点V不存在孩子结点；

时间复杂度为O(logn)

//向下调整的代码
//对heap数组在[low,high]范围进行向下调整
//其中low为欲调整结点的数组下标,high一般为堆的最后一个元素的数组下标
void downAdjust(int low,int high)
{
    int i=low,j=i*2;  //i为欲调整结点,j为其左孩子
    while(j<=high){   //存在孩子结点
        //如果右孩子存在，且右孩子结点值大于左孩子
        if(j+1<=high&&heap[j+1]>heap[j])
        {
            j=j+1;     //让j存储右孩子下标
        }
        //如果孩子中最大的权值比欲调整结点i大
        if(heap[j]>heap[i])
        {
            swap(heap[j],heap[i]);   //交换最大权值的孩子与欲调整结点i
            i=j;
            j=i*2;
        }else{
            break;    //孩子的权值均比欲调整结点i小，调整结束
        }
    }
}

建堆，假设序列中元素个数为n,由于完全二叉树的叶子结点个数为n/2向上取整，因此数组下标在[1,n/2向下取整]范围内结点都是非叶子结点，
因此可以从n/2向下取整号位置开始倒着枚举结点，对每个遍历到的结点i进行[i,n]范围的调整。
倒着枚举可以保证每个结点都是以其为根结点的子树中的权值最大的结点。
时间复杂度O(n)

void createHeap()
{
    for(int i=n/2;i>=1;i--){
        downAdjust(i,n);
    }
}

三、删除堆顶元素

思路：将最后一个元素覆盖堆顶元素，然后对根结点进行调整即可
时间复杂度：O(logn)

void deleteTop()
{
    heap[1]=heap[n--];  //用最后一个元素覆盖堆顶元素，并让元素个数减1
    downAdjust(1,n);   //向下调整堆顶元素
}

四、插入元素--向上调整

思路：将想要添加的元素放在数组最后（即完全二叉树的最后一个结点后面），然后进行向上调整操作。
向上调整总是把欲调整结点与父亲结点比较，如果权值比父亲结点大，就交换其与父亲结点，反复比较，直到到达堆顶或是父亲结点的权值较大为止。
时间复杂度为O(logn)

//对heap数组在[low,high]范围进行向上调整
//其中low一般设置为1，high表示欲调整结点的数组下标
void upAdjust(int low,int high)
{
    int i=high,j=i/2;   //i为欲调整结点,j为其父亲
    while(j>=low)       //父亲在[low,high]范围内
    {
        //父亲权值小于欲调整结点i的权值
        if(heap[j]<heap[i]){
            swap(heap[j],heap[i]);  //交换父亲结点和欲调整结点
            i=j;                    //保持i为欲调整结点，j为i的父亲
            j=i/2;
        }else{
            break;                  //父亲权值比欲调整结点i的权值大，调整结束
        }
    }
}

插入元素x

void insert(int x){
    heap[++n]=x;  //让元素个数加1，然后将数组末位赋值为x
    upAdjust(1,n);   //向上调整加入的结点n
}

五、堆排序

使用堆结构对一个序列进行排序，此处讨论递增排序。

堆排序的直观思路：取出堆顶元素，然后将堆的最后一个元素替换至堆顶，再进行一次针对堆顶元素的向下调整--如此反复直到堆中只有一个元素为止
具体实现时为了节省空间，可以倒着遍历数组，假设当前访问到i号位，那么将堆顶元素与i号位的元素交换，接着在[1,i-1]范围内对堆顶元素进行一次向下调整即可。

void heapSort()
{
    createHeap();   //建堆
    for(int i=n;i>1;i--){   //倒着枚举，直到堆中只有一个元素
        swap(heap[i],heap[1]);   //交换heap[i]与堆顶
        downAdjust(1,i-1);       //调整堆顶
    }
}

 六、练习题

问题B: 序列合并

题目描述

有两个长度都为N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。

输入

第一行一个正整数N（1 <= N <= 100000）。

第二行N个整数Ai，满足Ai <= Ai+1且Ai <= 10^9

第三行N个整数Bi，满足Bi <= Bi+1且Bi <= 10^9

输出

输出仅有一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。

样例输入 http://codeup.cn/problem.php?cid=100000616&pid=0

#include 
#include 
using namespace std;
const int maxn=100005;
int heap[maxn],n;
//建堆过程，向下调整
void downAdjust(int low,int high)
{
    int i=low,j=i*2;
    while(j<=high){
        if(j+1<=high&&heap[j+1]>heap[j])
        {
            j=j+1;
        }
        if(heap[j]>heap[i])
        {
            swap(heap[j],heap[i]);
            i=j;
            j=i*2;
        }
        else{
            break;
        }
    }
}
//建堆
void createHeap()
{
    for(int i=n/2;i>=1;i--){
        downAdjust(i,n);
    }
}
void heapSort()
{
    createHeap();
    for(int i=n;i>1;i--){
        swap(heap[i],heap[1]);
        downAdjust(1,i-1);   //调整堆顶
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>heap[i];
    heapSort();
    for(int i=1;i<=n;i++)
    {
        if(i!=n) cout<" ";
        else cout<endl;
    }
    return 0;
}

问题C：合并果子（堆）

http://codeup.cn/problem.php?cid=100000616&pid=2

思路：优先队列，小顶堆。

#include 
#include 
#include 
#include 
using namespace std;
//小顶堆
priority_queue<int,vector<int>,greater<int> > que;
int n;
int main()
{
    int value,sum=0,temp=0;
    cin>>n;
    for(int i=0;i)
    {
        cin>>value;
        que.push(value);
    }
    if(que.size()==1){
        cout<endl;
        return 0;
    }
    while(que.size()>1)
    {
        temp+=que.top();
        que.pop();
        if(!que.empty()){
            temp+=que.top();
            que.pop();
        }
        que.push(temp);
        sum+=temp;
        temp=0;
    }
    cout<endl;
    return 0;
}