heapSort<T>

A generic implementation of the Heap Sort algorithm that can sort any list of comparable elements.

Function Signature

List<T> heapSort<T extends Comparable<T>>(List<T> list)

Parameters

• list: A list of elements of type T that implements the Comparable interface

Return Value

• Returns the sorted list of type List<T>

Type Parameters

• T extends Comparable<T>: The type parameter T must implement the Comparable interface to ensure elements can be compared

Complexity Analysis

Time Complexity

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)

Space Complexity

• O(1) - Only requires a constant amount of additional memory space

Implementation

List<T> heapSort<T extends Comparable<T>>(List<T> list) {
  final result = List<T>.from(list);
  int n = result.length;

  // Build heap (rearrange array)
  for (int i = n ~/ 2 - 1; i >= 0; i--) {
    _heapify(result, n, i);
  }

  // One by one extract an element from heap
  for (int i = n - 1; i > 0; i--) {
    // Move current root to end
    var temp = result[0];
    result[0] = result[i];
    result[i] = temp;

    // call max heapify on the reduced heap
    _heapify(result, i, 0);
  }

  return result;
}

void _heapify<T extends Comparable<T>>(List<T> arr, int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left].compareTo(arr[largest]) > 0) {
    largest = left;
  }

  if (right < n && arr[right].compareTo(arr[largest]) > 0) {
    largest = right;
  }

  if (largest != i) {
    var swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;

    _heapify(arr, n, largest);
  }
}

Implementation Details

1. Function Declaration:

   • The function is generic, accepting any type T that implements Comparable<T>
   • Takes a single parameter list of type List<T>
   • Returns a sorted list of the same type

2. Algorithm Steps:

   • Creates a copy of the input list to preserve the original
   • Builds a max heap from the array
   • Repeatedly extracts the maximum element and places it at the end
   • Maintains the heap property by calling _heapify
   • Returns the sorted array

3. Helper Function:

   • _heapify maintains the max heap property
   • Compares parent with children and swaps if necessary
   • Recursively maintains heap property

Example Usage

void main() {
  // Sorting integers
  var numbers = [64, 34, 25, 12, 22, 11, 90];
  print('Original list: $numbers');
  var sortedNumbers = heapSort(numbers);
  print('Sorted list: $sortedNumbers');

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = heapSort(fruits);
  print('Sorted list: $sortedFruits');
}

Output

Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]

Original list: [banana, apple, orange, grape]
Sorted list: [apple, banana, grape, orange]

Usage Notes

1. Type Constraints:

   • The type T must implement Comparable<T>
   • Built-in types like int, double, and String already implement Comparable
   • Custom classes must implement Comparable interface to be sorted

2. Performance Considerations:

   • Efficient for large datasets with O(n log n) complexity
   • In-place sorting algorithm
   • Good for sorting large datasets

3. Stability:

   • Not stable - may change the relative order of equal elements
   • Consider using stable sorting algorithms if order preservation is important