Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
Define Max-heap.
4.2.
What is a set in the Standard Template Library (STL)?
4.3.
What is the main idea behind DFS?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Heap Sort for Decreasing Order Using Min-Heap

Introduction

This blog covers a problem related to the heap data structure. Heaps are among the most important and often asked data structures in programming contests and technical interviews. There are various standard heap problems and techniques. This blog tackles a coding task that involves sorting a given array in decreasing order using min-heap.

Problem Statement

Ninja is given an array of integers. He is assigned to sort the given array in a decreasing order using min-heap. Can you help Ninja to complete his task?

Min-Heap: A Min-Heap is a complete binary tree in which the value of each internal node is less than or equal to the value of that node's children. The mapping of heap elements to array elements is simple: if a node is stored at index k, then its left child is stored at index 2k + 1 and its right child is stored at index 2k + 2.

Sample Examples

Example 1

Input

Output

Explanation

Self-Explanatory
 

Example 2

Input

Output

Explanation

Self-Explanatory

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 HeapBinary HeapBuild HeapMin 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 problemsinterview 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!

Live masterclass