\
home Home
sort Sorts
Bubble Sort Selection Sort Insertion Sort Merge Sort Quick Sort Randomized Quick Counting Sort Gnome Sort Stooge Sort
SORTING VISUALIZER - Heap SORT

  HeapSort(A)

    1.   BuildMaxHeap(A)

       1.   for i = length(A)/2 to 1

       2.     Heapify(A, i)

    2.   for i = n to 1

    3.     Swap A[0] <-> A[i]

    4.     n = n - 1

    5.     Heapify(A, i)

        1.   largest = i

        2.   l = 2*i + 1

        3.   r = 2*i + 2

        4.   if l < n and A[l] > A[largest]

        5.   largest = l

        6.   if r < n & A[r] > A[largest]

        7.   largest = r

        8.   if largest != i

        9.   Swap A[i] <-> A[largest]

        10.  Heapify(A, largest)

    6.   End If

No of Comparisons:

   
         

Complexity

Time
 Space
Best Case Average Case Worst Case
O(1)
O(n)
O(nlog(n))
O(nlog(n))

Heap Sort

What is the working mechanism of Heap Sort?

Heap sort is a sorting algorithm that works by transforming an unsorted array into a binary heap data structure, and then extracting the maximum element of the heap repeatedly until the array is sorted.


Is Heap sort a stable, in-place sorting algorithm or an out-of-placesorting algorithm?

Heap sort is an unstable in-place algorithm, meaning that it does not require any extra space but can't maintains the relative order of duplicates.


How does the number of elements impact the efficiency of Heap sort?

The time taken by heap sort increases as the number of elements in the array increases. The time complexity of heap sort is O(n log n), which means that the time taken by the algorithm increases logarithmically with the number of elements. Also, the efficiency of heap sort may also depend on the initial state of the array. If the array is already partially sorted, the heap sort algorithm may require fewer comparisons to sort the array.


What are advantages and disadvantages of Heap Sort?

Advantages:

  • Easy to understand because it does not use advanced computer science concepts such as recursion.
  • It does not require any additional memory space.
  • The time required to perform Heap sort increases logarithmically as the number of items to sort increases. Making it very efficient.

Disadvantages:
  • Heap sort is unstable. It might rearrange the relative order.
  • Heap Sort are not very efficient when working with complex data.