Lab Manual: Data Structures and
Algorithms (DSA)
Lab Topic: Heap Sort
Objectives:
1. Understand the concept of heap data structures (max heap and min heap).
2. Implement heap sort algorithm in C++.
3. Analyze the time complexity of heap sort.
Introduction to Heap Sort:
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It
involves the following steps:
1. Build a max heap from the input data.
2. Repeatedly remove the largest element from the heap and rebuild the heap.
Key Properties of Heap:
A max heap is a binary tree where the parent node is always greater than or equal to its
child nodes.
In an array representation of a heap, for a node at index i:
o Left child is at index 2*i + 1.
o Right child is at index 2*i + 2.
o Parent node is at index (i-1)/2.
Algorithm Steps:
1. Heapify: Convert an array into a max heap.
2. Extract Max: Swap the root of the heap with the last element, reduce the heap size, and
heapify the root.
3. Repeat step 2 until the heap is empty.
C++ Implementation:
#include <iostream>
#include <vector>
using namespace std;
// Function to heapify a subtree rooted at index i
void heapify(vector<int>& arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
// Main function to perform heap sort
void heapSort(vector<int>& arr) {
int n = arr.size();
// Build a max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
// Function to print the array
void printArray(const vector<int>& arr) {
for (int i : arr)
cout << i << " ";
cout << endl;
}
// Main function
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
cout << "Original array: \n";
printArray(arr);
heapSort(arr);
cout << "Sorted array: \n";
printArray(arr);
return 0;
}
Sample Output:
Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13
Time Complexity Analysis:
1. Building the heap: O(n)
2. Heapify operation: O(log n) (performed n times during extraction)
3. Overall complexity: O(n log n)
Practice Questions:
1. Modify the heap sort algorithm to sort the array in descending order.
2. Write a function to build a min heap instead of a max heap.
3. Explain the differences between heap sort and merge sort in terms of performance and
use cases.
Conclusion:
Heap sort is an efficient, in-place, and non-stable sorting algorithm. It is widely used in scenarios
requiring guaranteed O(n log n) performance without additional memory allocation.
