How can building a heap be O(n) time complexity?

Question

Can someone help explain how can building a heap be O(n) complexity?

Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the heap property). So, this means the complexity should be O(n log n), I would think.

In other words, for each item we "heapify", it has the potential to have to filter down (i.e., sift down) once for each level for the heap so far (which is log n levels).

What am I missing?

Etty

what precisely do you mean by "building" a heap? – Ocotillo

As you would in a heapsort, take an unsorted array and filterdown each of the top half elements until it conforms to the rules of a heap – Etty

Only thing i could find was this link: The complexity of Buildheap appears to be Θ(n lg n) – n calls to Heapify at a cost of Θ(lg n) per call, but this result can be improved to Θ(n) cs.txstate.edu/~ch04/webtest/teaching/courses/5329/lectures/… – Etty

@Gba watch this video from MIT: He explains well on how we get O(n), with a lil bit of math youtube.com/watch?v=B7hVxCmfPtM – Callista

Direct link to the explanation @Callista mentioned: youtu.be/B7hVxCmfPtM?t=41m21s – Blackmon

heap contain binary tree and inserting in binary take logn time with n element simply total time is n*logn simple . – Indeed

Answer 1

I think there are several questions buried in this topic:

• How do you implement buildHeap so it runs in O(n) time?
• How do you show that buildHeap runs in O(n) time when implemented correctly?
• Why doesn't that same logic work to make heap sort run in O(n) time rather than O(n log n)?

How do you implement buildHeap so it runs in O(n) time?

Often, answers to these questions focus on the difference between siftUp and siftDown. Making the correct choice between siftUp and siftDown is critical to get O(n) performance for buildHeap, but does nothing to help one understand the difference between buildHeap and heapSort in general. Indeed, proper implementations of both buildHeap and heapSort will only use siftDown. The siftUp operation is only needed to perform inserts into an existing heap, so it would be used to implement a priority queue using a binary heap, for example.

I've written this to describe how a max heap works. This is the type of heap typically used for heap sort or for a priority queue where higher values indicate higher priority. A min heap is also useful; for example, when retrieving items with integer keys in ascending order or strings in alphabetical order. The principles are exactly the same; simply switch the sort order.

The heap property specifies that each node in a binary heap must be at least as large as both of its children. In particular, this implies that the largest item in the heap is at the root. Sifting down and sifting up are essentially the same operation in opposite directions: move an offending node until it satisfies the heap property:

• siftDown swaps a node that is too small with its largest child (thereby moving it down) until it is at least as large as both nodes below it.
• siftUp swaps a node that is too large with its parent (thereby moving it up) until it is no larger than the node above it.

The number of operations required for siftDown and siftUp is proportional to the distance the node may have to move. For siftDown, it is the distance to the bottom of the tree, so siftDown is expensive for nodes at the top of the tree. With siftUp, the work is proportional to the distance to the top of the tree, so siftUp is expensive for nodes at the bottom of the tree. Although both operations are O(log n) in the worst case, in a heap, only one node is at the top whereas half the nodes lie in the bottom layer. So it shouldn't be too surprising that if we have to apply an operation to every node, we would prefer siftDown over siftUp.

The buildHeap function takes an array of unsorted items and moves them until they all satisfy the heap property, thereby producing a valid heap. There are two approaches one might take for buildHeap using the siftUp and siftDown operations we've described.

1. Start at the top of the heap (the beginning of the array) and call siftUp on each item. At each step, the previously sifted items (the items before the current item in the array) form a valid heap, and sifting the next item up places it into a valid position in the heap. After sifting up each node, all items satisfy the heap property.

2. Or, go in the opposite direction: start at the end of the array and move backwards towards the front. At each iteration, you sift an item down until it is in the correct location.

Which implementation for buildHeap is more efficient?

Both of these solutions will produce a valid heap. Unsurprisingly, the more efficient one is the second operation that uses siftDown.

