What is the time complexity of insertion and deletion in a Heap? Why?

Difficulty: 3/10

heap operations, time complexity, priority queue

Heap Operation Complexity

Heap insertion takes O(log n) because the new element is initially placed at the end and may bubble up along the height of the heap. Removing the root also takes O(log n): the last element replaces the root and is then sifted down. Since a heap is complete, its height is O(log n).

javascript

1
Peek: O(1).
2
Insertion: O(log n).
3
Delete-min/delete-max: O(log n).
4
Search for an arbitrary value: O(n) in the general case.
5
Heap height is O(log n) because the tree is complete.

Scenario Questions

0-2 years experience

Follow-up Questions