In this section of the tutorial, we will discuss the Heap Sort in Data Structure and its concept and the algorithm of Heap Sort for performing different sorting operations in detail.
Now let’s move further to the introduction of Heap Sort in Data Structure.
What is Heap Sort in Data Structure?
Heap Sort is an improvised version of Selection Sort in which the largest element is selected as the root and is exchanged with the last element in the unsorted list. In Heap Sort, the unsorted elements are checked and the largest element from all the elements present in the array or tree is selected.
We will look into Heap representation in its array and tree forms.
- The reheap operation is applied on the data elements.
- Reheap operation moves the largest element to the root by flowing through the tree branches.
- The ability of Heap Sort to flow through the tree branches makes it faster to process than other straight sorting methods such as selection sort.
- Heap Sort works upon selecting the largest element from the unsorted elements.
- It makes Heap Sort efficient and faster to process than other sorting methods such as selection sort, which selects the smallest element that makes the process slow.
Now we will dive deep into the concept involved in Heap Sort which makes it much faster and efficient sorting method among other sorting methods.
Concept used in Heap Sort
The concept of Heap Sort is entirely understood the part where an array list of tree is converted into a Heap to begin the sorting process. We will understand the concepts and processing of Heap Sort in the points given below.
We will look into the illustrated diagrams below to understand the Heap creation and Heap Sort operation.
- The array list is converted into a heap once for each sort pass.
- Then the root (largest element) is exchanged with the last element in the unsorted array list.
- With this, the largest element is placed at the beginning of the sorted list.
- Again the exchange takes place by reheap down operation to place another element in the sorted list by exchanging.
- This reheap and exchange of data elements from the heap to the sorted list is repeated continuously until the entire list of array is sorted.
In other words, we can conclude that the Heap Sort is an improvised version of Selection Sort in which the largest element is selected as the root and is exchanged with the last element in the unsorted list.
Heap Sort Algorithm
Now that we are familiar with the concept of Heap Sort, we can now develop an algorithm of Heap Sort before we put it into implementation.
Algorithm HeapSort (heap, last) 1 set walker to 1 2 loop (heap built) 1 ReheapUp (heap, walker) 2 increment walker 3 end loop 4 set sorted to last 5 loop (until all data sorted) 1 exchange (heap, 0, sorted) 2 decrement sorted 3 ReheapDown (heap, 0, sorted) 6 end loop end HeapSort
Working of Heap Sort
- Here, we will sort an array list by first creating a Heap.
- Then we will operate Heap Sort operation on the created Heap, which will eventually sort our original array list.
- Heap array is filled with array elements.
- last is index value to the last element in the array.
- A loop is iterated after we have created the heap, the loop breaks only when all the data elements are completely sorted.
- The algorithm turns the array into heap by using the ReheapUp algorithm.
- Then the created heap is sorted by exchanging of elements on the top of the heap with the elements at the end of the heap.
Time and Space Complexity of Algorithm
Heap Sort Complexity |
Best Case |
Average Case |
Worst Case |
Time Complexity | O(nlogn) | O(nlogn) |
O(nlogn) |
Space Complexity | O(1) |
Heap Sort Implementation
Now that we understand the concept of Heap Sort and also we have written the algorithm of Heap Sort, now we can implement Heap Sort in a programming language to perform the operation. Here, we will implement the Heap Sort in C and C++.
Implementation in C
Code:
#include<stdio.h> int main() { int arr[8]={94,48,102,44,-32,71,53,11}, i, j, c, root, temp; int no=sizeof(arr[8])/sizeof(arr[0]); for (i = 1; i < no; i++) { c = i; do { root = (c - 1) / 2; if (arr[root] < arr[c]) { temp = arr[root]; arr[root] = arr[c]; arr[c] = temp; } c = root; } while (c != 0); } for (j = no - 1; j >= 0; j--) { temp = arr[0]; arr[0] = arr[j]; arr[j] = temp; root = 0; do { c = 2 * root + 1; if ((arr[c] < arr[c + 1]) && c < j-1) c++; if (arr[root]) { temp = arr[root]; arr[root] = arr[c]; arr[c] = temp; } root = c; } while (c < j); } for (i = 0; i < no; i++) printf("%d ", arr[i]); return 0; }
Output:
-32 11 44 48 53 71 94 102
Implementation in C++
Code:
#include <iostream> #include <vector> void HeapSort(std::vector<int>& array1); void Create_Max_Heap(std::vector<int>& array1); void Max_Heap(std::vector<int>& array1, int i, int size_); int main() { std::vector<int> array1 = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; HeapSort(array1); for(int i = 0; i < array1.size(); i++) { std::cout << array1[i] << " "; } std::cout << "\n"; return 0; } void HeapSort(std::vector<int>& array1) { Create_Max_Heap(array1); int sz = array1.size(); for(int i = array1.size() - 1; i > 0; i--) { std::swap(array1[0], array1[i]); sz--; Max_Heap(array1, 0, sz); } } void Create_Max_Heap(std::vector<int>& array1) { for(int i = (array1.size() / 2); i >= 0; i--) Max_Heap(array1, i, array1.size()); } void Max_Heap(std::vector<int>& array1, int i, int size_) { int largest, l = (2*i) + 1, r = l + 1; if(l < size_ && array1[l] > array1[i]) largest = l; else largest = i; if(r < size_ && array1[r] > array1[largest]) largest = r; if(largest != i) { std::swap(array1[i], array1[largest]); Max_Heap(array1, largest, size_); } }
Output:
1 2 3 4 7 8 9 10 14 16
In the next section of the tutorial, we will discuss the Counting Sort in Data Structure and its concept and the algorithm of Counting Sort for performing different sorting operations in detail. We shall discuss the algorithm and working principle in the same way as done in this article using real-world examples.