Heap is a complete binary tree that satisfies the heap property. It's commonly used to implement priority queues.
Key Characteristics:
Max Heap: Parent nodes are greater than or equal to their children. The largest element is at the root.
Min Heap: Parent nodes are less than or equal to their children. The smallest element is at the root.
Operation | Time Complexity | Space Complexity |
---|---|---|
Insert | O(log n) | O(1) |
Extract Root | O(log n) | O(1) |
Peek Root | O(1) | O(1) |
Build Heap | O(n) | O(1) |
Strengths:
Limitations: