基于数组的 MinHeap
Array based MinHeap
我正在尝试实现一个将列表转换为 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]
我认为你应该交换 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]
我正在尝试实现一个将列表转换为 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]
我认为你应该交换 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]