请你设计一个堆，使它具有如下功能：
1.查询( query ) 查询当前堆内最小的数字,并且输出该数字，如果堆为空，则输出"EMPTY"；
2.填加( add x ) 表示填加数字x到堆内
3.删除( del )   表示删除当前最小的数字,如果堆为空，则输出"EMPTY"

输入
首先输入一个数字N（1〈=N〈=50000）
然后输入N个指令
query
add x
del

输出
对应每条指令做相应操作


Smaple Input
9
add 2
add 1
query
del
query
del
del
del
query

Sample Output

1
2
EMPTY
EMPTY
EMPTY

就用小顶堆的标准算法会超时吗？
如果会的话，那这题感觉就不能用堆算了呀。（而且用其它结构感觉也没什么太多速度优势）

写出来看看。。

是说你连本讲数据结构或者算法的书都没有吗……

#include <stdio.h>

#define N 1000
int heap[N];
int top = 0;

void add(int x)
{
    int prt, cld;
    heap[top++] = x;

    for (cld = top-1; (cld-1)/2 >= 0; cld = prt)
    {
        prt = (cld-1)/2;
        if (heap[prt] <= heap[cld]) break;
        heap[top] = heap[cld];
        heap[cld] = heap[prt];
        heap[prt] = heap[top];
    }
}

void del()
{
    int prt, cld;
    if (top == 0)
    {
        printf ("EMPTY\n");
        return;
    }

    heap[top--] = heap[0];

    for (prt = 0; 2*prt+1 <= top; prt = cld)
    {
        cld = 2 * prt + 1;
        if (cld+1 <= top && heap[cld+1] < heap[cld]) ++cld;
        if (heap[top] < heap[cld]) break;
        heap[prt] = heap[cld];
    }
    heap[prt] = heap[top];
}

void query()
{
    if (top == 0)
        printf ("EMPTY\n");
    else
        printf ("%d\n", heap[0]);
}


int main (int argc, const char *argv[])
{  


    return 0;
}

得空给你写了一个，main 函数你自己加上唄。
没怎么调试，不敢保证是对的。不过思路你可以借鉴一下。

另外，你可以把你那个 tle 的代码发上来。大家看看是不是有改进的余地，没准改改就能用了呢～

我好像是直接数组模拟的==，一开始还以为数据宽点会AC==，这个最小堆没怎么写过。。

#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

int a[50005];

int main()
{
    int n;
    int x;
    scanf("%d",&n);
    string str;
    int num = 0;
    memset(a,0,sizeof(a));
    while(n--){
        cin >> str;
        if(str == "add"){
            scanf("%d",&x);
            a[num++] = x;
            sort(a, a + num);
        }else if(str == "query"){
            if(num == 0)    printf("EMPTY\n");
            else printf("%d\n",a[0]);
        }else if(str == "del"){
            if(num == 0)    printf("EMPTY\n");
            else{
                for(int i = 1,j=0; i < num; i++)
                    a[j++] = a[i];
                num--;
            }
        }

    }
    return 0;
} 

你写的这个timeout是必须的，大量的sort，内存copy、、最小堆得操作add,del为O(log(n)),query为O(1)。

哦。有的 OJ 不能 c++ 的。如果可以的话，就能直接用 STL 的 push_heap 和 pop_heap 应该就行了。对应 add 和 del。

en...主要是最小堆从来没写过。。。没办法，只能硬来试试看呃

没用过这个STL里面的make_heap()之类的，请以这题写一下，学习了。。