Heapsort в Python не сортирует - PullRequest
Новая
       27

Heapsort в Python не сортирует

0 голосов
/ 06 июля 2019

Я новичок в python и пытаюсь реализовать heapsort из моей C ++ реализации . Этот код не может отсортировать ввод.

Я написал другую программу для проверки функции build_max_heap, и эта функция не может создать максимальную кучу. 

def max_heapify(thelist, lst_size, idx):
    largest = idx
    left_child = (2 * idx) + 1
    right_child = (2 * idx) + 2

    if left_child < lst_size and thelist[left_child] > thelist[largest]:
        largest = left_child

    elif right_child < len(thelist) and thelist[right_child] > thelist[largest]:
        largest = right_child

    if largest != idx:
        thelist[idx], thelist[largest] = thelist[largest], thelist[idx]
        max_heapify(thelist, lst_size, largest)

def build_max_heap(thelist, lst_size):
    for curr_idx in range(lst_size // 2 - 1, -1, -1):
        max_heapify(thelist, lst_size, curr_idx)

def heap_sort(thelist):
    if len(thelist) == 0:
        print("Empty list!!")

    elif len(thelist) == 1:
        print("Only one element!!")

    else:
        build_max_heap(thelist, len(thelist))

        for curr_idx in range(len(thelist) -1, 0, -1):
            thelist[curr_idx], thelist[0] = thelist[0], thelist[curr_idx]
            max_heapify(thelist, curr_idx, 0)

1 Ответ

1 голос
/ 06 июля 2019

В вашей функции heapify есть две ошибки:

  1. Вторая ветвь должна быть не elif, а if, так как вы захотите выбрать правого потомка, даже если левый потомок больше, чем его родитель, но когда правый потомок еще больше.

  2. Вы не хотите использовать len(thelist) там, поскольку ваша функция должна опираться на аргумент lst_size. Это необходимо, потому что в heap_sort выполняются вызовы функций, передающие значение для этого аргумента, которое (и должно быть) меньше, чем фактическая длина списка.

Итак, измените: 

elif right_child < len(thelist) and thelist[right_child] > thelist[largest]:

до: 

if right_child < lst_size and thelist[right_child] > thelist[largest]:
...