How much extra space is used by heapsort?

How much extra space is used by heapsort?

• (A) O (1)
• (B) O(n)
• (C) O (Log n)
• (D) O (n²)


Heapsort is a comparison-based sorting algorithm that allows you to sort a list of elements in ascending or descending order. It is efficient, but not as efficient as some other sorting algorithms, such as quicksort. Here is how it works:

  1. Create a heap from the list of elements. A heap is a complete binary tree (that is, a binary tree in which every level is fully filled except possibly the last level and the last level has all keys as left as possible) with the property that the key at the root of the tree is greater than or equal to the keys of its children. There are two types of heaps: max-heaps and min-heaps. In a max-heap, the root node has the maximum key and in a min-heap, the root node has the minimum key.

  2. Repeatedly remove the root element (which is the maximum or minimum element in the heap) and insert it into a sorted list.

  3. After all the elements have been removed from the heap and inserted into the sorted list, the list will be sorted in ascending or descending order, depending on whether you are using a max-heap or a min-heap.

Heapsort has a time complexity of O(n log n) in the average and worst case and Only O(1) additional space is required. It is not a stable sort, which means that the relative order of elements with equal keys may be different after the sort.

Only O(1) additional space is required

Leave a Comment

Your email address will not be published. Required fields are marked *

PYQ of History UGC NET UGC NET Mathematical Reasoning and Aptitude ICT (Digital Initiatives) | UGC NET | paper – 1 The Scope of Information and Communication Technology(ICT) PYQ of People, Development, and Environment Top 30 PYQ of HINDI | UGC NET – 2023 Top 30 PYQ of Teaching Aptitude PYQ of Research Aptitude | NTA UGC NET | Paper 1 | Part 1 UGC NET Paper 1 Syllabus | Updated | 2023 Types of Research | Research Aptitude | nta ugc net | UGC NET 2023