Heaps and Priority Queues
📘 Data Structure and Algorithm
👁 121 views
📅 Nov 05, 2025
⏱ Estimated reading time: 1 min
Heaps and Priority Queues
A heap is a special type of binary tree used to implement priority queues. It is a complete binary tree that satisfies the heap property:
- Max Heap: Parent node value is greater than or equal to its children.
- Min Heap: Parent node value is smaller than or equal to its children.
Structure
Heaps are usually implemented using arrays:
// For a node at index i: Left child = 2 * i + 1 Right child = 2 * i + 2 Parent = (i - 1) / 2
Operations on Heap
- Insert: Add a new element at the end and heapify up.
- Delete: Remove the root and heapify down.
- Peek: Access the root element (max or min).
- Heapify: Rearrange nodes to maintain heap property.
Time Complexity
| Operation | Time Complexity |
|---|---|
| Insertion | O(log n) |
| Deletion | O(log n) |
| Find Max/Min | O(1) |
Applications
- Priority queue implementation.
- Heap sort algorithm.
- Dijkstra’s shortest path algorithm.
- Job scheduling systems.
Conclusion
Heaps are efficient structures for managing priority-based data. Understanding heap operations is essential for optimizing algorithms that depend on dynamic ordering.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials