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/
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?