from typing import List
def heap_up(array: List[int], idx: int) -> List[int]:
"""Bubble up the element at idx until it is in the correct position.
Args:
array (List[int]): The array to heapify.
idx (int): The index of the element to heapify.
Returns:
List[int]: The array with the element at idx heapified.
"""
left = 2 * idx + 1 if 2 * idx + 1 < len(array) else None
right = 2 * idx + 2 if 2 * idx + 2 < len(array) else None
largest = idx
if not left:
return array
if array[idx] < array[left]:
largest = left
if right and array[largest] < array[right]:
largest = right
if largest != idx:
array[idx], array[largest] = array[largest], array[idx]
array = heap_up(array, largest)
return array
def heapify(array: List[int]) -> List[int]:
"""Return a heapified version of the array.
Args:
array (List[int]): The array to heapify.
Returns:
List[int]: The heapified array.
"""
for i in range(len(array) // 2 - 1, -1, -1):
array = heap_up(array, i)
return array
def heap_sort(array: List[int]) -> List[int]:
"""Return a sorted version of the array using heap.
Args:
array (List[int]): The array to sort.
Returns:
List[int]: The sorted array.
"""
array = heapify(array)
for i in range(len(array) - 1, 0, -1):
array[0], array[i] = array[i], array[0]
array = heapify(array[:i]) + array[i:]
return array