Let h = log n represent the height of the heap. The work required for the siftDown approach is given by the sum

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

Each term in the sum has the maximum distance a node at the given height will have to move (zero for the bottom layer, h for the root) multiplied by the number of nodes at that height. In contrast, the sum for calling siftUp on each node is

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

It should be clear that the second sum is larger. The first term alone is hn/2 = 1/2 n log n, so this approach has complexity at best O(n log n).

How do we prove the sum for the siftDown approach is indeed O(n)?

One method (there are other analyses that also work) is to turn the finite sum into an infinite series and then use Taylor series. We may ignore the first term, which is zero:

If you aren't sure why each of those steps works, here is a justification for the process in words:

• The terms are all positive, so the finite sum must be smaller than the infinite sum.
• The series is equal to a power series evaluated at x=1/2.
• That power series is equal to (a constant times) the derivative of the Taylor series for f(x)=1/(1-x).
• x=1/2 is within the interval of convergence of that Taylor series.
• Therefore, we can replace the Taylor series with 1/(1-x), differentiate, and evaluate to find the value of the infinite series.

Since the infinite sum is exactly n, we conclude that the finite sum is no larger, and is therefore, O(n).

Why does heap sort require O(n log n) time?

If it is possible to run buildHeap in linear time, why does heap sort require O(n log n) time? Well, heap sort consists of two stages. First, we call buildHeap on the array, which requires O(n) time if implemented optimally. The next stage is to repeatedly delete the largest item in the heap and put it at the end of the array. Because we delete an item from the heap, there is always an open spot just after the end of the heap where we can store the item. So heap sort achieves a sorted order by successively removing the next largest item and putting it into the array starting at the last position and moving towards the front. It is the complexity of this last part that dominates in heap sort. The loop looks likes this:

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

Clearly, the loop runs O(n) times (n - 1 to be precise, the last item is already in place). The complexity of deleteMax for a heap is O(log n). It is typically implemented by removing the root (the largest item left in the heap) and replacing it with the last item in the heap, which is a leaf, and therefore one of the smallest items. This new root will almost certainly violate the heap property, so you have to call siftDown until you move it back into an acceptable position. This also has the effect of moving the next largest item up to the root. Notice that, in contrast to buildHeap where for most of the nodes we are calling siftDown from the bottom of the tree, we are now calling siftDown from the top of the tree on each iteration! Although the tree is shrinking, it doesn't shrink fast enough: The height of the tree stays constant until you have removed the first half of the nodes (when you clear out the bottom layer completely). Then for the next quarter, the height is h - 1. So the total work for this second stage is

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

Notice the switch: now the zero work case corresponds to a single node and the h work case corresponds to half the nodes. This sum is O(n log n) just like the inefficient version of buildHeap that is implemented using siftUp. But in this case, we have no choice since we are trying to sort and we require the next largest item be removed next.

In summary, the work for heap sort is the sum of the two stages: O(n) time for buildHeap and O(n log n) to remove each node in order, so the complexity is O(n log n). You can prove (using some ideas from information theory) that for a comparison-based sort, O(n log n) is the best you could hope for anyway, so there's no reason to be disappointed by this or expect heap sort to achieve the O(n) time bound that buildHeap does.

Epistaxis

I edited my answer to use a max heap since it seems that most other people are referring to that and it is the best choice for heap sort. – Epistaxis

This is what made it intuitively clear to me: "only one node is at the top whereas half the nodes lie in the bottom layer. So it shouldn't be too surprising that if we have to apply an operation to every node, we would prefer siftDown over siftUp." – Caesarism

[As was commented by The111 to the Answer by emre nevayeshirazi] this wiki image also captures the comparative efficiency of just 1) making the heap with heapify (left diagram) over then 2) removing nodes to complete the heapSorting (right diagram): On the right diagram, think of the numbers as the max number of swaps for that Node when its turn comes to replace the root node that was deleted, in order for that swapping Node to then siftDown to its correct place (thereby completing 1 heap deletion [for the heapSort]). – Hypocrite

