Heap

1. Overview

Definition: A heap is a specialized tree-based data structure that satisfies the heap property as described below:
Types:
- Max-Heap: The parent node has a value greater than or equal to its children.
- Min-Heap: The parent node has a value less than or equal to its children.
Common Implementations:
- Binary Heap: Most common heap implementation which uses a complete binary tree structure.
- Fibonacci Heap: More advanced, allowing for more efficient merge operations.
- Binomial Heap: Amalgamates multiple binomial trees for optimized operations.
Operations:
- Insertion: Adding a new element while maintaining the heap property.
- Deletion: Typically removing the root (max or min), followed by reorganizing to maintain heap integrity.
- Peek: Accessing the root element without modifying the heap.
Applications:
- Priority Queues: Heaps are commonly used to implement priority queues.
- Heap Sort: An efficient sorting algorithm that utilizes a heap.
- Graph Algorithms: Utilized in algorithms like Dijkstra's shortest path.
Time Complexity:
- Insertion: O(log n)
- Deletion (removing root): O(log n)
- Accessing the root: O(1)
- Building a heap: O(n)