The time complexity of various heap operations depends on the specific operation being performed. Here are the time complexities for common heap operations in a binary heap:
-
Insertion:
- Time Complexity: O(log n)
- Explanation: In the worst case, the new element needs to be "bubbled up" from the leaf level to the root level, which takes log(n) steps, where n is the number of elements in the heap.
-
Deletion (Root):
- Time Complexity: O(log n)
- Explanation: After removing the root, the last element is moved to the root, and then the new root needs to be "bubbled down" to its correct position. This takes log(n) steps.
-
Access Root:
- Time Complexity: O(1)
- Explanation: Accessing the root of the heap, which is always at index 0, is a constant-time operation.
-
Heapify:
- Time Complexity: O(n)
- Explanation: The heapify operation involves starting from the last non-leaf node and performing a "bubble down" operation for each node. Since each node is visited once, the time complexity is linear in the number of elements (n).
-
Heap Sort:
- Time Complexity: O(n log n)
- Explanation: Building a max heap from an array takes O(n) time using the heapify operation. After that, each removal of the root and "bubbling down" takes log(n) time. The total time complexity is O(n log n).
-
Decrease Key (for Min Heap):
- Time Complexity: O(log n)
- Explanation: After decreasing the key of a node, the node needs to be "bubbled up" to its correct position, taking log(n) time.
-
Increase Key (for Max Heap):
- Time Complexity: O(log n)
- Explanation: After increasing the key of a node, the node needs to be "bubbled down" to its correct position, taking log(n) time.
These time complexities make heaps efficient for priority queue operations and sorting. The logarithmic time complexities are achieved because heaps are complete binary trees, and the height of a complete binary tree is logarithmic in the number of elements.