@JeremyWest "One is to start at the top of the heap (the beginning of the array) and call siftUp on each item." - Did you mean to start at the bottom of the heap? – Encephaloma

@Encephaloma No, it is correct as written. The idea is to maintain a barrier between the part of the array that satisfies the heap property and the unsorted portion of the array. You either start at the beginning moving forward and calling siftUp on each item or start at the end moving backward and calling siftDown. No matter which approach you choose, you are selecting the next item in the unsorted portion of the array and performing the appropriate operation to move it into a valid position in the ordered portion of the array. The only difference is performance. – Epistaxis

Great answer, upvoted. One thing that's not clear to me is, in order to implement the heap as an array, you'd start from the end of the k arrays, and insert n/2 elements in the heap array from the end. After that, where do you insert the next element, which is the parent of one of the n/2 elements at height h? – Miscue

@AbhijitSarkar Hi Abhijit, I'm not sure I understand your question. There aren't k arrays in question, just one. If you're thinking of one array per row of the heap (perhaps?), that's not necessary. You can just number the elements in the heap so that you know how to find the parents and children of each node. It's roughly something like 2n+1, 2n+2 are the children of node n, depending on where you start your indices. – Epistaxis

@JeremyWest I'm talking about building the heap from k arrays each of max size n, which would be initial step of a k-way merge. I was referred to your answer from my question here – Miscue

@Abhijit That is a pretty different problem. But the idea there is to put the first item from each of the k sorted arrays into the heap, build the heap, then as you return the item at the top of the heap, you add a new item from the stream it came from. – Epistaxis

This answer would be greatly improved in its utility to most readers if it included a pseudocode implementation of O(n) heap construction. – Signesignet

@Signesignet Sure, I can add some code. The algorithm is pretty standard and pseudocode and real implementations are available all over the place. – Epistaxis

In theory that is totally true but it took a surprising amount of time for me to find a clean implementation of the O(n) approach. It would just be beneficial, since this is a high-ranking search result, to bring the resources together into one place. – Signesignet

"The terms are all positive, so the finite sum must be smaller than the infinite sum." Isn't this not true in general? For example, the classic 1 + 2 + 3 + ... = -1/12. – Heteroecious

@AisforAmbition You're correct; it is only true if the series converges, which is true in this case. Your example is a reminder that all bets are off for divergent series! – Epistaxis

Somebody correct me if I'm wrong, but isn't using siftUp also O(N)? After all, every time an element is added to the bottom, there is a 1/2 chance that it needs to sift up 1 level, a 1/4 chance that it needs to sift up 2 levels, and so on, which sums to an average of 2 levels needed to sift up no matter the size of the tree, meaning siftUp is O(1) for 1 element and thus O(N) for making a heap. Am I making some logical mistake here? – Monocot

@Telescope I haven't thought about it too carefully, but your analysis does seem correct if we're talking about average case performance. For the siftDown implementation, the worst case behavior is guaranteed to be linear. – Epistaxis

It may be true ShiftDown seemed cheaper assuming each shift costs the same as ShiftUp. However if we consider ShiftDown require two comparisons per shift(To shift with Larger child in a Max Heap or smaller child in a Min Heap), while ShiftUp only requires a single comparison with its parent per shift, we could argue ShiftUp is in fact cheaper? – Kozak

@Kozak Yes, the worst case cost for siftDown on an arbitrary node is likely to be roughly twice that of siftUp. However, this constant factor has no impact on the big-O analysis for buildHeap as an algorithm. More importantly, we're going to apply one of these two functions to every node in the heap. As mentioned in the answer, siftDown is asymptotically less expensive when applied over the entire heap than siftUp. If you like, think of the siftDown implementation as O(2n) vs. the siftUp implementation with a cost of O(nlog n). 2 < log n even for very small values of n. – Epistaxis

