heap sort

Heap Sort

Generate Random Numbers

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Heap Sort Overview

History

Heap sort is based on the binary heap data structure and was developed in the 1960s. It is considered an efficient sorting algorithm and is often used in systems that require high performance.

Current Uses

  • Data Processing: Used in systems that require efficient sorting and management of data.
  • Priority Queues: Often employed in implementing priority queues due to its underlying heap structure.
  • Embedded Systems: Suitable for environments with limited memory resources.

Time and Space Complexity

Time Complexity

  • Best Case: O(n log n) – Performance is consistent regardless of input.
  • Average Case: O(n log n) – Efficient average performance.
  • Worst Case: O(n log n) – Consistent performance even in the worst case.

Space Complexity

Space Complexity: O(1) – It is an in-place sorting algorithm that requires minimal additional space.

Pseudo Code

function heapSort(arr):
    n = length(arr)
    // Build heap (rearrange array)
    for i from n/2 - 1 to 0:
        heapify(arr, n, i)
    // One by one extract elements from heap
    for i from n-1 to 0:
        swap arr[0] and arr[i]
        heapify(arr, i, 0)

function heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        swap arr[i] and arr[largest]
        heapify(arr, n, largest)

Key Characteristics

  • In-Place: Heap sort operates in place, requiring minimal additional memory.
  • Not Stable: The algorithm is not stable, as equal elements may change order.

Summary

Heap sort is a comparison-based sorting algorithm that utilizes the properties of a binary heap. With a time complexity of O(n log n), it is efficient and suitable for applications requiring guaranteed performance.

Heap Sort Code Implementation