Why is the top down approach of heap construction less efficient than bottom up even though its order of growth is lower O(log n) over O(n)?

Question

How is the bottom up approach of heap construction of the order O(n) ? Anany Levitin says in his book that this is more efficient compared to top down approach which is of order O(log n). Why?

Nitrogenous

#9756221 – Kluge

Answer 1

That to me seems like a typo.

There are two standard algorithms for building a heap. The first is to start with an empty heap and to repeatedly insert elements into it one at a time. Each individual insertion takes time O(log n), so we can upper-bound the cost of this style of heap-building at O(n log n). It turns out that, in the worst case, the runtime is Θ(n log n), which happens if you insert the elements in reverse-sorted order.

The other approach is the heapify algorithm, which builds the heap directly by starting with each element in its own binary heap and progressively coalescing them together. This algorithm runs in time O(n) regardless of the input.

The reason why the first algorithm requires time Θ(n log n) is that, if you look at the second half of the elements being inserted, you'll see that each of them is inserted into a heap whose height is Θ(log n), so the cost of doing each bubble-up can be high. Since there are n / 2 elements and each of them might take time Θ(log n) to insert, the worst-case runtime is Θ(n log n).

On the other hand, the heapify algorithm spends the majority of its time working on small heaps. Half the elements are inserted into heaps of height 0, a quarter into heaps of height 1, an eighth into heaps of height 2, etc. This means that the bulk of the work is spent inserting elements into small heaps, which is significantly faster.

Soul

Isn't the heapify algorithm less efficient compared to top down approach with respect to insertions? Because top down approach takes O(log n) for insertion but for heapify, first we insert the elements as in order and then heapify which is O(n). So if too many elements are to be inserted one after the other, heapify would act as O(n2) which is less efficient than O(n log n) of top down ? – Nitrogenous

They're designed to do different things. The heapify algorithm is for the case where you already have all the elements you want to put into the heap available up-front, and the other approach works if you don't know in advance how many elements you'll have or what they are. If you're getting elements one at a time, the heapify algorithm is not as good. – Soul

This helped. Thanks for the explanation. – Nitrogenous

@geek_code If you're interested in looking up a slightly more advanced data structure, you may want to look at binomial heaps, which require time O(n) to do n insertions even if you don't know how many elements there will be in advance. – Soul

In the line "in the worst case, the runtime is Θ(n log n)" why are you using theta to denote the worst case. AFAIK big O is used to denote worst case. Sorry for this silly question, if it is, but please tell me 'Why'. – Misadventure

Big-O notation means “something asymptotically this or less” and big-Theta denotes “something asymptotically equal to this,” so saying “the worst-case runtime is O(n log n)” would mean that we asymptotically never do more than n log n work, but doesn’t actually say that there’s some case where we do an amount of work proportional to n log n. As an analogy, if I tell you that I’m at most 10km tall, you have no idea how tall I really am because I just gave an upper bound. Saying that he worst-case runtime is Theta(n log n) says that we actually do have to do n log n work. – Soul

Answer 2

If you consider swapping to be your basic operation -

In top down construction,the tree is constructed first and a heapify function is called on the nodes.The worst case would swap log n times ( to sift the element to the top of the tree where height of tree is log n) for all the n/2 leaf nodes. This results in a O(n log n) upper bound.

In bottom up construction, you assume all the leaf nodes to be in order in the first pass, so heapify is now called only on n/2 nodes. At each level, the number of possible swaps increases but the number of nodes on which it happens decreases.

For example - At the level right above leaf nodes, we have n/4 nodes that can have at most 1 swap each. At its' parent level we have, n/8 nodes that can have at most 2 swaps each and so on. On summation, we'll come up with a O(n) efficiency for bottom up construction of a heap.

Pome

Answer 3

It generally refers to a way of solving a problem. Especially in computer science algorithms.

Top down :

Take the whole problem and split it into two or more parts. Find solution to these parts. If these parts turn out to be too big to be solved as a whole, split them further and find find solutions to those sub-parts. Merge solutions according to the sub-problem hierarchy thus created after all parts have been successfully solved.

In the regular heapify(), we perform two comparisons on each node from top to bottom to find the largest of three elements:

1. Parent node with left child
2. The larger node from the first comparison with the second child

Bottom up :

Breaking the problem into smallest possible(and practical) parts. Finding solutions to these small sub-problems. Merging the solutions you get iteratively(again and again) till you have merged all of them to get the final solution to the "big" problem. The main difference in approach is splitting versus merging. You either start big and split "down" as required or start with the smallest and merge your way "up" to the final solution.

Bottom-up Heapsort, on the other hand, only compares the two children and follows the larger child to the end of the tree ("top-down"). From there, the algorithm goes back towards the tree root (“bottom-up”) and searches for the first element larger than the root. From this position, all elements are moved one position towards the root, and the root element is placed in the field that has become free.

Perfectible

Answer 4

Binary Heap can be built in two ways:

1. Top-Down Approach
2. Bottom-Up Approach

In the Top-Down Approach, first begin with 3 elements. You consider 2 of them as heaps and the third as a key k. You then create a new Heap by joining these two sub-heaps with the key as the root node. Then, you perform Heapify to maintain the heap order (either Min or Max Heap order). The, we take two such heaps(containing 3 elements each) and another element as a k, and create a new heap. We keep repeating this process, and increasing the size of each sub-heap until all elements are added. This process adds half the elements in the bottom level, 1/4th in the second last one, 1/8th in the third last one and so on, therefore, the complexity of this approach results in a nearly observed time of O(n).

In the bottom up approach, we first simply create a complete binary tree from the given elements. We then apply DownHeap operation on each parent of the tree, starting from the last parent and going up the tree until the root. This is a much simpler approach. However, as DownHeap's worst case is O(logn) and we will be applying it on n/2 elements of the tree; the time complexity of this particular method results in O(nlogn).

Regards.

Jeneejenei