@Jeremy Thank you! Crystal clear. Logn is good, but 2 is much better. – Kozak

This is a very complete and clear explanation. Well done! – Barrens

There are two approaches one might take for buildHeap that is begin from the top using siftUp and begin from the end using siftDown. Why can't we begin from the top and use siftDown? Or begin from the end using siftUp – Calm

Brilliant answer, specially the last point "Why does heap sort require O(n log n) time". – Nerve

Such a well written answer. Kudos! – Dunk

@Calm Suppose you started from the top, and used sift down. Everything has been working fine, and you are about to sift down (the key of) node k. But now one of the children of node k is a super giga huge number. It's not enough to just swap it with k. You have to sift it up a lot, potentially all the way to the root. So If you start reading your array from the top, and use sift down, you will probably have to mix in lots of sift up's as well. – Ukase

Answer 2

Your analysis is correct. However, it is not tight.

It is not really easy to explain why building a heap is a linear operation, you should better read it.

A great analysis of the algorithm can be seen here.

---

The main idea is that in the build_heap algorithm the actual heapify cost is not O(log n)for all elements.

When heapify is called, the running time depends on how far an element might move down in the tree before the process terminates. In other words, it depends on the height of the element in the heap. In the worst case, the element might go down all the way to the leaf level.

Let us count the work done level by level.

At the bottommost level, there are 2^(h)nodes, but we do not call heapify on any of these, so the work is 0. At the next level there are 2^(h − 1) nodes, and each might move down by 1 level. At the 3rd level from the bottom, there are 2^(h − 2) nodes, and each might move down by 2 levels.

As you can see not all heapify operations are O(log n), this is why you are getting O(n).

Janusfaced

This is a great explanation...but why is it then that the heap-sort runs in O(n log n). Why doesn't the same reasoning apply to heap-sort? – Wotan

@Wotan I think the answer to your question lies in understanding this image from this article. Heapify is O(n) when done with siftDown but O(n log n) when done with siftUp. The actual sorting (pulling items from heap one by one) has to be done with siftUp so is therefore O(n log n). – Layer

I really like your external document's intuitive explanation at the bottom. – Unsupportable

@Wotan the Answer below by Jeremy West addresses your question in more fine, easy-to-understand detail, further explaining The111's comment answer here. – Hypocrite

A question. It seems to me that the # comparisons made for a node at height i from the bottom of a tree of height h must make 2* log(h-i) comparisons as well and should be accounted for as well @The111. What do you think? – Upholstery

@Wotan HeapSort is nlogn because it involves extracting the minimum from the heap out (which lies at the root) n times, and each time, heapify down is called at the root which could at worst take log-n time. This is as opposed to emre's (OP's) answer that heapify down is called on all elements, only 1 of which lies at the root. – Stroke

youtube.com/… At about 38:00 – Modify

@Wotan Building the heap takes 0 operations for half the values, 1 operation for a quarter of values, 2 operations for 1/8th of the values etc. with a total O (N). When doing heapsort, all the operations take log n because you always remove an item from the top, then insert a new item at the top where it is most expensive to insert. – Proscription

Answer 3

Intuitively:

"The complexity should be O(nLog n)... for each item we "heapify", it has the potential to have to filter down once for each level for the heap so far (which is log n levels)."

Not quite. Your logic does not produce a tight bound -- it over estimates the complexity of each heapify. If built from the bottom up, insertion (heapify) can be much less than O(log(n)). The process is as follows:

( Step 1 ) The first n/2 elements go on the bottom row of the heap. h=0, so heapify is not needed.

( Step 2 ) The next n/22 elements go on the row 1 up from the bottom. h=1, heapify filters 1 level down.

( Step i ) The next n/2i elements go in row i up from the bottom. h=i, heapify filters i levels down.

( Step log(n) ) The last n/2log2(n) = 1 element goes in row log(n) up from the bottom. h=log(n), heapify filters log(n) levels down.

