Join Our 4-Week Free Gen AI Course with select Programs.

Request a callback

or Chat with us on

Heap Sort in Data Structures

Q: Is the heap sort stable?

Since Heap Sort in Data Structure may alter the relative sequence of comparable keys, heap sort is not stable. One can represent the binary heap using array-based techniques to save space and memory.

Q: What is heap sort's space complexity, and why?

Since no additional data structures are being used, Heap Sort in Data Structure is a built-in sorting method. Its spatial complexity is O as a result (1).

Q: Why is Heap sort better than Selection sort?

In contrary to selection sort, the heap sort maintains the unsorted area in the heap data structure to discover the biggest element more rapidly at every step instead of wasting time using the unsorted region’s linear-time scan. Sorting an array of values that have been randomly permuted using heapsort.

Q: What are the two phases of Heap Sort?

The Heap Sort in Data Structure is divided into two steps: The array that has to be sorted is transformed into a max heap in the first stage. The biggest element, or the one at the tree's root, is eliminated in the second stage, after which a new max heap is built from the remaining components.

Q: How much time does it take to find the maximum and minimum element in a max heap?

When using a max heap, it will require O(1), and when using a min heap, it will need O(n).

Basics of SQL

12 Hrs. duration

12 Modules

2600+ Learners

Start Learning

A binary tree is a tree in which a node can have a maximum of two offspring, while a heap is a full binary tree. A full binary tree has all levels filled in, except for the last level, or leaf node, with all nodes aligned to the left. The Heap sort Algorithm will be discussed in this post. Heap sort in data structure is responsible for processing the items by utilising the components of the provided array to create the max-heap or min-heap. The ordering of an array is known as a max-heap or min-heap, with the root member serving as the array’s maximum or minimum element.

Let’s first take a quick look at the description of heap sort before learning more about it.

Table of Content

What Is Heap Sort?
What is Heap Data Structure?
How Does Heap Sort Algorithm Work?
How to “heapify” a tree
Heap sort complexity
Implementation of Heap Sort (Java, Python, C, C++, )
Advantages of Heap Sort
Disadvantages of Heap Sort
Applications of Heap Sort
FAQs

What is Heap Sort?

Heap sort refers to the algorithm which is a comparison-based in-place sorting method that uses the available memory space and doesn’t require any more memory. As the name implies, heap sort uses a data structure called a heap to sort the supplied array. Due to its advantageous worst-case time complexity, it is one of the most favoured Sorting in Data Structures algorithms.

Like how selection sort separates an array into two parts, heap sort likewise does so.

Sorted region
Unsorted region

We have the unsorted area of the array at first, with the sorted region being empty. Iteratively, the biggest element is selected from the unsorted region and added to the sorted region. A special kind of full binary tree called a heap represents the elements in an unsorted area of the array.

What is Heap Sort in Data Structure?

"</p

Whether it is a max-heap or a min-heap, a heap is a full binary tree where the nodes are arranged differently.

Each given node in a heap data structure, which meets the heap property, is one of the following:

The root node’s key is the biggest of all the nodes and always greater than any of its child nodes. The max heap property is another name for this property.
The root node’s key is the smallest of all the nodes and always smaller than the child node or nodes. It is also known as the minimum heap property.

Another name for this kind of data structure is a binary heap.You can also check Business Analytics and Data Science program by Hero Vired.

How Does Heap Sort Work?

There are 2 fundamental components to a heap sort in Data Structures. The unsorted list or array is first compiled into a heap, and the sorted array is then made by continually removing the largest and smallest elements from the heap and adding them to the array. With each elimination, the heap is rebuilt.

The initial heap sort stage generates a Heap data structure when given an unsorted list (Max-Heap or Min-Heap). When a heap is formed, the first member will be the largest or the smallest (depending on whether Max-Heap or Min-Heap is used). Thus we will place that element in our array. Finally, we use the remaining items to create a heap again, selecting the first piece and inserting it into the array. We continuously perform the same thing until we have the entire sorted list in our array.

How To “Heapify” A Tree?

"<br We can convert a complete binary tree into a Max-Heap using the heapify function on all the non-leaf items in a heap. It might be challenging to understand heapify since it employs recursion. Heapify is the process of transforming a valid heap data structure from a binary tree.

The typical method is to start at the last internal node and work up to the root node, exchanging each node with the largest child node unless the heap property is met. The procedure is repeated for the impacted subtrees until the entire tree is a valid heap. Heapify has an O(log n) time complexity, where n refers to the number of nodes in the tree.

