A Heap Tree is a complete binary tree that satisfies the heap property:
-
Complete Binary Tree: All levels are filled except possibly the last, and the last level has all keys as left as possible.
-
Heap Property:
-
In a Max Heap, the parent node ≥ child nodes.
-
In a Min Heap, the parent node ≤ child nodes.
-
🔧 Types of Heap Tree:
| Type | Property | Root Node | Usage |
|---|---|---|---|
| Max Heap | Parent ≥ Children | Maximum | Priority Queues, Sorting (Heap Sort) |
| Min Heap | Parent ≤ Children | Minimum | Dijkstra’s Algorithm, Huffman Coding |
🔢 Example (Min Heap):
10
/ \
20 15
/ \ /
30 40 50
⚙️ Basic Operations:
| Operation | Description | Time Complexity |
|---|---|---|
| Insertion() | Add element and heapify up | O(log n) |
| Deletion() | Remove root and heapify down | O(log n) |
| Peek() | Get root element (max/min) | O(1) |
| Heapify() | Convert array into heap | O(n) |
✅ Applications of Heap Tree
-
Priority Queue implementation
-
Heap Sort algorithm
-
Graph Algorithms (Dijkstra, Prim)
-
Scheduling Systems (CPU Scheduling)
✅ Advantages and Diadvantages of Heap Tree
No comments:
Post a Comment