Skip to main content
added 19 characters in body
Source Link
Russel
  • 2.8k
  • 1
  • 9
  • 16

If anyone will still come across this problem and interested in a potential analysis way of obtaining the accepted answer. I have a preprintpreprint in arxiv discussing this: https://arxiv.org/abs/2010.04752. We got a simpler sum and a tighter constant, but you need to have some idea about potentials.

Essentially we treat the array as a forest of heaps and define the potential to be the sum of the levels of all the heaps in the forest. Each time the build heap repairs a subtree, we treat it as merging of at most 3 heaps. So each repair decreases the number of heaps in the forest, and therefore reduces the levels in the forest. We then show that the amortized cost of a repair is 1. Since there are n level 1 heaps at the start and there are n/2 repairs, which then leads to the O(n) total cost of build heapis 1.5n.

If anyone will still come across this problem and interested in a potential analysis way of obtaining the accepted answer. I have a preprint in arxiv discussing this: https://arxiv.org/abs/2010.04752. We got a simpler sum but you need to have some idea about potentials.

Essentially we treat the array as forest of heaps and define the potential to be the sum of the levels of all the heaps in the forest. Each time the build heap repairs a subtree, we treat it as merging of at most 3 heaps. So each repair decreases the number of heaps in the forest, and therefore reduces the levels in the forest. We then show that the amortized cost of a repair is 1, which then leads to the O(n) total cost of build heap.

If anyone will still come across this problem and interested in a potential analysis way of obtaining the accepted answer. I have a preprint in arxiv discussing this. We got a simpler sum and a tighter constant, but you need to have some idea about potentials.

Essentially we treat the array as a forest of heaps and define the potential to be the sum of the levels of all the heaps in the forest. Each time the build heap repairs a subtree, we treat it as merging of at most 3 heaps. So each repair decreases the number of heaps in the forest. We then show that the amortized cost of a repair is 1. Since there are n level 1 heaps at the start and there are n/2 repairs, the total cost is 1.5n.

Source Link
Russel
  • 2.8k
  • 1
  • 9
  • 16

If anyone will still come across this problem and interested in a potential analysis way of obtaining the accepted answer. I have a preprint in arxiv discussing this: https://arxiv.org/abs/2010.04752. We got a simpler sum but you need to have some idea about potentials.

Essentially we treat the array as forest of heaps and define the potential to be the sum of the levels of all the heaps in the forest. Each time the build heap repairs a subtree, we treat it as merging of at most 3 heaps. So each repair decreases the number of heaps in the forest, and therefore reduces the levels in the forest. We then show that the amortized cost of a repair is 1, which then leads to the O(n) total cost of build heap.