最小堆插入功能无法正常工作
Min-heap insert function doesn't work properly
任何人都可以帮助我实现插入功能吗？不知道为什么没有正确插入数据
在测试文件中，期望的数组是：[None,-12,-11,-6,-9, -3, -5, -2, -1, -4]
但是函数returns: [None, -12, -9, -6, -11, -3, -5, -2, -1, -4]
from functools import total_ordering
import math
class MinHeap:
def __init__(self):
self.arr_heap = [None]
def __str__(self):
return str(self.arr_heap[1:])
def __repr__(self):
return str(self)
def get_left_pos(self, i:int) ->int:
return 2*i
def get_right_pos(self, i:int) ->int:
return 2*i+1
def get_parent_pos(self, i) ->int:
return math.floor(i/2)
def swap(self, pos_1, pos_2):
aux = self.arr_heap[pos_1]
self.arr_heap[pos_1] = self.arr_heap[pos_2]
self.arr_heap[pos_2] = aux
def is_a_leaf(self, posicao):
return posicao >= len(self.arr_heap)//2 and posicao <= len(self.arr_heap)
def heapify(self, pos_raiz_sub_arvore:int):
parent_pos = pos_raiz_sub_arvore
left_child_pos = self.get_left_pos(parent_pos)
right_child_pos = self.get_right_pos(parent_pos)
if not self.is_a_leaf(parent_pos):
if (self.arr_heap[parent_pos] > self.arr_heap[left_child_pos] or self.arr_heap[parent_pos] > self.arr_heap[right_child_pos]):
if self.arr_heap[left_child_pos] < self.arr_heap[right_child_pos]:
self.swap(parent_pos, left_child_pos)
self.heapify(left_child_pos)
else:
self.swap(parent_pos, right_child_pos)
self.heapify(right_child_pos)
def insert(self, element):
self.arr_heap.append(element)
current = self.arr_heap.index(element)
while self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)-1]:
self.swap(current, self.get_parent_pos(current))
current = self.get_parent_pos(current)
def remove(self):
element = self.arr_heap[1]
element_pos = len(self.arr_heap)-1
self.arr_heap[1] = self.arr_heap[element_pos]
self.arr_heap.pop(element_pos)
self.heapify(1)
return element
def __str__(self):
return str(self.arr_heap)
def __repr__(self):
return str(self)
测试文件为：
import unittest
from typing import List, Dict
from heap import MinHeap
class TestHeap(unittest.TestCase):
def test_heapify(self):
obj_heap = MinHeap()
obj_heap.arr_heap = [None,-12,-9,-6]
obj_heap.heapify(1)
self.assertListEqual(obj_heap.arr_heap, [None,-12,-9,-6], f"The heapify operation was not performed correctly. Input list: {[None,-12,-9,-6]}")
obj_heap.arr_heap = [None,-12,-15,-6]
obj_heap.heapify(1)
self.assertListEqual(obj_heap.arr_heap, [None,-15,-12,-6], f"The heapify operation was not performed correctly. Input list: {[None,-12,-15,-6]}")
obj_heap.arr_heap = [None,-12,-9,-15]
obj_heap.heapify(1)
self.assertListEqual(obj_heap.arr_heap, [None,-15,-9,-12], f"The heapify operation was not performed correctly. Input list: {[None,-12,-9,-15]}")
obj_heap.arr_heap = [None,-12,-2,-6,-4,-5,3,0,-1,1, -3, 2]
obj_heap.heapify(2)
self.assertListEqual(obj_heap.arr_heap, [None,-12,-5,-6,-4,-3,3,0,-1,1, -2, 2], f"The heapify operation was not performed correctly. Expected outcome: {[None,-12,-5,-6,-4,-3,3,0,-1,1, -2, 2]} result obtained: {obj_heap.arr_heap}. Input list: {[None,-12,-2,-6,-4,-5,3,0,-1,1, -3, 2]}")
obj_heap.arr_heap = [None,-12,-2,-4,-6,-5,3,0,1,-3, -3, 2]
obj_heap.heapify(2)
self.assertListEqual(obj_heap.arr_heap, [None,-12,-6,-4,-3,-5,3,0,1,-2, -3, 2], f"The heapify operation was not performed correctly. Expected outcome: {[None,-12,-6,-4,-3,-5,3,0,1,-2, -3, 2]} result obtained: {obj_heap.arr_heap}. Input list: {[None,-12,-2,-4,-6,-5,3,0,1,-3, -3, 2]}")
def test_insert(self):
arr_test = [1,-8,-11,-14]
arr_heap_expected = [[None,-12,-9,-6,-4,-3,-5,-2,-1,1],
[None,-12,-9,-6,-8,-3,-5,-2,-1,-4],
[None,-12,-11,-6,-9,-3,-5,-2,-1,-4],
[None,-14,-12,-6,-9,-3,-5,-2,-1,-4],
]
for val_inserir in arr_test:
objHeap = MinHeap()
objHeap.insert(val_inserir)
self.assertListEqual([None,val_inserir],objHeap.arr_heap,f"Incorrect insertion when inserting the value {val_inserir} in the heap {[None,-12,-9,-6,-4,-3,-5,-2,-1]}, expected: {[None,val_inserir]} result: {objHeap.arr_heap}")
for i,val_inserir in enumerate(arr_test):
objHeap = MinHeap()
objHeap.arr_heap = [None,-12,-9,-6,-4,-3,-5,-2,-1]
objHeap.insert(val_inserir)
self.assertListEqual(arr_heap_expected[i],objHeap.arr_heap,f"Incorrect insertion when inserting the value {val_inserir} in the heap {[None,-12,-9,-6,-4,-3,-5,-2,-1]}, expected: {arr_heap_expected[i]} result: {objHeap.arr_heap}")
def test_remove(self):
obj_heap = MinHeap()
obj_heap.arr_heap = [None,-12,-9,-4,-7,-5,3,0,1,-2, -3, 2]
min_val = obj_heap.remove()
self.assertEqual(min_val, -12, f"Incorrect insertion when inserting the value (-12) but {min_val} ")
self.assertListEqual(obj_heap.arr_heap, [None,-9,-7,-4,-2,-5,3,0,1,2, -3], f"The test_remove operation did not end with the expected heap.")
obj_heap.arr_heap = [None,-12]
min_val = obj_heap.remove()
self.assertEqual(min_val, -12, f"Incorrect insertion when inserting the value (-12) but {min_val} ")
self.assertListEqual(obj_heap.arr_heap, [None], f"The test_remove operation did not end with the expected heap.")
if __name__ == "__main__":
unittest.main()
所有其他测试工作正常。
我了解了 MinHeaps，所以我可以用你的代码解决问题（是的......我没有生命 ;)）。有两个问题，它们在同一条线上。该行是 insert 方法中的这一行：
while self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)-1]:
第一个问题是-1。您想要将父元素的值与当前元素的值进行比较。父元素位于 self.get_parent_pos(current)。我不知道您为什么认为要查看之前的元素。你不知道。所以在这一行中，你的第三个插入测试成功了，但是你的第四个测试失败了：
while self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)]:
第四次测试失败的原因是新元素到达树的顶部并且您的算法继续运行。由于该元素现在没有父元素，因此代码在尝试获取父元素的值时会崩溃。答案是识别新元素何时到达树的顶部，然后停止。为此，您将行修改为：
while current > 0 and self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)]:
使用该版本的行，您的所有插入测试都通过了。
给你一个小花絮。你的方法：
def get_parent_pos(self, i) ->int:
return math.floor(i/2)
可以更简洁地写成：
def get_parent_pos(self, i) ->int:
return i // 2
/ 生成浮点数结果，而 '//' 通过向下舍入生成整数结果。请记住这一点，因为您经常想要进行整数除法，而“//”是一种更简洁、更简单的方法。
任何人都可以帮助我实现插入功能吗？不知道为什么没有正确插入数据
在测试文件中，期望的数组是：[None,-12,-11,-6,-9, -3, -5, -2, -1, -4]
但是函数returns: [None, -12, -9, -6, -11, -3, -5, -2, -1, -4]
from functools import total_ordering
import math
class MinHeap:
def __init__(self):
self.arr_heap = [None]
def __str__(self):
return str(self.arr_heap[1:])
def __repr__(self):
return str(self)
def get_left_pos(self, i:int) ->int:
return 2*i
def get_right_pos(self, i:int) ->int:
return 2*i+1
def get_parent_pos(self, i) ->int:
return math.floor(i/2)
def swap(self, pos_1, pos_2):
aux = self.arr_heap[pos_1]
self.arr_heap[pos_1] = self.arr_heap[pos_2]
self.arr_heap[pos_2] = aux
def is_a_leaf(self, posicao):
return posicao >= len(self.arr_heap)//2 and posicao <= len(self.arr_heap)
def heapify(self, pos_raiz_sub_arvore:int):
parent_pos = pos_raiz_sub_arvore
left_child_pos = self.get_left_pos(parent_pos)
right_child_pos = self.get_right_pos(parent_pos)
if not self.is_a_leaf(parent_pos):
if (self.arr_heap[parent_pos] > self.arr_heap[left_child_pos] or self.arr_heap[parent_pos] > self.arr_heap[right_child_pos]):
if self.arr_heap[left_child_pos] < self.arr_heap[right_child_pos]:
self.swap(parent_pos, left_child_pos)
self.heapify(left_child_pos)
else:
self.swap(parent_pos, right_child_pos)
self.heapify(right_child_pos)
def insert(self, element):
self.arr_heap.append(element)
current = self.arr_heap.index(element)
while self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)-1]:
self.swap(current, self.get_parent_pos(current))
current = self.get_parent_pos(current)
def remove(self):
element = self.arr_heap[1]
element_pos = len(self.arr_heap)-1
self.arr_heap[1] = self.arr_heap[element_pos]
self.arr_heap.pop(element_pos)
self.heapify(1)
return element
def __str__(self):
return str(self.arr_heap)
def __repr__(self):
return str(self)
测试文件为：
import unittest
from typing import List, Dict
from heap import MinHeap
class TestHeap(unittest.TestCase):
def test_heapify(self):
obj_heap = MinHeap()
obj_heap.arr_heap = [None,-12,-9,-6]
obj_heap.heapify(1)
self.assertListEqual(obj_heap.arr_heap, [None,-12,-9,-6], f"The heapify operation was not performed correctly. Input list: {[None,-12,-9,-6]}")
obj_heap.arr_heap = [None,-12,-15,-6]
obj_heap.heapify(1)
self.assertListEqual(obj_heap.arr_heap, [None,-15,-12,-6], f"The heapify operation was not performed correctly. Input list: {[None,-12,-15,-6]}")
obj_heap.arr_heap = [None,-12,-9,-15]
obj_heap.heapify(1)
self.assertListEqual(obj_heap.arr_heap, [None,-15,-9,-12], f"The heapify operation was not performed correctly. Input list: {[None,-12,-9,-15]}")
obj_heap.arr_heap = [None,-12,-2,-6,-4,-5,3,0,-1,1, -3, 2]
obj_heap.heapify(2)
self.assertListEqual(obj_heap.arr_heap, [None,-12,-5,-6,-4,-3,3,0,-1,1, -2, 2], f"The heapify operation was not performed correctly. Expected outcome: {[None,-12,-5,-6,-4,-3,3,0,-1,1, -2, 2]} result obtained: {obj_heap.arr_heap}. Input list: {[None,-12,-2,-6,-4,-5,3,0,-1,1, -3, 2]}")
obj_heap.arr_heap = [None,-12,-2,-4,-6,-5,3,0,1,-3, -3, 2]
obj_heap.heapify(2)
self.assertListEqual(obj_heap.arr_heap, [None,-12,-6,-4,-3,-5,3,0,1,-2, -3, 2], f"The heapify operation was not performed correctly. Expected outcome: {[None,-12,-6,-4,-3,-5,3,0,1,-2, -3, 2]} result obtained: {obj_heap.arr_heap}. Input list: {[None,-12,-2,-4,-6,-5,3,0,1,-3, -3, 2]}")
def test_insert(self):
arr_test = [1,-8,-11,-14]
arr_heap_expected = [[None,-12,-9,-6,-4,-3,-5,-2,-1,1],
[None,-12,-9,-6,-8,-3,-5,-2,-1,-4],
[None,-12,-11,-6,-9,-3,-5,-2,-1,-4],
[None,-14,-12,-6,-9,-3,-5,-2,-1,-4],
]
for val_inserir in arr_test:
objHeap = MinHeap()
objHeap.insert(val_inserir)
self.assertListEqual([None,val_inserir],objHeap.arr_heap,f"Incorrect insertion when inserting the value {val_inserir} in the heap {[None,-12,-9,-6,-4,-3,-5,-2,-1]}, expected: {[None,val_inserir]} result: {objHeap.arr_heap}")
for i,val_inserir in enumerate(arr_test):
objHeap = MinHeap()
objHeap.arr_heap = [None,-12,-9,-6,-4,-3,-5,-2,-1]
objHeap.insert(val_inserir)
self.assertListEqual(arr_heap_expected[i],objHeap.arr_heap,f"Incorrect insertion when inserting the value {val_inserir} in the heap {[None,-12,-9,-6,-4,-3,-5,-2,-1]}, expected: {arr_heap_expected[i]} result: {objHeap.arr_heap}")
def test_remove(self):
obj_heap = MinHeap()
obj_heap.arr_heap = [None,-12,-9,-4,-7,-5,3,0,1,-2, -3, 2]
min_val = obj_heap.remove()
self.assertEqual(min_val, -12, f"Incorrect insertion when inserting the value (-12) but {min_val} ")
self.assertListEqual(obj_heap.arr_heap, [None,-9,-7,-4,-2,-5,3,0,1,2, -3], f"The test_remove operation did not end with the expected heap.")
obj_heap.arr_heap = [None,-12]
min_val = obj_heap.remove()
self.assertEqual(min_val, -12, f"Incorrect insertion when inserting the value (-12) but {min_val} ")
self.assertListEqual(obj_heap.arr_heap, [None], f"The test_remove operation did not end with the expected heap.")
if __name__ == "__main__":
unittest.main()
所有其他测试工作正常。
我了解了 MinHeaps，所以我可以用你的代码解决问题（是的......我没有生命 ;)）。有两个问题，它们在同一条线上。该行是 insert 方法中的这一行：
while self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)-1]:
第一个问题是-1。您想要将父元素的值与当前元素的值进行比较。父元素位于 self.get_parent_pos(current)。我不知道您为什么认为要查看之前的元素。你不知道。所以在这一行中，你的第三个插入测试成功了，但是你的第四个测试失败了：
while self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)]:
第四次测试失败的原因是新元素到达树的顶部并且您的算法继续运行。由于该元素现在没有父元素，因此代码在尝试获取父元素的值时会崩溃。答案是识别新元素何时到达树的顶部，然后停止。为此，您将行修改为：
while current > 0 and self.arr_heap[current] < self.arr_heap[self.get_parent_pos(current)]:
使用该版本的行，您的所有插入测试都通过了。
给你一个小花絮。你的方法：
def get_parent_pos(self, i) ->int:
return math.floor(i/2)
可以更简洁地写成：
def get_parent_pos(self, i) ->int:
return i // 2
/ 生成浮点数结果，而 '//' 通过向下舍入生成整数结果。请记住这一点，因为您经常想要进行整数除法，而“//”是一种更简洁、更简单的方法。