Heap Sort in Data Structure: An Overview
What is heap sort in data structure?
Heap sort algorithm in data structure
Example
Python
# Heap Sort in python
def heapify(arr, n, i):
# Find the largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [2, 22, 9, 3, 8, 13]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d " % arr[i], end='')
Java
public class HeapSort {
public void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public void heapSort(int arr[]) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from the heap one by one
for (int i = n - 1; i >= 0; i--) {
// Swap root element with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
public static void main(String args[]) {
int arr[] = {2, 22, 9, 3, 8, 13};
int n = arr.length;
HeapSort heapSort = new HeapSort();
heapSort.heapSort(arr);
System.out.println("Sorted array is");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
C++
#include <iostream>
using namespace std;
class HeapSort {
public:
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from the heap one by one
for (int i = n - 1; i >= 0; i--) {
// Swap root element with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
};
int main() {
int arr[] = {2, 22, 9, 3, 8, 13};
int n = sizeof(arr) / sizeof(arr[0]);
HeapSort heapSort;
heapSort.heapSort(arr, n);
cout << "Sorted array is" << endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Explanation
In order to sort an array (arr) in ascending order, the Heap Sort algorithm first builds a maximum heap and then repeatedly swaps the array's root element with its last element.
Output:
Sorted array is
2, 3, 8, 9, 13, 22Working of Heap Sort Algorithm
- Build Max Heap: The first step is to build a max heap from the input array. To do this, we start from the last non-leaf node and heapify the array in a bottom-up manner. Heapify means that we compare the parent node with its children and swap them if necessary to maintain the heap property. This process ensures that the largest element is at the root of the heap.
- Heapify: After building the max heap, we have the largest element at the root. We swap this element with the last element in the unsorted region. Then, we reduce the size of the heap (considering the last element as sorted) and perform heapify on the root to maintain the heap property. This step effectively moves the maximum element from the unsorted region to the sorted region.
- Repeat: We repeat the heapify step until the heap becomes empty. Each iteration will result in moving the maximum element from the unsorted region to the sorted region.
- Obtain Sorted Array: Finally, we have a sorted array when the heap is empty and all elements have been moved to the sorted region. The sorted array is obtained by removing elements from the sorted region and placing them in the appropriate positions.
Visualization of heap sort
- Start by considering the list as a binary tree.
- Convert the list into a max heap by applying the "heapify" operation.
- Heapify ensures that the largest element is at the root of the tree and that each subtree is also a max heap.
- In this case, swap 9 with 2.
- The last element in the heap is 9, so move it to the end of the list.
- Apply heapify to the root node (2) and its children (8 and 3).
- Swap the root node (8) with the last element of the heap (3).
- Remove 8 from the heap and place it at the end of the list.
- Apply heapify to the root node (3) and its child (2).
- Swap the root node (5) with the last element of the heap (2).
- Remove 5 from the heap and place it at the end of the list.
- Apply heapify to the root node (2) and its child (3).
- Swap the root node (3) with the last element of the heap (2).
- Remove 3 from the heap and place it at the end of the list.
Implementation of Heap Sort Algorithm
Example
Python
def heapify(arr, n, i):
largest = i
left_child = 2 * i + 1
right_child = 2 * i + 2
# If the left child is larger than the root
if left_child < n and arr[left_child] > arr[largest]:
largest = left_child
# If the right child is larger than the largest so far
if right_child < n and arr[right_child] > arr[largest]:
largest = right_child
# If the largest is not the root
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# Recursively heapify the affected sub-tree
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements from the heap one by one
for i in range(n - 1, 0, -1):
# Swap the root (maximum element) with the last element
arr[i], arr[0] = arr[0], arr[i]
# Call heapify on the reduced heap
heapify(arr, i, 0)
def print_array(arr):
for value in arr:
print(value, end=" ")
print()
if __name__ == "__main__":
arr = [12, 11, 13, 5, 6, 7]
print("Original array:")
print_array(arr)
heap_sort(arr)
print("\nSorted array:")
print_array(arr)
Java
public class HeapSort {
public static void heapify(int arr[], int n, int i) {
int largest = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void heapSort(int arr[]) {
int n = arr.length;
// Build a max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from the heap one by one
for (int i = n - 1; i >= 0; i--) {
// Swap the root (maximum element) with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
public static void printArray(int arr[]) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
System.out.println("Original array:");
printArray(arr);
heapSort(arr);
System.out.println("\nSorted array:");
printArray(arr);
}
}
C++
#include <iostream>
using namespace std;
class HeapSort {
public:
static void heapify(int arr[], int n, int i) {
int largest = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
static void heapSort(int arr[], int n) {
// Build a max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from the heap one by one
for (int i = n - 1; i >= 0; i--) {
// Swap the root (maximum element) with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
static void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
};
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array:" << endl;
HeapSort::printArray(arr, n);
HeapSort::heapSort(arr, n);
cout << "\nSorted array:" << endl;
HeapSort::printArray(arr, n);
return 0;
}
Explanation
The heap_sort method is implemented in this code to sort an array in ascending order, the heapify function is defined to maintain the max-heap property, and an example array is used to show how to use it [12, 11, 13, 5, 6, 7].
Output
Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13Heap sort complexity
Heap Sort Time Complexity
- Worst Case: O(nlogn).The worst scenario is when a list is arranged in descending order but we wish to sort it in ascending order.
- Average Case: O(nlogn). The most common scenario is when the list is organized randomly.
- Best Case: O(n). When the list is already in the appropriate order, that is the ideal situation. The tree doesn't need to be heapified in this situation. It reduces the complexity by a factor of logn, resulting in an O(n) complexity.
Heap Sort Space Complexity
The heap sort algorithm has O(1) space complexity. This is due to the fixed amount of variables we have used, which means that aside from the loop variables and auxiliary variables like temp, n, index, and biggest, we do not require any additional memory space. It indicates that even without the use of a second variable, we can sort an array with 1,000 elements.
Applications of heap sort
- Sorting: Heap sort can efficiently sort an array of elements in ascending or descending order. It has a worst-case time complexity of O(n log n), which makes it suitable for sorting large data sets.
- Priority Queue: Heap sort can be used to implement a priority queue, where each element has a priority associated with it. The heap structure allows for the efficient insertion and extraction of elements based on their priority.
- Selection of Top-K Elements: Heap sort can be used to efficiently find the top-k elements from a large dataset. By building a max-heap, the k largest elements can be extracted in O(k log n) time complexity.
- Median Finding: Heap sort can be employed to find the median of a dataset. By using two heaps (a max-heap for the lower half of elements and a min-heap for the upper half), the median can be determined in O(log n) time complexity for each element.
- External Sorting: Heap sort can be used in external sorting algorithms, where data is too large to fit entirely in memory. It can be applied in the initial phase of sorting, where chunks of data are sorted and written back to the disk before merging them.
Heap sort advantages and disadvantages
Advantages of heap sort
- Efficiency: Heap sort has a time complexity of O(n log n) in all cases, where 'n' is the number of elements to be sorted. This makes it more efficient than many other sorting algorithms, such as bubble sort or insertion sort, which have higher time complexities in the worst case.
- Space efficiency: Heap sort in data structure sorts the elements in place, meaning it does not require additional memory proportional to the number of elements being sorted. It achieves this by utilizing the original array to build a binary heap and then performing in-place swaps to sort the elements.
- Guaranteed worst-case performance: Unlike some other sorting algorithms, such as quicksort, which have a worst-case time complexity of O(n^2) in certain scenarios, heap sort guarantees a worst-case time complexity of O(n log n) regardless of the input data distribution. This predictability makes it a reliable choice in situations where worst-case performance is critical.
- In-place sorting: As mentioned earlier, heap sort performs sorting in place, which means it does not require additional memory beyond the input array. This makes it suitable for situations where memory usage is a concern or when working with large datasets that may not fit into available memory.
- Stability: Heap sort is a stable sorting algorithm, meaning it preserves the relative order of elements with equal keys. This property can be important in certain applications where maintaining the original order of elements is necessary.
- Simplicity: The basic concept of heap sorting is relatively simple to understand compared to some other advanced sorting algorithms. It involves building a binary heap and repeatedly extracting the maximum (or minimum) element from the heap to construct the sorted array. This simplicity makes it easier to implement and debug.
- Partial sorting: Heap sort can be easily modified to perform partial sorting, where only the top k elements are sorted, rather than the entire array. This feature can be useful in situations where only a subset of the largest or smallest elements is required
Disadvantages of heap sort
- Not a stable sorting algorithm: Heap sort does not guarantee the relative order of elements with equal keys. If there are duplicate elements in the input array, their order may change after sorting. This makes heap sort unsuitable for sorting certain types of data where stability is important.
- Requires additional space: Heap sort requires additional space to build the heap data structure. The sorting algorithm itself is an in-place algorithm, meaning it sorts the elements within the input array without requiring additional memory. However, the process of creating the heap initially requires a separate heap data structure, which can consume extra memory. This extra space requirement can be a disadvantage when working with large data sets.
- Poor cache performance: Heap sort does not exhibit good cache performance, especially compared to other sorting algorithms like to merge sort or quicksort. This is because heap sort accesses memory in a non-sequential manner, jumping between different parts of the heap. This irregular memory access pattern can lead to cache misses and slower performance, particularly when sorting large arrays.
- The complexity of implementation: Implementing heap sort correctly can be more complex compared to other sorting algorithms like bubble sort or insertion sort. Building the heap and performing the heapify operation to maintain the heap property requires careful implementation. This complexity can make heap sorting harder to understand and debug, especially for novice programmers.
- Not adaptive: Heap sort does not take advantage of any existing order in the input array. It always performs the same number of comparisons and swaps regardless of the initial order of the elements. This lack of adaptivity makes it less efficient than some other sorting algorithms when applied to partially sorted or nearly sorted arrays.
FAQs
1. What is heap sort in data structure?
The binary heap data structure is used by the comparison-based sorting algorithm known as heap sort to arrange the items in a predetermined order.
2. What are the two types of heap sort?
Depending on whether they organize objects in ascending or descending order, the two forms of heap sort are called Max Heap Sort and Min Heap Sort.
3. What is the example of heap sort?
Sorting an array of numbers like [4, 2, 9, 7, 5] in ascending order is an example of a heap sort.
4. What is heap sort used for?
Large datasets can be effectively sorted using heap sort, which is frequently used in algorithms like priority queues.
5. What are the advantages of heap sort?
The advantages of heap sort include in-place sorting, time complexity of O(n log n), and consistent performance independent of the distribution of the input data.
Summary
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
