python

Question

我正在尝试为堆编写删除函数。我得到了一个 head class 和 heapify 函数来使用，我只需要实现删除。我想在 O(log n) 时间内实现它。这是我试过的：

from heap import *
class heap_delete(heap):
    def delete(self, i):
        self.A[i] = self.A[-1] #put the bottom rightmost element in i
        self.min_heapify(i)

但是当我用提供的测试代码运行时，它显示 'failed'。阅读 AssertionError 声明似乎我试图操作的索引没有发生任何事情。这是我正在导入的堆代码：

def parent(i):
    return int(i/2)
def left(i)
    return 2*i
def right(i):
    return 2*i+1
class heap:
    def __init__(self):
        self.A = [None] #to make it 1 based, None is stuck at 0
    def __getitem__(self, i):
        return self.A[i]
    def min_heapify(self, i):
        l = left(i)
        r = right(i)
        smallest = i
        if l <= self.heapsize and self.A[l] < self.A[i]:
            smallest = l
        if r <= self.heapsize and self.A[r] < self.A[smallest]:
            smallest = r
        if smallest != i:
            self._swap(i, smallest)
            self.min_heapify(smallest)
    def _swap(self, index1, index2):
        self.A[index1], self.A[index2] = self.A[index2], self.A[index1]

还有decrease_key、extract_min、插入等功能。如有必要，我可以将它们添加到 post，但我相信我需要的一切都在这里。我收到的 AssertionError 如下：

    self.assertEquals(h.A, [None])
AssertionError: Lists differ: [None, 5] != [None]

和

    self.assertEquals(h.A, [None])
AssertionError: Lists differ: [None, 15] != [None]

前一个 AssertionError 来自我应该运行我的代码的测试函数。它调用 h.insert(5) 和 h.delete(1)，然后调用 self.assertEquals(h.A, [None])。同样在测试函数中的梯形图在 5、15、10 和 0 上调用 insert，然后是 h.delete(h.A.index(10))，然后是与之前相同的 assertEquals 语句。由此我相信我的删除功能没有删除任何东西。我尝试使用 del 和提供的 _swap 但可能没有正确使用它们。我再次寻找 O(log n) 时间，所以如果有人能指出我正确的方向，那就太好了。

Answer 1

当您从堆中删除时，您的数组大小应该会下降。您的删除功能目前没有发生这种情况:)。

Answer 2

def delete(self, i):
    self.A[i] = self.A[-1] #put the bottom rightmost element in i
    del self.A[-1]         # <--- shrink the list
    self.min_heapify(i)

python - 从堆中删除索引 i 处的元素

python - deleting element at index i from heap

heap

class