Heapsort in C++

Yasin Cakal

Heapsort is an efficient sorting algorithm that is used to sort data structures such as arrays and linked lists. Heapsort is based on the heap data structure, which is a specialized tree-based structure. Heapsort can be used in a variety of applications, such as sorting large datasets, organizing data, and finding the largest or smallest elements in a set of data. In this article, we will discuss the Heapsort algorithm, its time and space complexities, and provide examples of Heapsort in C++.

What is the Heapsort Algorithm?

Heapsort is an efficient sorting algorithm that is used to sort data structures such as arrays and linked lists. It works by organizing the elements of the data structure into a binary heap. A binary heap is a special kind of tree-based data structure in which each node is greater than or equal to its children. Heapsort begins by building a heap from the elements in the data structure, then it repeatedly extracts the maximum element from the heap and inserts it into the sorted list.

Heapsort Algorithm in C++

The following is an example of Heapsort in C++. It begins by building a heap from the elements in the array, then it repeatedly extracts the maximum element from the heap and inserts it into the sorted list.

// Heapsort in C++ 
#include <iostream> 
using namespace std; 

// Function to heapify the array 
void heapify(int arr[], int n, int i) 
{ 
	// Find the largest among root, left child and right 
	int largest = i; 
	int l = 2*i + 1; 
	int r = 2*i + 2; 

	if (l < n && arr[l] > arr[largest]) 
		largest = l; 

	if (r < n && arr[r] > arr[largest]) 
		largest = r; 

	// Swap and continue heapifying if root is not largest 
	if (largest != i) 
	{ 
		swap(arr[i], arr[largest]); 
		heapify(arr, n, largest); 
	} 
} 

// Main function to do Heapsort 
void heapSort(int arr[], int n) 
{ 
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// One by one extract an element from heap 
	for (int i=n-1; i>0; i--) 
	{ 
		// Move current root to end 
		swap(arr[0], arr[i]); 

		// call max heapify on the reduced heap 
		heapify(arr, i, 0); 
	} 
} 

