建堆：O(n)
询问：O(logn)
建堆复杂度的证明：
首先这个循环是从i = headsize/2 -> 1，也就是说这是一个bottom-up的建堆。于是，有1/2的元素向下比较了一次，有1/4的向下比较了两次，1/8的，向下比较了3次，......，1/2^k的向下比较了k次，其中1/2^k <= 1, k 约等于lg(n)。于是就有总的比较量：首先
阅读背景：
O(n)求数组中第k大的元素——堆排序
来源：互联网
分享到：
