Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region.

Algorithm Overview

Heap sort leverages the properties of a binary heap to efficiently sort data.

Key Features

• Heap-Based: Uses binary heap data structure
• Not Stable: Does not preserve relative order of equal elements
• Guaranteed Performance: Always O(n log n) regardless of input
• Multiple Implementations: Both heap-class and in-place versions
• Customizable: Supports custom key functions and reverse sorting

Time and Space Complexity

• Time Complexity: O(n log n) in all cases
• Space Complexity:
• O(n) for heap-based implementation (creates separate heap)
• O(1) for in-place implementation
• Build Heap: O(n) time
• Extract Operations: n × O(log n) = O(n log n) time

Usage Examples

Basic Usage

from algo.algorithms.sorting.heap_sort import heap_sort

# Sort integers
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = heap_sort(numbers)
print(sorted_numbers)  # [11, 12, 22, 25, 34, 64, 90]

# Sort strings
words = ['banana', 'apple', 'cherry']
sorted_words = heap_sort(words)
print(sorted_words)  # ['apple', 'banana', 'cherry']

In-Place Sorting

from algo.algorithms.sorting.heap_sort import heap_sort_in_place

# Modify original array
arr = [3, 1, 4, 1, 5]
heap_sort_in_place(arr)
print(arr)  # [1, 1, 3, 4, 5]

Reverse Sorting

# Sort in descending order
numbers = [3, 1, 4, 1, 5]
descending = heap_sort(numbers, reverse=True)
print(descending)  # [5, 4, 3, 1, 1]

Custom Key Function

# Sort by string length
words = ['apple', 'pie', 'banana', 'a']
by_length = heap_sort(words, key=len)
print(by_length)  # ['a', 'pie', 'apple', 'banana']

Heap Property Validation

from algo.algorithms.sorting.heap_sort import is_heap

# Check if array satisfies heap property
arr = [9, 5, 6, 2, 3, 7, 1, 4]
print(is_heap(arr, is_min_heap=False))  # Check if max heap

def heap_sort_in_place(arr, reverse=False, key=None):
    # Build heap
    for i in range(len(arr) // 2 - 1, -1, -1):
        heapify_down(arr, len(arr), i)

    # Extract elements
    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify_down(arr, i, 0)

Edge Cases Handled

# Empty array
result = heap_sort([])  # Returns []

# Single element
result = heap_sort([42])  # Returns [42]

# All same elements
result = heap_sort([5, 5, 5, 5])  # Returns [5, 5, 5, 5]

# Large arrays (predictable performance)
large_array = list(range(1000, 0, -1))
result = heap_sort(large_array)  # Completes in O(n log n)

API Reference

Heap Sort Implementation

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region.

Key Features:

• In-place sorting algorithm
• Not stable (does not preserve relative order of equal elements)
• Guaranteed O(n log n) time complexity
• Uses binary heap data structure

Algorithm Steps:

1. Build a max heap from the input array
2. Repeatedly extract the maximum element and place it at the end
3. Reduce heap size and restore heap property

Time Complexity: O(n log n) - consistent across all cases

Space Complexity: O(1) - sorts in place

Stability: Not stable

heap_sort(arr, reverse=False, key=None)

Sort an array using heap sort algorithm.

Parameters:

Name	Type	Description	Default
arr	List[T]	List to be sorted	required
reverse	bool	If True, sort in descending order	False
key	Optional[Callable[[T], any]]	Optional function to extract comparison key from elements	None

Returns:

Type	Description
List[T]	New sorted list

Time Complexity: O(n log n) Space Complexity: O(n) due to creating new heap and result list

heap_sort_in_place(arr, reverse=False, key=None)

Sort an array in place using heap sort algorithm.

This is a more traditional heap sort implementation that sorts in place by manually implementing the heap operations on the array itself.

Parameters:

Name	Type	Description	Default
arr	List[T]	List to be sorted in place	required
reverse	bool	If True, sort in descending order	False
key	Optional[Callable[[T], any]]	Optional function to extract comparison key from elements	None

Time Complexity: O(n log n) Space Complexity: O(1) - truly in-place

is_heap(arr, is_min_heap=True, key=None)

Check if an array satisfies the heap property.

Parameters:

Name	Type	Description	Default
arr	List[T]	Array to check	required
is_min_heap	bool	True to check min heap property, False for max heap	True
key	Optional[Callable[[T], any]]	Optional function to extract comparison key from elements	None

Returns:

Type	Description
bool	True if array satisfies heap property, False otherwise