Кодирование heapsort для python 3

def heapSort(lst):

    heap = arrayHeap.mkHeap(len(lst), arrayHeap.less)
    alst = list(lst)
    while alst != []:
        v = alst.pop(0)
        arrayHeap.add (heap, v)

    while heap.size != 0:
        w = arrayHeap.removeMin(heap)
        alst.append(w)
    return last

это действительная функция сортировки кучи?

1 ответ

Решение

Предполагая ваш arrayHeap предоставляет те же гарантии, что и stdlib heapq или любая другая разумная реализация кучи, тогда это допустимая сортировка кучи, но это очень глупо.

Скопировав исходную последовательность в список, а затем щелкнув с левой стороны, вы делаете O(N^2) подготовку к вашей сортировке O(N log N).

Если вы измените это на всплывающее с правой стороны, то вы только делаете подготовку O(N), поэтому все это занимает O(N log N), как это должно быть в heapsort.

При этом я не могу понять, почему вы хотите выскочить из списка, а не просто перебирать его. Или, если на то пошло, почему вы хотите скопировать оригинальную последовательность в список, а не просто перебирать ее напрямую. Если вы сделаете это, это будет быстрее, и будет использовать только половину памяти, и будет намного проще кода. Как это:

def heapSort(lst):
    heap = arrayHeap.mkHeap(len(lst), arrayHeap.less)
    for v in lst:
        arrayHeap.add(heap, v)
    alst = []
    while heap.size:
        w = arrayHeap.removeMin(heap)
        alst.append(w)
    return last

С немного более приятным API, как в stdlib heapq модуль (кстати, почему вы его не используете?), вы можете сделать это еще проще:

def heapSort(lst):
    alst = []
    for v in lst:
        heapq.heappush(alst, v)
    return [heapq.heappop(alst) for i in range(len(alst))]

... или, если вы уверены lst это список, и вы не против его поменять:

def heapSort(lst):
    heapq.heapify(lst)
    return [heapq.heappop(lst) for i in range(len(lst))]

... или, конечно, вы можете скопировать lst и затем измените копию:

def heapSort(lst):
    alst = lst[:]
    heapq.heapify(alst)
    return [heapq.heappop(alst) for i in range(len(alst))]

Вы можете заметить, что первый из них является первым из основных примеров в heapq Docs.

Другие вопросы по тегам