class MaxHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, k):
        self.heap.append(k)
        self.heapify_up(len(self.heap) - 1)

    def delete(self, i):
        self.heap[i] = float('inf')
        self.heapify_up(i)
        self.extract_max()

    def extract_max(self):
        if len(self.heap) == 0:
            return None
        max_value = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return max_value

    def heapify_up(self, i):
        while i != 0 and self.heap[i] > self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)

    def heapify_down(self, i):
        max_index = i
        l = self.left_child(i)
        r = self.right_child(i)
        if l < len(self.heap) and self.heap[l] > self.heap[max_index]:
            max_index = l
        if r < len(self.heap) and self.heap[r] > self.heap[max_index]:
            max_index = r
        if i != max_index:
            self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]
            self.heapify_down(max_index)

def heap_sort(arr):
    n = len(arr)
    max_heap = MaxHeap()

    # 构建堆
    for i in range(n):
        max_heap.insert(arr[i])

    # 交换元素，重建堆
    for i in range(n - 1, -1, -1):
        arr[i] = max_heap.extract_max()

    return arr

arr = [4, 10, 3, 5, 1]

sorted_arr = heap_sort(arr)

print(sorted_arr)