Почему мой код для Heapsort ведет себя так? - PullRequest
Новая
       53

Почему мой код для Heapsort ведет себя так?

0 голосов
/ 24 марта 2020 
class MaxHeap(object):
    def __init__(self, list1):
        self.heap_list = list1
        self.heap_size = len(list1) - 1
    def MaxHeapify(self, index):
        largest_index = index
        left_child = 2 * largest_index
        right_child = 2 * largest_index + 1
        print('before left child', largest_index)
        if left_child <= self.heap_size and self.heap_list[left_child] > self.heap_list[largest_index]:
            print('left child loop')
            largest_index = left_child
        print('before right child', largest_index)
        if right_child <= self.heap_size and self.heap_list[right_child] > self.heap_list[largest_index]:
            print('right child loop')
            largest_index = right_child
        print('after left and right child', largest_index)
        if largest_index != index:
            print('exchange loop')
            self.heap_list[largest_index], self.heap_list[index] = self.heap_list[index], self.heap_list[largest_index]
            print(self.heap_list)
            self.MaxHeapify(largest_index)

    def BuildMaxHeap(self):
        startIdx = self.heap_size // 2
        for i in range(startIdx, 0, -1):
            self.MaxHeapify(i)

    def ret_heap(self):
        return self.heap_list
def fn():
    list1 = [0,7,9,8]
    print('Output 1: ')
    h1 = MaxHeap(list1)
    h1.BuildMaxHeap()
    print(h1.ret_heap())

    list2 = [0,7,8,9]
    print('Output 2: ')
    h2 = MaxHeap(list2)
    h2.BuildMaxHeap()
    print(h2.ret_heap())

fn()

У меня есть два списка ввода: 

list1 = [0,7,9,8]
list2 = [0,7,8,9]

Вывод выглядит так с отладочными операторами печати: 

Output 1: 
before left child 1
left child loop
before right child 2
after left and right child 2
exchange loop
[0, 9, 7, 8]
before left child 2
before right child 2
after left and right child 2
[0, 9, 7, 8]
Output 2: 
before left child 1
left child loop
before right child 2
right child loop
after left and right child 3
exchange loop
[0, 9, 8, 7]
before left child 3
before right child 3
after left and right child 3
[0, 9, 8, 7]

Мой вопрос, когда я вызываю экземпляр BuildMaxHeap для list1 (h1), код никогда не вводит правильный дочерний оператор if в MaxHeapify (как видно из вывода, он никогда не печатает правильный дочерний элемент l oop), тогда как когда я запускаю код для list2, это происходит. Почему он не входит во второе оператор if, хотя все его условия выполнены?

...