构建大根堆

对于一个没有重复元素的整数数组，请用其中元素构造一棵MaxTree，MaxTree定义为一棵二叉树，其中的节点与数组元素一一对应，同时对于MaxTree的每棵子树，它的根的元素值为子树的最大值。现有一建树方法，对于数组中的每个元素，其在树中的父亲为数组中它左边比它大的第一个数和右边比它大的第一个数中更小的一个。若两边都不存在比它大的数，那么它就是树根。请设计O(n)的算法实现这个方法。
方法不容易想到，直接说结论：

1. 对于每个元素，找到其左边第一个大于它的数，和右边第一个大于它的数：

   
   

2. 对于某个元素来说，如果左右数存在，则较小者即为它的父节点；若左右其一不存在，存在者即为父节点；否则没有父节点。

   
   

验证正确性：

1. 除了最大数以外，每个数都可找到一个父亲。所以一定会构成树。

2. 任何数在单独一侧的孩子至多有一个。假设K1K2都是A的孩子，则A>K1且A>K2.假设K1<K2则K1必以K2做父节点，而非A。同理可证。

   
   

关键步骤在于：
求序列中某个元素左边和右边第一个大于它的数。
类似于之前的算法，需要借助栈：
遍历到元素x时，
情况1：s为空或x<s.top() :记录x的左端第一个比它大的值是空或s.top();压入x;
情况2：弹出s的顶部元素直至满足情况1为止。
从左向右遍历和再从右向左遍历，分别算出某元素左边和右边第一个大于它的数。
然后综合这两张表，得到每个元素的父节点编号。
如果需要组建二叉树，建议生成一个哈希表，表的内容为数组中某个元素，对应二叉树结点的地址。数组每个元素先new产生结点，结点地址装入哈希表。然后遍历父节点编号列表，在父与子之间做指针域的链接。
这样的话，在生成父节点编号表的时候，就可以留意看看哪个元素是根节点，预先保存下来。当然这里就不做实现了。

CODE

void firstBigL(const vector<int>&A,vector<int>& firstBiger){
    int n=A.size();
    firstBiger.resize(n);
    stack<int>s;//注意里面存的是下标
    for(int i=0;i<n;++i){
        while(!s.empty()&& A[s.top()]<A[i]){
            s.pop();
        }
        if(s.empty())
            firstBiger[i]=-1;
        else
            firstBiger[i]=s.top();
        s.push(i);
    }
}
void firstBigR(const vector<int>&A,vector<int>& firstBiger){
    int n=A.size();
    firstBiger.resize(n);
    stack<int>s;//注意里面存的是下标
    for(int i=n-1;i>=0;--i){
        while(!s.empty()&& A[s.top()]<A[i]){
            s.pop();
        }
        if(s.empty())
            firstBiger[i]=-1;
        else
            firstBiger[i]=s.top();
        s.push(i);
    }
}
vector<int> buildMaxTree(vector<int> A, int n) {
        // write code here
    vector<int> bigL,bigR;
    firstBigL(A,bigL);
    firstBigR(A,bigR);
    for(int i=0;i<n;++i){
        if(bigL[i]==-1)
            bigL[i]=bigR[i];
        else{
            if(bigR[i]>-1 && A[bigR[i]]<A[bigL[i]])
                bigL[i]=bigR[i];
        }
    }
    return bigL;
}

如果元素有相等的情况

因为函数中，栈顶比x小就会弹出，如果相等就压入x进去，所以最后的结果，是数组左边（右边）第一个大于等于x的数。这样的话，照理也可以构建大根堆，但是：
2 5 5 2
两个5分别以对方作为父节点，建立失败。