Binary Max Heap Time Complexity

Question

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

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

However wikipedia states

Creating Binary Heap is O(nlogn)
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 ?

score 2 · Answer 1 · answered Mar 23 '14 at 23:17

2

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.

answered Mar 23 '14 at 23:17

Jim Mischel

131,090
20
188
351

Thanks cleared my doubts. But can you please tell me some practical application second type? – Mayukh Sarkar May 17 '20 at 08:06

score 1 · Accepted Answer · answered Mar 23 '14 at 16:04

1

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

answered Mar 23 '14 at 16:04

nullptr

11,008
1
23
18

Thanks. That makes sense. Marked as answer – Rajeshwar Mar 23 '14 at 16:06

score 0 · Answer 3 · answered Apr 22 '21 at 07:01

0

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)

answered Apr 22 '21 at 07:01

sendon1982

9,982
61
44

score 0 · Answer 4 · answered May 31 '21 at 06:58

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.

Binary Max Heap Time Complexity

4 Answers4