Skip to main content
Computer Science

Return to Answer

added 4 characters in body
Source Link
Nathaniel
Nathaniel
  • 17k
  • 2
  • 30
  • 55

Edit: This proof is insufficient as pointed out in comment.

I am assuming that when the author says "covers the full height of the tree", (it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree). This claimit means that the node that is not true as pointed out in commentput at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

I am assuming that when the author says "covers the full height of the tree", (it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree). This claim is not true as pointed out in comment.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

Edit: This proof is insufficient as pointed out in comment.

I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

added 58 characters in body
Source Link
Nathaniel
Nathaniel
  • 17k
  • 2
  • 30
  • 55

I am assuming that when the author says "covers the full height of the tree", it means that the node that(it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree). This claim is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the treenot true as pointed out in comment.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

I am assuming that when the author says "covers the full height of the tree", (it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree). This claim is not true as pointed out in comment.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

Source Link
Nathaniel
Nathaniel
  • 17k
  • 2
  • 30
  • 55

I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.