Как разделить кучу на две подкучи с помощью heapify для heapsort?

я пытаюсь создать функцию HeapSort в python, используя некоторые вспомогательные функции.

Я пытаюсь следовать инструкциям своей книги и использую некоторые функции, такие как fixHeap, которые восстанавливают правильный порядок в куче с узлом, не следующим правилам:

def getMaxKnot(i,j,A):
    k = max(A[i],A[j])
    if k==A[i]:
        return i
    if k==A[j]:
        return j


def fixheap(v,H): #basically restore an heap with a node not following heap rules
    if (2*v+1)>len(H)-1:
        return H
    else:
        u=getMaxKnot(2*v+1,2*v+2,H)
        if H[u]>H[v]:
            listoperations.swap(u,v,H) #swap item in position u and v
        return fixheap(u,H)

Теперь я хочу в основном создать функцию heapify, которая рекурсивно работает с левым и правым деревьями, используя мою функцию fixheap для восстановления правильного порядка.

Моя идея заключалась в следующем:

def heapify(A):
        if A==[]:
            return A
        else:
            heapify(LEFT TREE)
            heapify(RIGHT TREE)
            fixheap(0,A)

Любые идеи о том, как разделить мой массив A на ЛЕВОЕ ДЕРЕВО и ПРАВОЕ ДЕРЕВО?


python recursion heapsort divide
person sixpain    schedule 03.11.2017    source источник
comment
Что такое «вспомогательная функция»?   -  person huck_cussler    schedule 03.11.2017
comment
Вся версия heapify, которую я вижу в Интернете, была основана на одной функции, которая преобразует массив в кучу. Итак, я назвал вспомогательную функцию fixHeap, но в основном это простая функция определения   -  person sixpain    schedule 03.11.2017
comment
Вспомогательный, извините   -  person sixpain    schedule 03.11.2017

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, в fixheap чего-то не хватает. Представьте, что узел v имеет только один (левый) дочерний узел, тогда getMaxKnot вызовет ошибку недопустимого индекса, поскольку j будет указывать за конец массива A.

Лично я не думаю, что getMaxKnot заслуживает отдельной функции. Я бы также расположил аргументы fixheap в обратном порядке, чтобы второй можно было легко опустить и дать ему значение по умолчанию (когда это корневой элемент). Также замена двух значений действительно однострочная:

def fixheap(H, v = 0): # put arguments in this order
    u = 2*v + 1
    if u >= len(H):
        return H
    if u+1 < len(H) and H[u+1] > H[u]: # Only compare when there are two child nodes
        u += 1
    if H[u] > H[v]:
        [H[u], H[v]] = [H[v], H[u]] # Swapping is easy
        return fixheap(H, u)

Затем к вашему основному вопросу: ваш heapify также должен получить узел в качестве аргумента, который будет корнем поддерева, которое вы хотите увеличить. Принцип на самом деле не сильно отличается от того, как используется функция fixheap:

def heapify(H, v = 0):
    u = 2*v + 1
    if u >= len(H):
        return H
    heapify(H, u)
    if u + 1 < len(H): # make sure there is a right child
        heapify(H, u+1)
    fixheap(H, v)
person trincot    schedule 03.11.2017
comment
Наконец я решил это на себе. В основном одна ошибка заключается в том, что я думал о том, как разделить левое дерево и правое дерево, например, разделить мою кучу на 2-подсписок. Вместо этого было просто необходимо вызвать heapify для правого сына и левого сына, используя рекурсию. Моя вторая ошибка заключалась в том, что в heapify, следуя вашему совету, чтобы улучшить его, я забыл вставить условие сделать обмен только в том случае, если Parent больше, чем Son. Спасибо! - person sixpain; 04.11.2017