Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?

share|improve this question
    
What have you tried? –  Juho Nov 14 '12 at 5:14
    
So if I provide 2\$ for each node that I build. So if we have n nodes , we have to make sure our bank doesn't run out of 2n\$. DOn't know how to proof it using induction. –  user1675999 Nov 14 '12 at 5:27
    
Give a little more information how the build operation works. –  A.Schulz Nov 14 '12 at 7:01
1  
Note that the $O(n)$ cost to build a heap is in the worst-case, it is not amortized. –  Massimo Cafaro Nov 16 '12 at 9:30

2 Answers 2

up vote 7 down vote accepted

I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).

It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair. We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum_{h=1}^k O(h) 2^{k-h} = 2^k \sum_{h=1}^k O(h)/2^{h}. $$

Since $\sum_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for built is less than $C\cdot 2^k\le C \cdot n = O(n)$.

share|improve this answer
    
Hey guys, thanks for the reply. I actually came up with this, but I was struggling to prove the ammortised cost analysis, that at any node x of a tree, whose height is h, such that i put 2$ on each node. Then when i run max_heapify from that node, i will have h+1$ left in my credit. –  user1675999 Nov 21 '12 at 6:14
    
Are you asking why heapify takes $O(h)$? There a definitely different ways how to do the analysis. You should notice that we are not talking about amortized costs, since we only consider one single build operation. Of course you can amortize the costs of the heapify operations, but you can also just sum them up, that is what I did. –  A.Schulz Nov 21 '12 at 7:23

Note that here we don't have an arbitrary list of operations, we are talking about a single operation. So referring to it as amortized analysis can be confusing. Amortized analysis is usually used for an arbitrary list of operations, not a particular list of operations. We can use the methods for amortized analysis but AFAIK it is not common to call the result an amortized analysis.

Schulz answer is correct and uses the aggregate method. It is the usual proof of the fact and you can find it in textbooks like CLRS, chapter 6.

If you want to use the potential method for proving the bound, then remember that we want to get $O(1)$ for each heapify operation (to get $O(n)$ for the build heap operation). The real cost for each heapify is $O(h)$. We have to pay for the rest from the potential function. If we charge $c$ units for amortized cost then we can see that the analysis will work (we will determine $c$ later).

For the nodes in the bottom level (1) we will have to pay $n/2$. So we save potential $$cn/2-n/2$$

For the next level (2) we will pay $2n/4$ so we have potential $$c(n/2 + n/4) - (n/2 + 2n/4)$$

For the next level (3) we will pay $3n/8$ so we have potential $$c(n/2 + n/4 + n/8) - (n/2 + 2n/4 + 3n/8)$$

For the $k$th level we will pay $kn/2^i$ so we have potential $$cn\Sigma_{i=1}^k \frac{1}{2^i} - n\Sigma_{i=1}^k \frac{i}{2^i}$$

Note that $\Sigma_{i=1}^k \frac{i}{2^i} \leq d$ for some constant $d$ independent of $n$ and $k$ and $\Sigma_{i=1}^k \frac{1}{2^i} \geq \frac{1}{2}$. If we put these in the formula we get that the potential will always be at least $\frac{c}{2}n - dn$. So if we choose $c$ to be any constant larger than $2d$ it will always be positive.

The exact value of $c$ is not really important.

To cast this as an accounting method we need to specify which part of the data structure the potential is being assigned. In this case the potential needs to be assigned to the levels of the heap (if we want to assign the potential to nodes then it will be more complicated since it is difficult to tell which nodes will be use later when heapify is applied to nodes on higher levels).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.