Как реализовать max_heapify в структуре данных кучи в Python

Question

Ниже приведен класс кучи.Я пытаюсь отсортировать кучу, но у меня проблема с моей max_heapify функцией.Я вставил значения [10, 9, 7, 6, 5, 4, 3], и моя сортировка кучи печатает заданный вывод.Заданный вывод и ожидаемый вывод дан ниже класса

класс кучи

class Heap(object):
    def __init__(self):
        self.A = []

    def insert(self, x):
        self.A.append(x)

    def Max(self):
        """
        returns the largest value in an array
        """
        return max(self.A)

    def extractMax(self):
        """
        returns and remove the largest value from an array
        """
        x = max(self.A)
        self.A.remove(x)
        self.max_heapify(0)
        return x;

    def parent(self, i):
        """
        returns the parent index
        """
        i+=1
        i = int(i/2)
        return i

    def left(self, i):
        """
        returns the index of left child
        """
        i = i+1
        i = 2*i
        return i

    def right(self, i):
        """
         returns the index of right child
        """
        i+=1;
        i = 2*i + 1
        return i

    def heap_size(self):
        """
         returns the size of heap
        """

        return len(self.A)

    def max_heapify(self, i):
        """
        heapify the array 
        """
        l = self.left(i)
        r = self.right(i)

        if(l < self.heap_size() and self.A[l] > self.A[i]):
            largest = l
        else:
            largest = i

        if(r < self.heap_size() and self.A[r] > self.A[largest]):
            largest = r


        if largest != i:

            temp = self.A[i]
            self.A[i] = self.A[largest]
            self.A[largest] = temp

            self.max_heapify(largest)


    def build_max_heap(self):

           n = len(self.A)
           n = int(n/2)
           for i in range(n, -1, -1):
               self.max_heapify(i)


    def heap_sort(self):
        """
         sorts the heap
        """

        while self.heap_size() > 0:

                self.build_max_heap()
                temp = self.A[0]
                n = len(self.A) - 1
                self.A[0] = self.A[n]
                self.A[n] = temp
                x = self.A.pop()
                print(x)
                self.max_heapify(0)




h = Heap()
h.insert(10)
h.insert(9)
h.insert(7)
h.insert(6)
h.insert(5)
h.insert(4)
h.insert(3)
h.heap_sort()    

заданный вывод

10
7
6
5
4
3
9

ожидаемый вывод

10
9
7
6
5
4
3

Answer 1

Похоже, вы пытаетесь построить максимальную кучу с корнем в A[0].Если это так, то ваши вычисления индекса left, right и parent неверны.У вас есть:

def parent(self, i):
    """
    returns the parent index
    """
    i+=1
    i = int(i/2)
    return i

def left(self, i):
    """
    returns the index of left child
    """
    i = i+1
    i = 2*i
    return i

def right(self, i):
    """
     returns the index of right child
    """
    i+=1;
    i = 2*i + 1
    return i

Так что если i=0, левый ребенок будет 2, а правый ребенок будет 3. Хуже, если i=3, parent вернется 2. Таким образом, у вас естьслучай, когда parent(right(i)) != i.Это никогда не сработает.

Правильные расчеты:

left = (2*i)+1
right = (2*i)+2
parent = (i-1)/2

Я не знаю, почему ваш extractMax звонит max(self.A).Вы уже знаете, что максимальный элемент в A[0].Чтобы извлечь максимальный элемент, все, что вам нужно сделать, это:

returnValue = save value at self.A[0]
take last item in the array and place at self.A[0]
decrease length of array
maxHeapify(0)

Я использовал псевдокод, потому что мне не очень удобно с Python.

Цикл внутри вашего *Метод 1025 * серьезно неоптимальный.Вы звоните self.build_max_heap на каждой итерации.Вам не нужно это делать.Если extractMax работает правильно, все, что вам нужно сделать, это:

while self.heap_size() > 0:
    temp = self.extractMax()
    print temp

Теперь, если вы хотите отсортировать массив на месте, так что сам self.A будет отсортирован, это немного большесложно.Но, похоже, это не то, что вы пытаетесь сделать.