Complexity of Heap Sort in Data Structure

The number of levels the new element must ascend to meet the heap property determines the number of operations needed. As a result, the worst-case time complexity of the insertion operation is O. (log n). The average-case complexity of the insertion operation is O for a random heap and repeated insertions (1).

1. Time Complexity

The length of the input determines how long it takes an heap sort algorithm in Data Structures to run, known as temporal complexity. It calculates how long each algorithm’s code statement takes to run.

Case	Time Complexity
Best Case	O(n logn)
Average Case	O(n log n)
Worst Case	O(n log n)

2. Best Case Complexity – When there’s no need for sorting, that is when the array is sorted already, it gives rise to the best-case complexity. The heap sort’s best-case time complexity will be O (n logn).

3. Average Case Complexity – This happens when the array’s items are arranged in an inconsistent manner that is neither correctly ascending nor downward. The heap sort’s average case time complexity is O (n log n).

Sorting Algorithm	Average Case Complexity
Bubble Sort	O(n^2)
Insertion Sort	O(n^2)
Selection Sort	O(n^2)
Merge Sort	O(n log n)
Quick Sort	O(n log n)
Heap Sort	O(n log n)
Radix Sort	O(nk)

4. Worst Case Complexity- It happens when the array’s items are sorted in a reversible manner. The array’s items are in descending order. Therefore, let’s say you need to sort them in ascending order. The heap sort’s worst-case time complexity is O (n log n).

The heap sort’s time complexity in all four scenarios is O (n logn). A full binary tree with n items has a height of logn.

5. Space Complexity

The amount of storage or working space a heap sort algorithm in Data Structures needs is called its space complexity. It is closely correlated with or proportionate to how much input the algorithm receives. Calculating how much space an algorithm’s variables occupy will yield space complexity. The algorithm runs more quickly, and the less space it needs. It’s also crucial to understand that space difficulty and temporal complexity are unrelated.

Space Complexity	O(1)
Stable	N0

Implementation of Heap Sort

The following images show the implementation of Heap Sort in Java, Python, C and C++:

Heap sort in Java

Below is the example of heap sort in Java:

public class HeapSort {
 public void sort(int arr[]) {
  int n = arr.length;
	//Rearrange array (building heap)
  	for (int i = n / 2 - 1; i >= 0; i--) {
    	heapify(arr, n, i);
  	}
  	//Extract elements from heap one by one
  	for (int i = n - 1; i >= 0; i--) {
    	//Current root moved to the end
    	int tmp = arr[0];
    	arr[0] = arr[i];
    	arr[i] = tmp;
	heapify(arr, i, 0);//calling max heapify on the heap reduced
  	}
	}
 
           void heapify(int arr[], int n, int i) {
  	int max = i; //Initialize max as root
  	int leftChild = 2 * i + 1;
  	int rightChild = 2 * i + 2;
 
  	//If left child is greater than root
  	if (leftChild < n && arr[leftChild] > arr[max])
    	max = leftChild;
 
  	//If right child is greater than max
  	if (rightChild < n && arr[rightChild] > arr[max])
    	max = rightChild;
 
  	//If max is not root
  	if (max != i) {
    	int swap = arr[i];
    	arr[i] = arr[max];
    	arr[max] = swap;
 
    	//heapify the affected sub-tree recursively
    	heapify(arr, n, max);
  	}
	}
 
	//print size of array n using utility function
	static void display(int arr[]) {
  	int n = arr.length;
  	for (int i = 0; i < n; ++i)
    	System.out.print(arr[i] + " ");
  	System.out.println();
	}
 
	//Driver code
	public static void main(String args[]) {
  	int arr[] = {11, 34, 9, 5, 16, 10};
 
  	HeapSort hs = new HeapSort();
  	System.out.println("Original array:");
  	display(arr);
        	  hs.sort(arr);
 
  	System.out.println("Sorted array:");
  	display(arr);
	}
  }
 
Output of the program:
 Original array:
 11 34 9 5 16 10
 Sorted array:
 5 9 10 11 16 34

Internship Assurance

DevOps & Cloud Engineering

Explore

Heap sort in Python

Below is the example of heap sort in Python:

def heapify(arr, n, i):
	largest = i #Initialize max as root
	l = 2 * i + 1
	r = 2 * i + 2
 
	//If left child is greater than root
	if l < n and arr[i] < arr[l]:
  	largest = l
	
	//If right child is greater than max
	if r < n and arr[largest] < arr[r]:
  	largest = r
 
	//If max is not root
	if largest != i:
  	arr[i], arr[largest] = arr[largest], arr[i]
  	heapify(arr, n, largest) //heapify the root
 
