Approach
The approach to the given problem is an interesting one. We build a min-heap from the given array data. The smallest item is kept at the heap's root. Replace it with the heap's final item to lower the heap size by one. Finally, heapify the tree's root until the heap size is bigger than 1.
Algorithm
1. Create a minimum heap from the input data.
2. The smallest item is kept at the heap's root. Replace it with the heap's final element, then reduce the heap's size by one.
3. Finally, heapify the tree's root.
4. Repeat steps 1-3 until the heap size is more than 1.
Implementation
#include <bits/stdc++.h>
using namespace std;
// To heapify a subtree
void heapify(int nums[], int n, int i)
{
int smallest = i; // Initialize smallest as root
int l = 2 * i + 1; // left node= 2*i + 1
int r = 2 * i + 2; // right node= 2*i + 2
if (l < n && nums[l] < nums[smallest])
smallest = l;
if (r < n && nums[r] < nums[smallest])
smallest = r;
if (smallest != i) {
swap(nums[i], nums[smallest]);
// Recursively heapify the sub-tree
heapify(nums, n, smallest);
}
}
// function for performing a heap sort
void sortArray(int nums[], int n)
{
for (int j = n / 2 - 1; j >= 0; j--)
heapify(nums, n, j);
for (int j = n - 1; j >= 0; j--) {
swap(nums[0], nums[j]);
heapify(nums, j, 0);
}
}
/* function to print array of size n */
void printer(int nums[], int n)
{
for (int i = 0; i < n; ++i)
cout << nums[i] << " ";
cout << "\n";
}
// Driver program
int main()
{
int nums[] = { 4, 6, 3, 2, 9 };
int n = sizeof(nums) / sizeof(nums[0]);
sortArray(nums, n);
cout << "Sorted array is: \n";
printer(nums, n);
}
You can also try this code with Online C++ Compiler
Run Code
Output
Time Complexity
Heapify takes O(logn) while heap construction takes O(n). Hence, the overall time complexity of heap sorting with min heap or max heap is O (nlogn).
Space Complexity
The Space Complexity of the above approach is O(n) for using the call stack.
Frequently Asked Questions
Define Max-heap.
A max-heap can be defined as a complete binary tree in which each internal node's value is larger than or equal to the values of that node's children.
What is a set in the Standard Template Library (STL)?
Set is a C++ STL container used to store the unique elements, and all the elements are stored in a sorted manner. Once the value is stored in the set, it cannot be modified within the set; instead, we can remove this value and can add the modified value of the element.
What is the main idea behind DFS?
The main idea behind the DFS is to begin at the root or any random node and mark the node before moving to the next unmarked node and repeating this loop until there are no unmarked nearby nodes.
Conclusion
In this blog, we discussed a coding problem where we sorted a given array in decreasing order using min-heap. We discussed the time and space complexity of the approach as well.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Implementation of Heap, Binary Heap, Build Heap, Min Heap.
Recommended Problems -
Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problems, interview experiences, and interview bundle.
You should also consider our premium courses to offer your career advantage over others!
Please upvote our blogs if you find them useful and exciting!
Happy Coding!