MinHeap на основе массива - PullRequest
Новая
       58

MinHeap на основе массива

0 голосов
/ 08 мая 2018

Я пытаюсь реализовать функцию, которая превращает список в MinHeap. Я не вижу, где я иду не так. 

def min_heapify(nums):
    n = len(nums) - 1
    i = n // 2  # last parent

    while i >= 1:
        k = i
        v = nums[k]
        min_heap = False
        while not min_heap and 2 * k <= n:
            j = 2 * k
            if j + 1 <= n:
                if nums[j + 1] < nums[j]:
                    j += 1
            if nums[k] < nums[j]:
                min_heap = True
            else:
                nums[k] = nums[j]
                k = j
        nums[k] = v
        i -= 1

Пример ввода: 

a_list = [0, 5, 2, 3, 4]
min_heapify(a_list)

Вывод (4 неверно): 

print("Min Heapify", a_list)  # Min Heapify [0, 2, 5, 3, 4]

1 Ответ

0 голосов
/ 09 мая 2018

Я думаю, вы должны поменять местами num[j] и num[k], где вы просто назначаете nums[k] = nums[j]: 

def min_heapify(nums):
    n = len(nums) - 1
    i = n // 2  # last parent

    while i >= 1:
        k = i
        v = nums[k]
        min_heap = False
        while not min_heap and 2 * k <= n:
            j = 2 * k
            if j + 1 <= n:
                if nums[j + 1] < nums[j]:
                    j += 1
            if nums[k] < nums[j]:
                min_heap = True
            else:
                # HERE: Need to swap num[j] and num[k]
                [nums[j], nums[k]] = [nums[k], nums[j]]
                k = j
        nums[k] = v
        i -= 1

a_list = [0, 11, 5, 2, 3, 4, 7, 17, 6, 1]
min_heapify(a_list)
print(a_list)

# prints: [0, 1, 3, 2, 5, 4, 7, 17, 6, 11]
...