Basic Heap Operations
Insert an element into the heap
1. Create a hole in the next available location (i.e. in the next available position of the array representation)
§ This step maintains the complete binary tree property, ensuring the tree remains balanced (each level filled from left to right).
2. Bubble Up (Heapify Up):
§ Check if the new element violates the heap property. In a min-heap, the element should be smaller than or equal to its parent.
§ If the element is smaller than its parent, swap it with the parent.
§ Continue to swap with parents until either:
o The element is larger than its parent, or
o The element reaches the root of the heap (where it has no parent).
Example – to insert 1 into the heap
2
/ \
4 5
/ \
7 6
2
/ \
4 5
/ \ \
7 6 1
2
/ \
4 1
/ \ \
7 6 5
1
/ \
4 2
/ \ \
7 6 5
DeleteMin
Deleting the Root Element in a Min-Heap
- Remove the Root Element – (Root element is the smallest element in a min-heap)
- To maintain the complete binary tree structure, replace the root with the last element in the heap (the rightmost element in the last level).
- The heap's size is now reduced by one.
- Heapify Down (Bubble Down):
- Check if the new element violates the heap property. In a min-heap, the element at root should be smaller than or equal to its child.
- If the element is larger than its child, swap it with the smaller child.
- Continue to swap with children until either:
- The element is smaller than its children, or
- The element reaches the leaf of the heap (where it has no children).
- This restores the min-heap property, ensuring every parent node is smaller than its children.
Example – to delete minimum element in the heap
2
/ \
4 5
/ \ \
7 6 8
8
/ \
4 5
/ \
7 6
4
/ \
8 5
/ \
7 6
4
/ \
6 5
/ \
7 8
No comments:
Post a Comment
Don't be a silent reader...
Leave your comments...
Anu