Binary Heap

1. Key Properties and Characteristics

Definition: A binary heap is a complete binary tree that satisfies the heap property.
Heap Property:
- Max-Heap: The key of each node is greater than or equal to the keys of its children. The maximum key is at the root.
- Min-Heap: The key of each node is less than or equal to the keys of its children. The minimum key is at the root.
Structure:
- Complete binary trees, meaning all levels are fully filled, except possibly for the last level.
- Efficiently stored in array format, where for a node at index i:
  - Left child: 2*i + 1
  - Right child: 2*i + 2
  - Parent: floor((i - 1) / 2)
Time Complexity:
- Insertion: O(log n)
- Deletion: O(log n)
- Find-min or Find-max: O(1)
- Building a heap: O(n)
Applications:
- Priority Queues: Efficiently manage dynamically changing priority data.
- Heapsort: An efficient sorting algorithm using binary heaps.
- Graph algorithms: Such as Dijkstra’s and Prim’s for minimum spanning trees.