Max-Heapify 中的最坏情况 - 如何获得 2n/3? [英] Worst case in Max-Heapify - How do you get 2n/3?

问题描述

在 CLRS，第三版，第 155 页，在 MAX-HEAPIFY 中给出，

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,

子树的每个子树的大小至多 2n/3——最坏的情况当树的底层正好是半满时发生.

The children’s subtrees each have size at most 2n/3—the worst case occurs when the bottom level of the tree is exactly half full.

我明白为什么当树的底部正好是半满时最糟糕.并且在这个问题中也得到了回答 MAX-HEAPIFY 中的最坏情况:最坏的情况发生在树的最底层正好是半满"

I understand why it is worst when the bottom level of the tree is exactly half full. And it is also answered in this question worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"

我的问题是如何获得 2n/3?

My question is how to get 2n/3?

为什么如果底层是半满，那么子树的大小就达到了2n/3?

Why if the bottom level is half full, then the size of the child tree is up to 2n/3?

如何计算?

谢谢

推荐答案

在每个节点恰好有 0 个或 2 个子节点的树中，具有 0 个子节点的节点数比具有 2 个子节点的节点数多 1.{说明:高度h处的节点数为2^h，由几何级数的求和公式等于(高度0到h-1的节点之和)+1；并且所有从高度 0 到 h-1 的节点都是刚好有 2 个孩子的节点}

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

    ROOT
  L      R
 /     / 
/     /   
-----  -----
*****

设k为R中的节点数.L中的节点数为k + (k + 1) = 2k + 1.节点总数为n = 1 + (2k + 1) + k =3k + 2(根加 L 加 R).比率为 (2k + 1)/(3k + 2)，其上限为 2/3.没有小于 2/3 的常数有效，因为当 k 趋于无穷大时，极限是 2/3.

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.

这篇关于Max-Heapify 中的最坏情况 - 如何获得 2n/3?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！