每日一题：堆排序中建堆过程的时间复杂度是

end

来源：https://www.nowcoder.com/questionTerminal/385157a6b64540c3b233bd12f8a83ee7

其实，建堆的整个过程中一个节点的比较次数是与它的高度k成正比的，比如，上图中的1这个元素，它也是从最后一层依次比较了3次（高度h=4），才到达了现在的位置。

所以，我们可以得出第h层的元素有1个，它最多需要比较(h-1)次；第(h-1)层有2个元素，它们最多比较(h-2)次；第(h-2)层有22个元素，它们最多比较(h-3)次；...；第1层有2(h-1)个元素，它们最多比较0次。

构造二叉堆的时间复杂度为线性

构造二叉堆的时间复杂度为线性

构造二叉堆的时间复杂度为线性

heap property

关系：元素之间的关系

What are the minimum and maximum numbers of elements in a heap of height h?

The BUILD-MAX-HEAP procedure, which runs in linear time, produces a max- heap from an unordered input array.

The BUILD-MAX-HEAP procedure, which runs in linear time, produces a max- heap from an unordered input array.

The procedure BUILD-MAX-HEAP goes through the remaining nodes of the tree and runs MAX-HEAPIFY on each one.

BUILD-MAX-HEAP.A/

2. 1 A:heap-size D A:length
4. 2 for i D bA:length=2c downto 1

3 MAX-HEAPIFY.A;i/

Exercises

6.2-1

Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY.A;3/ on the array A D h27;17;3;16;13;10;1;5;7;12;4;8;9;0i.

6.2-2

Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY.A;i/, which performs the corresponding manipulation on a min- heap. How does the running time of MIN-HEAPIFY compare to that of MAX- HEAPIFY?