算法原题来自：hihocoder
你可以在我的github获取源码:https://github.com/Wtango/hihocoder
大根堆属于完全二叉树，并且根所有节点的权重都比这个节点的左右孩子的权重大。
题目中堆的建立如维护主要有两个操作：1.添加节点 2.删除根
添加节点即建堆的过程，建堆的时间复杂度O(N) ,删除根节点的时间复杂度为O(log N),使用数组表示堆的时候需要注意边界处理。
#include <stdio.h>
#include <string.h>
#define MAXNODE 100010
int tree[MAXNODE] = {0};
int size = 0;
void swap(int n1,int n2)
{
int tmp = tree[n1];
tree[n1] = tree[n2];
tree[n2] = tmp;
}
void add_node(int weight)
{
tree[++size] = weight;
int loc = size;
while((loc > 1) && tree[loc] > tree[loc/2]) {
swap(loc,loc/2);
loc /= 2;
}
}
int big_son(int node)
{
int lnode = 2 * node;
if(lnode + 1 > size)
return lnode;
return tree[lnode] > tree[lnode + 1]?lnode :lnode + 1;
}
int del_root()
{
int root_weight = tree[1];
tree[1] = tree[size--];
int loc = 1;
while((2 * loc <= size)) {
int bs = big_son(loc);
if(tree[loc] < tree[bs]) {
swap(loc,bs);
loc = bs;
continue;
}
break;
}
return root_weight;
}
int main()
{
char c;
int N,weight;
scanf("%d",&N);
while(N--) {
getchar();
scanf("%c",&c);
if(c == 'A') {
scanf("%d",&weight);
add_node(weight);
}
else
printf("%d\n",del_root());
}
}
因为使用了scanf(“%c”) 操作，需要使用getchar()来吸收掉的’\n’字符。