//Main function to perform heap sort
def heapSort(arr):
  n = len(arr)
 
  #Build MaxHeap
  for i in range(n //2, -1, -1):
	heapify(arr, n, i)
 
  #Extract elements from heap one by one
  for i in range(n - 1, 0, -1):
	arr[i], arr[0] = arr[0], arr[i]
	heapify(arr, i, 0)
 
#Driver code
arr = [11, 34, 9, 5, 16, 10]
n = len(arr)
print("Original array:")
for i in range(n):   	
	print("%d " % arr[i], end = '')
heapSort(arr)
print("Sorted array:")
for i in range(n):   	
	print("%d " % arr[i], end = '')
Output of the program:
 Original array:
 11 34 9 5 16 10
 Sorted array:
 5 9 10 11 16 34

Heap sort in C

Below is the example of heap sort in C:

#include    	
  void swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
  }
  void heapify(int arr[], int n, int i) {
	int max = i; //Initialize max as root
	int leftChild = 2 * i + 1;
	int rightChild = 2 * i + 2;
	//If left child is greater than root
	if (leftChild < n && arr[leftChild] > arr[max])
  	max = leftChild;
	//If right child is greater than max
	if (rightChild < n && arr[rightChild] > arr[max])
  	max = rightChild;
	//If max is not root
	if (max != i) {
  	swap(&arr[i], &arr[max]);
  	//heapify the affected sub-tree recursively
  	heapify(arr, n, max);
	}
  }
  //Main function to perform heap sort
  void heapSort(int arr[], int n) {
	//Rearrange array (building heap)
	for (int i = n / 2 - 1; i >= 0; i--)
  	heapify(arr, n, i);
    //Extract elements from heap one by one
	for (int i = n - 1; i >= 0; i--) {
  	swap(&arr[0], &arr[i]); //Current root moved to the end
  	heapify(arr, i, 0); //calling max heapify on the heap reduced
	}
  }
  //print size of array n using utility function
  void display(int arr[], int n) {
	for (int i = 0; i < n; ++i)
  	printf("%d ", arr[i]);
	printf("n");
  }
  //Driver code
  int main() {
	int arr[] = {11, 34, 9, 5, 16, 10};
	int n = sizeof(arr) / sizeof(arr[0]);
	printf("Original array:n");
	display(arr, n);
	heapSort(arr, n);
	printf("Sorted array:n");
	display(arr, n);
  }
Output of the program:
 Original array:
 11 34 9 5 16 10
 Sorted array:
 5 9 10 11 16 34

Heap sort in C++

Below is the example of heap sort in C++:

#include 
  using namespace std;
 
  void heapify(int arr[], int n, int i) {
	int max = i; //Initialize max as root
	int leftChild = 2 * i + 1;
	int rightChild = 2 * i + 2;
 
	//If left child is greater than root
	if (leftChild < n && arr[leftChild] > arr[max])
  	max = leftChild;
 
	//If right child is greater than max
	if (rightChild < n && arr[rightChild] > arr[max])
  	max = rightChild;
 
	//If max is not root
	if (max != i) {
  	swap(arr[i], arr[max]);
  	heapify(arr, n, max); //heapify the affected sub-tree recursively
	}
  }
 
  //Main function to perform heap sort
  void heapSort(int arr[], int n) {
	//Rearrange array (building heap)
	for (int i = n / 2 - 1; i >= 0; i--)
  	heapify(arr, n, i);
 
	//Extract elements from heap one by one
	for (int i = n - 1; i >= 0; i--) {
  	swap(arr[0], arr[i]); //Current root moved to the end
 
  	heapify(arr, i, 0); //calling max heapify on the heap reduced
	}
  }
 
  //print size of array n using utility function
  void display(int arr[], int n) {
	for (int i = 0; i < n; ++i)
  	cout << arr[i] << " ";
	cout << "n";
  }
 
  //Driver code
  int main() {
	int arr[] = {11, 34, 9, 5, 16, 10};
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << "Original array:n";
	display(arr, n);
	heapSort(arr, n);
 
	cout << "Sorted array:n";
	display(arr, n);
  }
 
Output of the program:
 Original array:
 11 34 9 5 16 10
 Sorted array:
 5 9 10 11 16 34

Advantages of Heap Sort in Data Structure

Let’s look at some of the major advantages and disadvantages of heap sort in data structure:

