1
votes

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 ?

4

4 Answers

2
votes

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.

1
votes

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).

0
votes

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)

0
votes

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.