Binary Max Heap Time Complexity

Question

I am unable to find the time complexity of Binary Heaps. At one post it states that

1. Creating Binary Max Heap is O(n)
2. Adding/Inserting Items is O(logn)

However wikipedia states

1. Creating Binary Heap is O(nlogn)
2. Adding/Inserting Items is O(logn)

I would appreciae it if someone could tell me what the Creating,Adding and Deleting time complexities of Binary( Max) Heaps are ?

Answer 1

Turning an unordered array into a binary heap in place is an O(n) operation. So obviously if you have a bunch of items from which you want to build a heap, you put them in an array and call a method that will rearrange the array into a heap. That method is typically called BuildHeap or Heapify.

If you build an empty heap and then add n items to it, it will take O(log n) operations to insert each item, making for a O(n log n) running time.

Answer 2

The Wikipedia article suggests an algorithm of building a heap in O(n). Although of course you can build it on O(n log n).

All other modification operations require O(log n).

Answer 3

Time complexity to heapify from bottom to top is O(n) (using given arry to heapify)

Time complexity to heapify from top to bottom is O(nlogn) (Create heap one node at a time)

Answer 4

You can build a binary heap by inserting the n elements one after the other which means the runtime is O(n log(n)) assuming that the heap property holds for all subtrees of height h. You can build a heap storing n keys using bottom-up construction with log(n) phases. Since each node is traversed by at most two proxy paths, the total number of nodes at the proxy path is O(n). Therefore, bottom-up heap construction runs in O(n) time.