Bumped by Community user
    Bumped by Community user
    Bumped by Community user
4 added 1719 characters in body
source | link

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Update:

Trying to explain in more detail what I don't understand. As far as I know/remember for given $n$ that somehow measures how large is the input of an algorithm the worst case analysis is "choose among all the possible instances of size $n$ the one that would give you the worst case execution cost"

Following this direction, to me is not particular clear how for given $n$ we can be sure that the left subtree has $\frac{2n}{3}$ nodes, it is ok when the value $n$ is such that the distribution of nodes is such that half of the last level is full, while the other one is empty. In the proof for cost bounding I would differently.

I would distinguish two cases :

  1. The tree has height $h$ and is complete, i.e. the total number of nodes is $2^{h+1} - 1$, I would also explain that it is possible to build in such case an heap such that starting from the root key it is possible to push down such key until it reach a leaf, how much is the cost in such case? it is exactly $h = ln_2(n+1) - 1 = O(ln \;n)$.

  2. The tree has height $h$ but it is not complete, given the heap structure the left-most leaf is at height $h$. As done in point 1 I would explain it is possible to build a tree such that the root would be pushed down always in the left branch. How much is the cost in this case? Given that $n > 2^{h} - 1$ we have that $h < ln_2(n+1) = O(ln(n))$.

I don't think is difficult to build a particular example for both 1. and 2. I also don't really see the point of "completing a tree" for computing the worst case cost, I can understand this operation can make the analysis easier, but for what I know about worst case analysis (assuming it is correct) it doesn't sounds correct to me.

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Update:

Trying to explain in more detail what I don't understand. As far as I know/remember for given $n$ that somehow measures how large is the input of an algorithm the worst case analysis is "choose among all the possible instances of size $n$ the one that would give you the worst case execution cost"

Following this direction, to me is not particular clear how for given $n$ we can be sure that the left subtree has $\frac{2n}{3}$ nodes, it is ok when the value $n$ is such that the distribution of nodes is such that half of the last level is full, while the other one is empty. In the proof for cost bounding I would differently.

I would distinguish two cases :

  1. The tree has height $h$ and is complete, i.e. the total number of nodes is $2^{h+1} - 1$, I would also explain that it is possible to build in such case an heap such that starting from the root key it is possible to push down such key until it reach a leaf, how much is the cost in such case? it is exactly $h = ln_2(n+1) - 1 = O(ln \;n)$.

  2. The tree has height $h$ but it is not complete, given the heap structure the left-most leaf is at height $h$. As done in point 1 I would explain it is possible to build a tree such that the root would be pushed down always in the left branch. How much is the cost in this case? Given that $n > 2^{h} - 1$ we have that $h < ln_2(n+1) = O(ln(n))$.

I don't think is difficult to build a particular example for both 1. and 2. I also don't really see the point of "completing a tree" for computing the worst case cost, I can understand this operation can make the analysis easier, but for what I know about worst case analysis (assuming it is correct) it doesn't sounds correct to me.

3 edited tags
source | link

Worst case heap sort, and number of nodes of height $h$ How to get this upper bound on worst-case heaps?

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most the ceil of $\frac{n}{2^{h+1}}$,$\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

Worst case heap sort, and number of nodes of height $h$

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most the ceil of $\frac{n}{2^{h+1}}$, There are proofs but I can't understand the motivation.

How to get this upper bound on worst-case heaps?

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most $\lceil \frac{n}{2^{h+1}} \rceil$. There are proofs but I can't understand the motivation.

2 deleted 11 characters in body
source | link

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call ishappens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I was thinking that I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most the ceil of $\frac{n}{2^{h+1}}$, There are proofs but I can't understand the motivation.

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call is when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I was thinking that I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most the ceil of $\frac{n}{2^{h+1}}$, There are proofs but I can't understand the motivation.

I've seen answers on the subjects, however I still don't get such answers. In the Cormen book (Introduction to algorithms) it is explained that the worst case for a $Max-Heapify$ call happens when the last level is "half full", in this case the worst case cost is modeled by the inequality:

$$ T\left(n\right) \leq T\left( \frac{2n}{3} \right) + \Theta(1) $$

I understand the equality (i.e. what it is modeling) but I don't understand how the worst case is built, I've tried to imagine an heap where the left subtree of the root is full up to level $h$ while the right one has (for example) just one node at level $h$, and with this example I can't see why the worst case modeling doesn't work, why such case would not represent an instance of the worst case?

The second question is that I don't understand why the number of nodes at height $h$ are at most the ceil of $\frac{n}{2^{h+1}}$, There are proofs but I can't understand the motivation.

1
source | link