1

What are the performance differences between a bottom-up HeapSort and a top-down HeapSort ?

Prince Zuko
  • 31
  • 1
  • 6
  • Welcome to Stack Overflow. This is not a homework completion service. Your instructor gave you the assignment, not us, and you're going to need to do your own work. If we do it for you, you don't learn anything. If you can't get started, ask your teacher for help; they're being paid to teach you. Good luck. – Ken White May 28 '18 at 02:23
  • Seriously ? I'm just asking which one would be better performance wise. – Prince Zuko May 28 '18 at 04:01
  • 1
    Have you [done your research](https://en.wikipedia.org/wiki/Heapsort)? – eesiraed May 28 '18 at 04:13
  • Take a look at [bottom up vs top down heap sort](https://stackoverflow.com/questions/36226714/why-is-the-top-down-approach-of-heap-construction-less-efficient-than-bottom-up). – rcgldr May 28 '18 at 14:40

1 Answers1

3

A heap is a binary tree; therefore, we know it has log n depth and each level has 2^i nodes. Level 0 (root) has 1 node, level 1 has 2 nodes, level 2 has 4 nodes, etc.

Now think about the two methods you have mentioned:

For bottom-up, we insert nodes to the bottom and let them "bubble up" the heap each time. Contrarily, for top-down, we let the nodes "fall down" to their rightful place. Which one is more efficient?

Let's think about the worst-case scenarios:

In bottom-up, each node could rise to the very top level. At level 1, that requires one swap (on two nodes); at level 2, that requires two (on four nodes)... and once we get to the last level, we have to make log n swaps (on a quite large n/2 nodes)! This gives us O(n log n) efficiency.

Top-down: at each level, any node can fall to the bottom of the tree (log n swaps). The way it is distinguished from bottom-up is that as the maximum fall distance increases, the number of potential nodes affected by it decreases. Level 0 is the only one that can fall log n, and that is just one node (rather than n/2 as in bottom-up). Therefore, the summation of all the "falls" is O(n) and it is the more efficient algorithm.

Brandon Hass
  • 41
  • 2