Question

虽然方法改进一相比于常规方法是有了改善，但最多比较次数仍然需要 2n-3 次，未达到题目所要求。这次我们方找最小元素的过程入手。
上文已经说过，求最元素的过程到少要经过 n-1 次比较，这一点是难以改变的。但我们仍可以通过调整第一次遍历方式，使留给第二次遍历更多有用的信息。尽量让每个元素与其它元素的比较次数平均化，这样，当任意一个元素成为最小元素时，它的队列的元素个数都不会太多。仍然以上文的图为例：

方法改进一的第一次遍历可以画成这一样的图，数组中的每一元素是这个二叉树的叶子结点。假如某一个元素是最小元素，那么它的队列的元素即该叶子结点的高度。只要将树平均化，如下图所示，保证每一个叶子的高度都不会太高，那么每个元素对应的队列都就不会太大。