Applications of Binary Tree : 1. Heap Sort
Trees are hierarchical data structures widely used in computing due to their efficient organization, searching, and processing capabilities. They play a crucial role in various applications such as data storage, sorting, compression, and optimization.
Applications :
- Sorting – Heap Sort uses a binary heap to achieve an efficient sorting time.
- Data Compression – Huffman Coding reduces file sizes by encoding characters based on frequency.
- Optimization Algorithms – Many greedy and dynamic programming strategies use trees for efficient decision-making.
1. Binary Heap
A heap is a specialized binary tree-based data structure that satisfies the heap property:
- In a max-heap, the key at each node is greater than or equal to the keys of its children.
- In a min-heap, the key at each node is less than or equal to the keys of its children.
Heap insertion involves maintaining the heap property while adding a new element to a binary heap.
To understand the heap sort algorithm let us first understand the Heap Insertion (Build Heap) and Heap deletion (extract Max or root). It is because Heap Sort algorithm involves primarily two steps. i) build Max Heap and ii) Extract max.
Heap Insertion (Max Heap)
In a max-heap, the key at each node is greater than or equal to the keys of its children.
Insertion Algorithm:
- Add the Element:
- Place the new element at the end of the heap (as the last leaf).
- Heapify-Up:
- Compare the inserted element with its parent.
- If the inserted element is greater than its parent (in max-heap), swap them.
- Repeat this process until the heap property is restored or the element reaches the root.
Example:
Consider the following max-heap:
50
/ \
30 20
/ \ /
15 10 8
Step 1: Insert 40 Add the new element at the end:
50
/ \
30 20
/ \ / \
15 10 8 40
Step 2: Heapify-Up
- Compare 40 with its parent (20).
- Since 40 > 20, swap them.
50
/ \
30 40
/ \ / \
15 10 8 20
compare 40 with its new parent (50).
- Since 40 < 50, no more swapping is needed.
Finally heap:
50
/ \
30 40
/ \ / \
15 10 8 20
Heap Deletion (Extract-Max)
Heap deletion refers to removing the root element (the maximum element in a max-heap or the minimum element in a min-heap) while maintaining the heap property.
- Remove the root (maximum element).
- Replace the root with the last element in the heap.
- Heapify-Down (Max-Heapify):
- Compare the new root with its largest child.
- If the new root is smaller than the largest child, swap them.
- Repeat until the heap property is restored.
Example:
Initial Max-Heap
50
/ \
30 40
/ \ / \
15 10 8 20
Step 1: Remove the Root (50)
- Replace it with the last element (20).
20
/ \
30 40
/ \ /
15 10 8
Step 2: Heapify-Down
- Compare 20 with its children 30 and 40.
- Swap 20 with the larger child (40).
40
/ \
30 20
/ \ /
15 10 8
- Now, compare 20 with its new children (8, no need to swap).
- The heap property is restored.
Final Heap after Deletion
40
/ \
30 20
/ \ /
15 10 8
Heap Sort
The Heap Sort Algorithm is based on the principles of a binary heap. It involves two primary phases: building a max heap and sorting the array.
Key Concepts you must understand.
- Heapify:
- A function to maintain the max-heap property by comparing a node with its children and swapping it with the largest child if necessary. This operation is applied recursively until the subtree rooted at the node satisfies the max-heap property.
- Build-Heap:
- A procedure to convert an unordered array into a max-heap by repeatedly applying the heapify operation.
- Heap Sort:
Uses the max-heap to repeatedly extract the maximum element (root) and place it at the end of the array, reducing the heap size by 1.
Steps in Heap Sort
- Build-Max-Heap
Construct a max-heap from the input array. Start heapifying from the last non-leaf node up to the root.
- Sort the Array
- Swap the root (largest element) with the last element of the heap.
- Reduce the heap size by 1.
- Restore the max-heap property by calling heapify on the root.
Repeat this process until the heap size is reduced to 1.
Algorithm (Pseudocode)
Max-Heapify
This function restores the max-heap property for a subtree rooted at index iii.
MAX-HEAPIFY(A, i, heap_size)
left ← 2 * i + 1 // Index of left child
right ← 2 * i + 2 // Index of right child
largest ← i
IF left < heap_size AND A[left] > A[largest]
largest ← left
IF right < heap_size AND A[right] > A[largest]
largest ← right
IF largest ≠ i
SWAP(A[i], A[largest])
MAX-HEAPIFY(A, largest, heap_size)
2. Build-Max-Heap
BUILD-MAX-HEAP(A)
heap_size ← LENGTH(A)
FOR i ← (heap_size / 2) – 1 DOWNTO 0
MAX-HEAPIFY(A, i, heap_size)
3. Heap-Sort
HEAP-SORT(A)
BUILD-MAX-HEAP(A)
heap_size ← LENGTH(A)
FOR i ← LENGTH(A) – 1 DOWNTO 1
SWAP(A[0], A[i]) // Move max to end
heap_size ← heap_size – 1 // Reduce heap size
MAX-HEAPIFY(A, 0, heap_size)
Example.
Example
Input Array: [8, 32, 6, 15, 5]
Step 1: Build Max Heap
Original array: [8, 32, 6, 15, 5]
After building max-heap: [32, 15, 6, 8, 5]
Step 2: Extract Max and Heapify
- Swap root (32) with the last element (5):
[5,1 5, 6, 8, 32]
Heapify: [15, 8, 6, 5, 32]
- Swap root (15) with the last element (5):
[5, 8, 6, 15, 32]
Heapify: [8, 5, 6, 15, 32]
- Swap root (8) with the last element (5):
[5, 6, 8, 15, 32]
Heapify: [6, 5, 8, 15, 32]
- Swap root (6) with the last element (5):
[5, 6, 8, 15, 32]
Result: [5, 6, 8, 15, 32]
