Module 3 (Important topics + PYQ + Model paper)
1. Heap (MP+24)
2. Heap sort (MP+24+25)
3. Counting sort (25)
4. Horsepool Algorithm (MP+24+25)
5. AVL tree & Rotations (MP+24+25)
1. Heap (MP+24)
A Heap is a special type of complete binary tree used in algorithms, where the tree satisfies the heap property. It
is mainly used to implement priority queues and is an important data structure in Heap Sort.
Types of Heap
A. Max heap: In a Max Heap, the value of each parent node is greater than or equal to its children. Root node
contains the largest element.
B. Min heap : In a Min Heap, the value of each parent node is less than or equal to its [Link] node
contains the smallest element.
Properties of Heap
1. Complete Binary Tree Property
o All levels are completely filled except possibly the last level.
o The last level is filled from left to right.
2. Heap Order Property
o In Max Heap → Parent ≥ Children
o In Min Heap → Parent ≤ Children
3. Height of Heap
o Height of a heap with n nodes = ⌊log₂ n⌋
o So operations like insert and delete take O(log n) time.
4. Efficient Root Access
o Maximum (in Max Heap) or Minimum (in Min Heap) is always at the root.
5. Not a Binary Search Tree
o Heap does not maintain sorted order between siblings or subtrees
Representation of Heap
Heap is generally represented using an array.
For a node at index i:
(1-based indexing)
• Left Child = 2i
• Right Child = 2i + 1
• Parent = ⌊i/2⌋
(0-based indexing)
• Left Child = 2i + 1
• Right Child = 2i + 2
• Parent = ⌊(i - 1)/2⌋
2. Heap sort
time complexity in all cases (best , worst , average ) is O(n log n).
Step 1: Build Max Heap
Convert the given array into a Max Heap.
Step 2: Sort the Array
• Swap the root (largest element) with the last element.
• Reduce heap size by 1.
• Apply heapify on the root.
• Repeat until heap size becomes 1.
3. Counting Sort
Simple Algorithm
Step 1: Find Maximum Element
Find the maximum value k in the array.
Step 2: Create Count Array
Create a count array C[0…k] and initialize all values to 0.
Step 3: Store Frequencies
Count how many times each element appears.
Step 4: Find Cumulative Sum
Modify count array so that each element stores the sum of previous counts.
Step 5: Build Output Array
Place elements into the output array using count positions.
4. Horsepool algorithm
Steps of Horspool Algorithm
Let:
T = Text of length n
P = Pattern of length m
Step 1: Preprocessing (Bad match Table Creation)
▪ Create a Bad match Table for all characters.
▪ Initialize all shifts to m.
▪ For each character in pattern (except last),
Value = length (m) – index -1
Step 2: Pattern Matching
▪ Align pattern with beginning of text.
▪ Compare from right to left
▪ If mismatch occurs, shift pattern using shift value of mismatched text character.
Repeat until pattern is found or text ends.
ALL Problem explination videos in playlist
Playlist link :