Сортировка кучей (heapsort)

Сортировка кучей строит из массива двоичную кучу, а затем n раз извлекает корень (минимум или максимум), помещая его в конец. Сочетает гарантированную скорость и сортировку на месте.

Сложность: время O(n log n) во всех случаях. Память: O(1) при сортировке на месте. Неустойчивая.

import heapq

def heapsort(a):
    h = list(a)
    heapq.heapify(h)            # O(n)
    return [heapq.heappop(h)    # n раз O(log n)
            for _ in range(len(h))]

print(heapsort([5, 1, 8, 3]))  # [1, 3, 5, 8]