сортировка кучи и обратная сортировка с кучей макс / мин - PullRequest
Новая
       75

сортировка кучи и обратная сортировка с кучей макс / мин

1 голос
/ 16 марта 2020

Я просто хочу проверить, понял ли я, что сказал профессор и онлайн-ресурсы.

Для алгоритма heapSort индекс первого элемента начинается с 0.

Для максимальной кучи , percolate down должен поменять максимальный дочерний элемент с его родителем, если дочерний элемент больше родительского, поэтому что-то вроде (это для назначения, поэтому я попытался разместить как можно меньше кода): 

def percolateDownMaxHeap( array, hole, length):
    while hole * 2 < size - 1:
        left = 2*hole + 1
        right = left + 1

        max = left

        if (left < size - 1) and (array[right] > array[left]):
            max = right

        if (array[max] > array[hole]):
            swap(array, hole, max)

        else:
            break

        hole = max

Таким образом, в конце, максимальный элемент должен быть с индексом 0.

Если это правильно, то я не понимаю, что такое реализация heapSort: 

def heapSort(array):
    i = len(array) / 2
    while i >= 0:
        percolateDownMaxHeap( array, i, len(array))
        i -= 1

    i = len(array) - 1

    while i > 0:
        swap( array, 0, i );
        percolateDownMaxHeap( array, i, len(array))
        i -= 1

Не просачивается вниз в максимальную кучу должен положить самый большой элемент с индексом 0? В этом случае, почему бы не использовать перколят на кучу мин? Код работает, но я не уверен, правильно ли я понял или я реализовал максимальную кучу вместо минимальной кучи

Спасибо

1 Ответ

2 голосов
/ 16 марта 2020

Разве не происходит перенаправление в максимальную кучу, которая должна помещать самый большой элемент в индекс 0?

Это так. Затем ваш код обменивает его за пределы кучи, поэтому каждый последующий обмен помещает следующий по величине элемент, которому он принадлежит.

В этом случае, почему бы не использовать percolate вниз на кучи min?

Это приведет к тому, что элемент min окажется в правильном положении, но куча все еще нуждается в этом положении в массиве, поэтому неясно, что делать со следующим элементом.

...