关于堆的两个小疑点

关于堆的两个小问题
1、写一个有效算法来测试一个给定的数组A[1...n]是否是一个堆，该算法的时间复杂度是什么？
2、从n个元素的最大堆中找到最小键值可能有多快？



[解决办法]
判断一个数组是否是一个堆，要看是否满足堆的性质，那大顶堆举例，大致的代码如下(手工敲打，不保证编译通过)：

C/C++ code

#define TRUE (1)#define FALSE (0)int isHeap(int k[], int size){    int i = 0;    int mid = size/2;        for(i=0; i<mid; ++i){        if(k[i] < k[2*i+1])   return FALSE;        if(2*i+2<size && k[i]<k[2*i+2])   return FALSE;    }    return TRUE;}
[解决办法]
探讨


第一问的代码ls已经给出了，至于第二问的从n个元素的最大堆中找到最小键值时间复杂度为O(lgn)