NOTICE: that after step one, 1/2 of the elements (n/2) are already in the heap, and we didn't even need to call heapify once. Also, notice that only a single element, the root, actually incurs the full log(n) complexity.

---

Theoretically:

The Total steps N to build a heap of size n, can be written out mathematically.

At height i, we've shown (above) that there will be n/2i+1 elements that need to call heapify, and we know heapify at height i is O(i). This gives:

The solution to the last summation can be found by taking the derivative of both sides of the well known geometric series equation:

Finally, plugging in x = 1/2 into the above equation yields 2. Plugging this into the first equation gives:

Thus, the total number of steps is of size O(n)

Accumbent

Thank you very much. Why you decided to plug in x=1/2 please? – Turnbuckle

Because of the formula of the sumation to infinity of i*x^i = x/ (1-x)^2. so i*(1/2)^i is the same as i*(x)^i when x = 1/2 – Emigrate

Answer 4

There are already some great answers but I would like to add a little visual explanation

Now, take a look at the image, there are
n/2^1 green nodes with height 0 (here 23/2 = 12)
n/2^2 red nodes with height 1 (here 23/4 = 6)
n/2^3 blue node with height 2 (here 23/8 = 3)
n/2^4 purple nodes with height 3 (here 23/16 = 2)
so there are n/2^(h+1) nodes for height h
To find the time complexity lets count the amount of work done or max no of iterations performed by each node
now it can be noticed that each node can perform(atmost) iterations == height of the node

Green  = n/2^1 * 0 (no iterations since no children)  
red    = n/2^2 * 1 (heapify will perform atmost one swap for each red node)  
blue   = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)  
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)   

so for any nodes with height h maximum work done is n/2^(h+1) * h

Now total work done is

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

now for any value of h, the sequence

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

will never exceed 1
Thus the time complexity will never exceed O(n) for building heap

Mortification

this is the best explanation ever. – Individualist

Answer 5

It would be O(n log n) if you built the heap by repeatedly inserting elements. However, you can create a new heap more efficiently by inserting the elements in arbitrary order and then applying an algorithm to "heapify" them into the proper order (depending on the type of heap of course).

See http://en.wikipedia.org/wiki/Binary_heap, "Building a heap" for an example. In this case you essentially work up from the bottom level of the tree, swapping parent and child nodes until the heap conditions are satisfied.

Rothmuller

Answer 6

As we know the height of a heap is log(n), where n is the total number of elements.Lets represent it as h
When we perform heapify operation, then the elements at last level(h) won't move even a single step.
The number of elements at second last level(h-1) is 2^h-1 and they can move at max 1 level(during heapify).
Similarly, for the i^th, level we have 2ⁱ elements which can move h-i positions.

Therefore total number of moves:

S= 2^h*0+2^h-1*1+2^h-2*2+...2⁰*h

S=2^h {1/2 + 2/2² + 3/2³+ ... h/2^h} -------------------------------------------------1

this is AGP series, to solve this divide both sides by 2
S/2=2^h {1/2² + 2/2³+ ... h/2^h+1} -------------------------------------------------2

subtracting equation 2 from 1 gives
S/2=2^h {1/2+1/2² + 1/2³+ ...+1/2^h+ h/2^h+1}
S=2^h+1 {1/2+1/2² + 1/2³+ ...+1/2^h+ h/2^h+1}

Now 1/2+1/2² + 1/2³+ ...+1/2^h is decreasing GP whose sum is less than 1 (when h tends to infinity, the sum tends to 1). In further analysis, let's take an upper bound on the sum which is 1.

This gives:
S=2^h+1{1+h/2^h+1}
  =2^h+1+h
  ~2^h+h

as h=log(n), 2^h=n

Therefore S=n+log(n)
T(C)=O(n)

Parallelize

Answer 7

While building a heap, lets say you're taking a bottom up approach.

