First let us know about what binary heap is:
A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:
- the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
- the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.
- Also, a Binary Heap is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
The deletion of a random node would take O(n+log(n)) which equivalent to O(n) (worst case) as first we will find where the random element is in the heap which will take O(n) and then delete it which will further take O(log(n))
Therefore time complexity would be O(n)