提示：吃糖果吃多了会变胖的！

小Ho写了半天的Brute Force算法，却发现自己的电脑性能还是差了一点，不能满足其滔天食欲，于是乖乖的找上了小Hi，请教有没有更为高效的算法。

“正好，本来想要给你讲解的Prim算法的优化需要用到堆结构，既然你也遇到了这样一个非常适合使用堆来解决的问题，那就一并讲解给你听吧！”小Hi满意的点了点头。

“堆……那是什么东西啊？”小Ho问道。

“堆有两种，小根堆和大根堆，先说大根堆，如果对于一个节点上带有权值的完全二叉树，每个节点的权值都比它的左右子节点的权值大的话，这颗二叉树就被称为大根堆。”小Hi道。

“那么小根堆应该就是每个节点的权值都比它的左右子节点的权值小咯？”小Ho得出结论。

“是的！”小Hi说道：“那么如果我们把每个节点都看做一棵糖果，整棵树看成你的糖果盒子，那么想要找到最大的糖果其实非常简单——就是这棵树的根节点！”

“每个节点的权值都比它的左右子节点的权值大……那么根节点自然是权值最大的节点。”小Ho想了想道：“没有错，但是问题在于，我怎么样构造这样一棵树呢？”

“我们这样来考虑：如果现在所有的糖果已经被构造成为了这样一棵树，你往其中放入一棵新的糖果，该如何保持这棵树的性质？”小Hi问道。

小Ho边思考边道：“唔……首先我得把它当做一个节点加入到树中——为了保持仍然是完全二叉树，只能加到最后一排的第一个空余位置（如果最后一排满了则加到新的一排的第一个位置），然后我们考虑可能出现违反大根堆性质的地方：新加入节点P的权值可能比其父亲节点F的权值要大，但是解决方法很简单：直接将P和F的位置进行交换（在实际操作中直接将权值进行交换就可以了），但是这样可能会导致F的权值比其父亲节点F‘要大，所以这样的交换需要一直向上进行，直到某个节点的权值不再比其父亲节点要大，或者到达了根节点。总而言之，就是在加入一个新的节点之后，不断向上消除不符合大根堆性质的地方。”

“嗯~这样是正确的！”小Hi点了点头：“这样添加一颗新糖果的问题得到了解决，但是拿掉一棵糖果的问题你准备怎么解决呢？”

“拿掉的糖果是根节点……这样会很麻烦，不如先将根节点与最后一层最后一个节点进行对调，这样仍然保证了是一棵完全二叉树，所以问题还是如何保证‘每个节点的权值都比它的左右子节点的权值大’这个性质。现在可能产生问题的节点只有根节点，所以考察根节点T和其左右子结点L、R的权值大小关系，不妨设L的权值比R要大（反之会有相似的结论），如果L的权值比T小，那么不存在任何问题，否则将L和T的权值进行交换便可以解决根节点处不满足性质的问题——但是这样的交换又可能导致L（现在的权值是T的权值）不满足这样的情况，所以便要继续向下进行检查,知道某个节点的权值比其左右子节点都要大，或者到达了叶子节点。总而言之，就是将根节点同最后一个节点互换并删除之后，从根节点开始不断向下消除不符合大根堆性质的地方。”

小Hi点了点头道：“这样一来，对于两种操作，你都可以维护好大根堆的性质，而最开始的状态——一棵为空的树自然也是满足这个性质的，所以这个问题不就变得很简单了么！”

“是的！”小Ho高兴道：“我可以去吃糖了！”

 1 #include <iostream> 2 #include <queue> 3 using namespace std; 4 int main(){ 5     priority_queue<int> que; 6     int n, w; 7     char c; 8     cin >> n; 9     while(n--){10         cin >> c;11         if(c == ‘A‘){12             cin >> w;13             que.push(w);14         } else if (c == ‘T‘) {15             cout << que.top() << endl;16             que.pop();17         }18     }19     return 0;20 }

 1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4  5 int heap[100005], size = 0; 6 //第一个元素的下标为1. 7 void push(int x){ 8     int i = ++size; 9     while(i > 1){10         int p = i / 2;11         if(heap[p] >= x)12             break;13         heap[i] = heap[p];14         i = p;15     }16     heap[i] = x;17 }18 19 int pop(){20     //最大值21     int ret = heap[1];22     //要提到根的值23     int x = heap[size--];24     int i = 1;25     while(2 * i + 1 <= size){26         int a = 2 * i, b = 2 * i + 1;27         if(heap[b] > heap[a])28             a = b;29         if(x >= heap[a])30             break;31         heap[i] = heap[a];32         i = a;33     }34     heap[i] = x;35     36     return ret;37 }38 39 int main(){40     int n, w;41     char c;42     cin >> n;43     while(n--){44         cin >> c;45         if(c == ‘A‘){46             cin >> w;47             push(w);48         } else {49             cout << pop() << endl;50         }51     }52     return 0;53 }