1. You take each element and compare it with its children to check if the pair conforms to the heap rules. So, therefore, the leaves get included in the heap for free. That is because they have no children.
2. Moving upwards, the worst case scenario for the node right above the leaves would be 1 comparison (At max they would be compared with just one generation of children)
3. Moving further up, their immediate parents can at max be compared with two generations of children.
4. Continuing in the same direction, you'll have log(n) comparisons for the root in the worst case scenario. and log(n)-1 for its immediate children, log(n)-2 for their immediate children and so on.
5. So summing it all up, you arrive on something like log(n) + {log(n)-1}*2 + {log(n)-2}*4 + ..... + 1*2^{(logn)-1} which is nothing but O(n).

Summerly

Answer 8

We get the runtime for the heap build by figuring out the maximum move each node can take. So we need to know how many nodes are in each row and how far from their can each node go.

Starting from the root node each next row has double the nodes than the previous row has, so by answering how often can we double the number of nodes until we don't have any nodes left we get the height of the tree. Or in mathematical terms the height of the tree is log2(n), n being the length of the array.

To calculate the nodes in one row we start from the back, we know n/2 nodes are at the bottom, so by dividing by 2 we get the previous row and so on.

Based on this we get this formula for the Siftdown approach: (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (log2(n) * 1)

The term in the last paranthesis is the height of the tree multiplied by the one node that is at the root, the term in the first paranthesis are all the nodes in the bottom row multiplied by the length they can travel,0. Same formula in smart:

Bringing the n back in we have 2 * n, 2 can be discarded because its a constant and tada we have the worst case runtime of the Siftdown approach: n.

Watchtower

Answer 9

Short Answer

Building a binary heap will take O(n) time with Heapify().

When we add the elements in a heap one by one and keep satisfying the heap property (max heap or min heap) at every step, then the total time complexity will be O(nlogn). Because the general structure of a binary heap is of a complete binary tree. Hence the height of heap is h = O(logn). So the insertion time of an element in the heap is equivalent to the height of the tree ie. O(h) = O(logn). For n elements this will take O(nlogn) time.

Consider another approach now. I assume that we have a min heap for simplicity. So every node should be smaller than its children.

1. Add all the elements in the skeleton of a complete binary tree. This will take O(n) time.
2. Now we just have to somehow satisfy the min-heap property.
3. Since all the leaf elements have no children, they already satisfy the heap property. The total no of leaf elements is ceil(n/2) where n is the total number of elements present in the tree.
4. Now for every internal node, if it is greater than its children, swap it with the minimum child in a bottom to top way. It will take O(1) time for every internal node. Note: We will not swap the values up to the root like we do in insertion. We just swap it once so that subtree rooted at that node is a proper min heap.
5. In the array-based implementation of binary heap, we have parent(i) = ceil((i-1)/2) and children of i are given by 2*i + 1 and 2*i + 2. So by observation we can say that the last ceil(n/2) elements in the array would be leaf nodes. The more the depth, the more the index of a node. We will repeat Step 4 for array[n/2], array[n/2 - 1].....array[0]. In this way we ensure that we do this in the bottom to top approach. Overall we will eventually maintain the min heap property.
6. Step 4 for all the n/2 elements will take O(n) time.

So our total time complexity of heapify using this approach will be O(n) + O(n) ~ O(n).

Madonna

Answer 10

We can use another optimal solution to build a heap instead of inserting each element repeatedly. It goes as follows:

• Arbitrarily putting the n elements into the array to respect the shape property of heap.
• Starting from the lowest level and moving upwards, sift the root of each subtree downward as in the heapify-down process until the heap property is restored.

This process can be illustrated with the following image:

Next, let’s analyze the time complexity of this above process. Suppose there are n elements in the heap, and the height of the heap is h (for the heap in the above image, the height is 3). Then we should have the following relationship:

When there is only one node in the last level then n = 2^h . And when the last level of the tree is fully filled then n = 2^(h+1).

And start from the bottom as level 0 (the root node is level h), in level j, there are at most 2^(h-j) nodes. And each node at most takes j times swap operation. So in level j, the total number of operation is j*2^(h-j).

So the total running time for building the heap is proportional to:

If we factor out the 2^h term, then we get:

​As we know, ∑j/2ʲ is a series converges to 2 (in detail, you can refer to this wiki).

Using this we have:

Based on the condition 2^h <= n, so we have:

Now we prove that building a heap is a linear operation.

Trappist

Answer 11

In case of building the heap, we start from height, logn -1 (where logn is the height of tree of n elements). For each element present at height 'h', we go at max upto (logn -h) height down.

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)

