是否有O(n)算法来构建min-heap？

Question

如果输入数组按升序排序，例如从1到n的数字，那么从这样的数组构建最小堆需要O(n)吗？

编辑1:我知道如果我们从n个元素构建一个最小堆，那么在最坏的情况下，它的运行时间将是Ω(n*log )，但是这n个元素的升序排序是否可以在O(n)最坏情况下运行时间构建最小堆？

编辑2:有没有可能我们可以从一个n大小的数组中以O(n)的降序构建一个最小的堆？如果是这样，那为什么呢？

Answer 1

如果数组已排序-它已经是最小堆，因为主堆属性A[i]<= A[2*i]和A[i]<= A[2*i+1] (用于从1开始的计算)为真。

请注意，对于任何源数组，堆构建过程都需要O(n)时间。Arbitrary found source

Answer 2

来自Wikipedia on Binary Heap

堆通常是使用数组实现的。任何二叉树都可以存储在数组中，但是因为二进制堆总是一个完整的二叉树，所以它可以被紧凑地存储。

所有细节都在页面上给出。