Heap Operations
A heap is a specialized tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues and for efficient sorting algorithms like heapsort.
There are two main types of heaps:
| Operation | Time Complexity | Notes |
|---|---|---|
| buildHeap | O(n) | Bottom-up heapify is more efficient than repeated inserts |
| insert | O(log n) | Bubble-up takes log time in worst case |
| delete_min / delete_max | O(log n) | Swap + heapify down from root |
| bubble_up_min_heap / bubble_up_max_heap | O(log n) | Recursive up the tree |
| min_heapify / max_heapify | O(log n) | Recursive down the tree |
| peek | O(1) | Just return the root element |
| getSize | O(1) | Returns vector size |
| display | O(n) | Linear traversal of the array |
| isMinHeap / isMaxHeap | O(n) | Checks all parent-child relationships |