Socialism

Answer 12

Successive insertions can be described by:

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

By starling approximation, n! =~ O(n^(n + O(1))), therefore T =~ O(nlog(n))

Hope this helps, the optimal way O(n) is using the build heap algorithm for a given set (ordering doesn't matter).

Coherence

Answer 13

Basically, work is done only on non-leaf nodes while building a heap...and the work done is the amount of swapping down to satisfy heap condition...in other words (in worst case) the amount is proportional to the height of the node...all in all the complexity of the problem is proportional to the sum of heights of all the non-leaf nodes..which is (2^h+1 - 1)-h-1=n-h-1= O(n)

Mcneely

Answer 14

@bcorso has already demonstrated the proof of the complexity analysis. But for the sake of those still learning complexity analysis, I have this to add:

The basis of your original mistake is due to a misinterpretation of the meaning of the statement, "insertion into a heap takes O(log n) time". Insertion into a heap is indeed O(log n), but you have to recognise that n is the size of the heap during the insertion.

In the context of inserting n objects into a heap, the complexity of the ith insertion is O(log n_i) where n_i is the size of the heap as at insertion i. Only the last insertion has a complexity of O (log n).

Vintage

Answer 15

Lets suppose you have N elements in a heap. Then its height would be Log(N)

Now you want to insert another element, then the complexity would be : Log(N), we have to compare all the way UP to the root.

Now you are having N+1 elements & height = Log(N+1)

Using induction technique it can be proved that the complexity of insertion would be ∑logi.

Now using

log a + log b = log ab

This simplifies to : ∑logi=log(n!)

which is actually O(NlogN)

But

we are doing something wrong here, as in all the case we do not reach at the top. Hence while executing most of the times we may find that, we are not going even half way up the tree. Whence, this bound can be optimized to have another tighter bound by using mathematics given in answers above.

This realization came to me after a detail though & experimentation on Heaps.

Mede

Answer 16

I really like explanation by Jeremy west.... another approach which is really easy for understanding is given here http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

since, buildheap depends using depends on heapify and shiftdown approach is used which depends upon sum of the heights of all nodes. So, to find the sum of height of nodes which is given by S = summation from i = 0 to i = h of (2^i*(h-i)), where h = logn is height of the tree solving s, we get s = 2^(h+1) - 1 - (h+1) since, n = 2^(h+1) - 1 s = n - h - 1 = n- logn - 1 s = O(n), and so complexity of buildheap is O(n).

Foxworth

Answer 17

"The linear time bound of build Heap, can be shown by computing the sum of the heights of all the nodes in the heap, which is the maximum number of dashed lines. For the perfect binary tree of height h containing N = 2^(h+1) – 1 nodes, the sum of the heights of the nodes is N – H – 1. Thus it is O(N)."

Trici

Answer 18

Proof of O(n)

The proof isn't fancy, and quite straightforward, I only proved the case for a full binary tree, the result can be generalized for a complete binary tree.

Minnesinger

Answer 19

Intuitive answer with a stupid (but cache oblivious) algorithm to do it:

Quickselect runs in linear time and is cache oblivious. You can use it to split an array in half around its median in linear time. If you recurse this procedure only on the lower half each time, then in only twice the time of the first quickselect you've built a heap (which also has the stronger property that values at each level are all lower than the values at the previous level).

Auspicious