0

I have just started out with heaps and I am stuck at being able to understand the intuition behind the BUILD MAX HEAP method in CLRS, I understand how it works, but do not understand WHY we require the bottom up approach to create the heap in the first place, and that too in linear time! When we already have the MAX HEAPIFY method which can effectively change around an array data structure in a way such that we can use it as a heap, and it runs in logarithmic time. Please help me out here, is there a fundamental error in the way that I have interpreted the way heaps work? Or is it something else?

Jgl
  • 13
  • 2
  • *"and it runs in logarithmic time"* - no, it doesn't. You cannot heapify an array in less than O(*n*) time. You can sift up or sift down a single element in O(log *n*) time, but not every element in O(log *n*) time. – kaya3 Dec 22 '19 at 13:13
  • 1
    See this other question for the difference between building a heap using sift-up vs. sift-down: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity – kaya3 Dec 22 '19 at 13:15
  • Thank you for the insight! Upon closer inspection I now realise how stupid the questions that I asked was. – Jgl Dec 22 '19 at 15:09
  • Not stupid, just a misconception; everybody learning CS is going to have misconceptions sometimes. – kaya3 Dec 22 '19 at 15:25

0 Answers0