Menu
I am trying to mostly understand the reasoning behind the Big O and Omega of inserting a new element in a heap. I know I can find answers online but I really like having a thorough understanding rather than just finding answers online and just memorizing blindly.
So for instance if we have the following heap (represented in array format)
[8,6,7,3,5,3,4,1,2]
If we decide to insert a new element "4" our array will look like this now
[8,6,7,3,5,3,4,1,2,4]
It would be placed in index 9 and since this is a 0th index based array its parent would be index 4 which is element 5. In this case we would not need to do anything because 4 is < 5 and it does not violate the binary heap property. So best case is OMEGA(1).
However if the new element we insert is 100 then we would have to call the max-heapify function which has running time of O(log n) and therefore in the worst case inserting a new element in the heap takes O(log n).
Can someone correct me if I am wrong because I am not sure if my understanding or reasoning is 100%?
228
Since, the complexity of deleting an element from any Heap is O(logN), therefore, the time complexity for sorting goes to N times of O(logN) .
Naive approach: We can extract the maximum element from the max-heap k times and the last element extracted will be the kth greatest element. Each deletion operations takes O(log n) time, so the total time complexity of this approach comes out to be O(k * log n).
Heap is based on array, and for creating an array you need O(n), for inserting into a heap you need O(logN), so if you have a unordered list of task and you want to create a heap, you need O(NLogN). If you use an array, you need O(n), to create the array, and O(NlogN) to sort the array, so you need O(NLogN).
Time Complexity of Min/Max Heap The Time Complexity of this operation is O(1).
Yes you are right about the best-case running time. And for the worst-case running time, you are also right that this is Theta(lg n) and the reason why is that your heap is always assumed to be BALANCED, i.e. every height level set of nodes is full except at the bottom level. So when you insert an element at the bottom level and swap from one level up to the next level in your heap, the number of nodes at that level is cut roughly in half and so you can only do this swap log_2(n) = O(lg n) times before you are at the root node (i.e. the level at the top of the heap that has just one node). And if you insert a value that belongs at the top of the heap, initially at the bottom of the heap then you will indeed have to do basically log_2(n) swaps to get the element to the top of the heap where it belongs.. So the number of swaps in the worst case is Theta(lg n).
180
Your understanding is correct. Since the heap has a complete binary tree structure, its height = lg n (where n is no of elements). In the worst case (element inserted at the bottom has to be swapped at every level from bottom to top up to the root node to maintain the heap property), 1 swap is needed on every level. Therefore, the maximum no of times this swap is performed is log n. Hence, insertion in a heap takes O(log n) time.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