// Function to print an array 
void printArray(int arr[], int size) 
{ 
	for (int i=0; i<size; ++i) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

// Driver program 
int main() 
{ 
	int arr[] = {12, 11, 13, 5, 6, 7}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	heapSort(arr, n); 

	cout << "Sorted array is \n"; 
	printArray(arr, n); 
}

Time Complexity of Heapsort

The time complexity of Heapsort can be broken down into three parts:

Best Case: The best case time complexity of Heapsort is O(nlog(n)), where n is the number of elements in the array. This is because Heapsort is an efficient sorting algorithm that can sort an array in linear time.
Average Case: The average case time complexity of Heapsort is also O(nlog(n)). This is because in the average case, Heapsort will have to go through all of the elements in the array in order to sort them.
Worst Case: The worst case time complexity of Heapsort is O(n^2). This is because in the worst case, Heapsort will have to go through all of the elements in the array multiple times in order to sort them.

Space Complexity of Heapsort

The space complexity of Heapsort is O(1), as Heapsort does not require any additional memory to perform the sorting.

Conclusion

In conclusion, Heapsort is an efficient sorting algorithm that can sort an array in linear time. It works by organizing the elements of the array into a binary heap and then repeatedly extracting the maximum element from the heap and inserting it into the sorted list. The time complexity of Heapsort is O(nlog(n)) in the best, average, and worst cases. The space complexity of Heapsort is O(1), as it does not require any additional memory to perform the sorting.

Exercises

Write a C++ program to sort an array of 10 integers using the Heapsort algorithm.

#include <iostream> 
using namespace std; 

// Function to heapify the array 
void heapify(int arr[], int n, int i) 
{ 
	// Find the largest among root, left child and right 
	int largest = i; 
	int l = 2*i + 1; 
	int r = 2*i + 2; 

	if (l < n && arr[l] > arr[largest]) 
		largest = l; 

	if (r < n && arr[r] > arr[largest]) 
		largest = r; 

	// Swap and continue heapifying if root is not largest 
	if (largest != i) 
	{ 
		swap(arr[i], arr[largest]); 
		heapify(arr, n, largest); 
	} 
} 

// Main function to do Heapsort 
void heapSort(int arr[], int n) 
{ 
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// One by one extract an element from heap 
	for (int i=n-1; i>0; i--) 
	{ 
		// Move current root to end 
		swap(arr[0], arr[i]); 

		// call max heapify on the reduced heap 
		heapify(arr, i, 0); 
	} 
} 

// Function to print an array 
void printArray(int arr[], int size) 
{ 
	for (int i=0; i<size; ++i) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

int main() 
{ 
	int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	heapSort(arr, n); 

	cout << "Sorted array is \n"; 
	printArray(arr, n); 

	return 0; 
}

Write a C++ program to find the minimum element in an array of 10 integers using the Heapsort algorithm.

#include <iostream> 
using namespace std; 

// Function to heapify the array 
void heapify(int arr[], int n, int i) 
{ 
	// Find the smallest among root, left child and right 
	int smallest = i; 
	int l = 2*i + 1; 
	int r = 2*i + 2; 

	if (l < n && arr[l] < arr[smallest]) 
		smallest = l; 

	if (r < n && arr[r] < arr[smallest]) 
		smallest = r; 

	// Swap and continue heapifying if root is not smallest 
	if (smallest != i) 
	{ 
		swap(arr[i], arr[smallest]); 
		heapify(arr, n, smallest); 
	} 
} 

// Function to find the minimum element in the array 
int findMin(int arr[], int n) 
{ 
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// Return the minimum element from the heap 
	return arr[0]; 
} 

// Driver program 
int main() 
{ 
	int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	int min = findMin(arr, n); 

	cout << "The minimum element in the array is " << min << endl; 

	return 0; 
}

Write a C++ program to find the maximum element in an array of 10 integers using the Heapsort algorithm.

#include <iostream> 
using namespace std; 

// Function to heapify the array 
void heapify(int arr[], int n, int i) 
{ 
	// Find the largest among root, left child and right 
	int largest = i; 
	int l = 2*i + 1; 
	int r = 2*i + 2; 

	if (l < n && arr[l] > arr[largest]) 
		largest = l; 

	if (r < n && arr[r] > arr[largest]) 
		largest = r; 

	// Swap and continue heapifying if root is not largest 
	if (largest != i) 
	{ 
		swap(arr[i], arr[largest]); 
		heapify(arr, n, largest); 
	} 
} 

// Function to find the maximum element in the array 
int findMax(int arr[], int n) 
{ 
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// Return the maximum element from the heap 
	return arr[0]; 
} 

// Driver program 
int main() 
{ 
	int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	int max = findMax(arr, n); 

	cout << "The maximum element in the array is " << max << endl; 

	return 0; 
}

Write a C++ program to find the kth smallest element in an array of 10 integers using the Heapsort algorithm.

#include <iostream> 
using namespace std; 

// Function to heapify the array 
void heapify(int arr[], int n, int i) 
{ 
	// Find the smallest among root, left child and right 
	int smallest = i; 
	int l = 2*i + 1; 
	int r = 2*i + 2; 

	if (l < n && arr[l] < arr[smallest]) 
		smallest = l; 

	if (r < n && arr[r] < arr[smallest]) 
		smallest = r; 

	// Swap and continue heapifying if root is not smallest 
	if (smallest != i) 
	{ 
		swap(arr[i], arr[smallest]); 
		heapify(arr, n, smallest); 
	} 
} 

// Function to find the kth smallest element in the array 
int findKthSmallest(int arr[], int n, int k) 
{ 
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// Extract the kth smallest element from the heap 
	for (int i=0; i<k-1; i++) 
	{ 
		swap(arr[0], arr[n-1]); 
		heapify(arr, n-1, 0); 
	} 

	// Return the kth smallest element 
	return arr[0]; 
} 

// Driver program 
int main() 
{ 
	int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int k = 5; 

	int kthSmallest = findKthSmallest(arr, n, k); 

	cout << "The " << k << "th smallest element in the array is " << kthSmallest << endl; 

	return 0; 
}

Write a C++ program to find the kth largest element in an array of 10 integers using the Heapsort algorithm.

#include <iostream> 
using namespace std; 

// Function to heapify the array 
void heapify(int arr[], int n, int i) 
{ 
	// Find the largest among root, left child and right 
	int largest = i; 
	int l = 2*i + 1; 
	int r = 2*i + 2; 

	if (l < n && arr[l] > arr[largest]) 
		largest = l; 

	if (r < n && arr[r] > arr[largest]) 
		largest = r; 

	// Swap and continue heapifying if root is not largest 
	if (largest != i) 
	{ 
		swap(arr[i], arr[largest]); 
		heapify(arr, n, largest); 
	} 
} 

// Function to find the kth largest element in the array 
int findKthLargest(int arr[], int n, int k) 
{ 
	// Build heap (rearrange array) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// Extract the kth largest element from the heap 
	for (int i=0; i<k-1; i++) 
	{ 
		swap(arr[0], arr[n-1]); 
		heapify(arr, n-1, 0); 
	} 

	// Return the kth largest element 
	return arr[0]; 
} 

// Driver program 
int main() 
{ 
	int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int k = 5; 

	int kthLargest = findKthLargest(arr, n, k); 

	cout << "The " << k << "th largest element in the array is " << kthLargest << endl; 

	return 0; 
}

Data Structures and Algorithms with C++

Participants 445