题目内容：

 

實作Max heap的三種操作：push, pop, top。

 

指令0 x：代表push，將x push進max heap。

指令1 : 代表pop，將最大的數字pop出來，若heap為空則忽略這道指令。

指令2 : 代表top，將最大的數字印出來，若heap為空則忽略這道指令。

 

输入格式:

 

本題只有一道測資。

測資第一行為一個數字N，代表接下來有N行指令。每行指令個格式如題目敘述。

 

所有push的數字皆不相同。

 

0 < N < 20000

0 < x < 10000000

 

输出格式：

 

將所有top指令輸出的數字作加總，最後輸出這個和。

Hint : 注意overflow!

 

 

输入样例：

 

15

1

0 9550684

0 8533293

1

2

2

1

0 505825

0 9809892

0 1484329

0 4958409

0 3788064

0 28006

2

0 2979864

 

 

输出样例：

 

26876478

 

时间限制：100ms内存限制：128000kb

 

实现方式一：（堆排序，时间复杂度：O(lgn)）

1 #include 
      
        2 int cmd1,cmd2; 3 int count = 0; 4 long long sum = 0; 5 long long a[20000]; 6  7 void push(long long a[]){ 8     a[++count] = cmd2; 9     int index = count;10     while(index!=1) {11         int parent = index/2;12         if(a[parent]
       
         a[rchd]) 34             chd = lchd;35         else36             chd =rchd;37         if(a[index]
       
      

实现方式二：（时间复杂度：O(nlgn)）

1 #include 
      
        2 int cmd1,cmd2; 3 int count = 0; 4 long long sum = 0; 5 long long a[20002]; 6 void HeapAdJust(long long a[],int i,int size){ 7     int l_child = 2*i; 8     int r_child = 2*i+1; 9     int max =i ;10     int temp;11     12     if(l_child<=size&&a[l_child]>a[i]){13         max = l_child;14     }15     if(r_child<=size&&a[r_child]>a[max]){16         max = r_child;17     }    18     if(max != i){19         temp = a[i];20         a[i] = a[max];21         a[max] = temp;22         HeapAdJust(a,max,size);23     }24 }25 26 void BuildHeap(long long a[],int size){27     int i;28     for(i=size/2;i>=1;i--){29         HeapAdJust(a,i,size);30     }31 }32 33 void push(long long a[]){34     a[++count] = cmd2;35     BuildHeap(a,count);36 }37 38 void pop(long long a[]){39     if(count==0){40         return;41     }42     a[1] = a[count];43     count--;44     BuildHeap(a,count);45     return;46 }47 48 void top(long long a[]){49     sum +=a[1]; 50 }51 52 int main(void){53     int n,i;54     scanf("%d",&n);55     for(i=0;i