Heap sort has the following advantages:

Efficiency – While other heap sort algorithms in Data Structures may become exponentially slower as the number of items to sort rises, the amount of time needed to complete a heap sort increases logarithmically. This sorting method is quite effective.
Memory Usage – Memory use is modest since it requires the minimum amount of memory needed to store the initial list of things to be sorted.
Simplicity – Since it does not employ complex computer science ideas like recursion, it is easier to comprehend than other similarly effective sorting algorithms.

Disadvantages of Heap Sort in Data Structure

There are certain disadvantages of heap sort, such as:

Costly: Heap sort is usually expensive.
Unstable: The heap sort is erratic because its relative order could change.
Efficient: Heap sort is not particularly effective when dealing with complicated data.

Applications of Heap Sort in Data Structure

The Heap Sort in Data Structure is used in the applications listed below.

Heaps are a component in priority queue creation. We can delete, insert, look for the element by prioritizing it, or extract and insert it with priority with the priority queue by taking O (log N) time. While Heap Sort in Data Structure and heap like the AVL trees, Red-Black tree, and Binary Search Tree may perform similar functions, they are more sophisticated.

An actual instance of the application of priority queues- This kind of line might be employed when clients who want quick service are given preference over those who arrive early. For instance, clients with a modest balance may be preferred in a licensing center.

The priority queues developed using heap data structure have more complex usage in graph algorithms, which can minimize the average waiting time for all clients. Dijkstra’s algorithm, Prims, Huffman coding, and BFS algorithm are a few of them.

The Heap Sort in Data Structure makes it simple and quick to determine which member in an array is the kth smallest or biggest.

Systems that deal with security and embedded systems use heap sort.

The heap sort method makes advantage of the heap data structure and is simple and effective. A reliable sorting algorithm known as the Heap Sort in Data Structure has a worst-case time complexity of O (nlogn).

Conclusion

In conclusion, a Heap Sort in Data Structure is a useful tool for organising huge datasets and a crucial technique for anybody learning about Heap Sort in Data Structure and algorithms to comprehend. The Learner Success Team at Hero Vired will ensure you get the training needed to master data science. Learn from experts who will assist you as you progress through this certification programme. Want to know about stack in data structures? Read the blog!

Author’s Note

Hero Vired is a leading learn tech firm that connects with top universities to deliver programmes relevant to the industry and develop tomorrow’s change-makers.

FAQs

Is the heap sort stable?

Since Heap Sort in Data Structure may alter the relative sequence of comparable keys, heap sort is not stable. One can represent the binary heap using array-based techniques to save space and memory.

What is heap sort's space complexity, and why?

Since no additional data structures are being used, Heap Sort in Data Structure is a built-in sorting method. Its spatial complexity is O as a result (1).

Why is Heap sort better than Selection sort?

In contrary to selection sort, the heap sort maintains the unsorted area in the heap data structure to discover the biggest element more rapidly at every step instead of wasting time using the unsorted region’s linear-time scan. Sorting an array of values that have been randomly permuted using heapsort.

What are the two phases of Heap Sort?

The Heap Sort in Data Structure is divided into two steps: The array that has to be sorted is transformed into a max heap in the first stage. The biggest element, or the one at the tree's root, is eliminated in the second stage, after which a new max heap is built from the remaining components.

How much time does it take to find the maximum and minimum element in a max heap?

When using a max heap, it will require O(1), and when using a min heap, it will need O(n).

The DevOps Playbook

Simplify deployment with Docker containers.

Streamline development with modern practices.

Enhance efficiency with automated workflows.

Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

PLACEMENT ASSISTANCE

Certificate Program in

Extended Reality (VR+AR)

Part-time · 7 Months

Apply by : 21 September, 2024

Executive Program in

Product Management

With

Part-time · 6 Months

Apply by : 21 September, 2024

3 ASSURED INTERVIEWS

Accelerator Program in

Business Analytics and Data Science

With

Part-time · 10 months

Apply by : 21 September, 2024

Upskill with expert articles

View all

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Data Science

Accelerator Program in Business Analytics & Data Science

Integrated Program in Data Science, AI and ML

Accelerator Program in AI and Machine Learning

Advanced Certification Program in Data Science & Analytics

Technology

Certificate Program in Full Stack Development with Specialization for Web and Mobile

Certificate Program in DevOps and Cloud Engineering

Certificate Program in Application Development

Certificate Program in Cybersecurity Essentials & Risk Assessment

Finance

Integrated Program in Finance and Financial Technologies