堆的数据结构能够使得堆顶总是维持最大（对于大根堆）或最小（对于小

堆的数据结构能够使得堆顶总是维持最大（对于大根堆）或最小（对于小根堆），给定一个数组，对这个数组进行建堆，则平均复杂度是多少？如果只是用堆的 push 操作，则一个大根堆依次输入 3,7,2,4,1,5,8 后，得到的堆的结构示意图是下述图表中的哪个？（）

A.O(n)
B.O(n) ,
C.O(logn)
D.O(n),

[解析]

堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在O(1)~O(logn)之间。采用push的操作实现大根堆，每次输入后，为了保证是大根堆，每插入一个元素，调整一次。具体过程如下：

所以正确答案为D。