这个最小堆代码执行后为什么没有变化

Question

问题遇到的现象和发生背景

无论是使用列表构造最小堆还是一个一个元素插入构成最小堆都是未排序的，不知道到是不是percdown那里错了？

问题相关代码，请勿粘贴截图

```python
class MinHeap:
    def __init__(self):
        self.list = [0]
        self.currentsize = 0
    def insert(self,value):
        self.list.append(value)
        self.currentsize += 1
        i = self.currentsize
        while (i // 2 > 0 and value < self.list[i]):
            self.list[i] = self.list[i//2]
            i = i // 2
        self.list[i] = value
    def PercDown(self,i):
        tmp = self.list[i]
        while 2*i <= self.currentsize:
            '''找到孩子中的较小者'''
            if 2*i == self.currentsize:
                MinChild = 2*i
            else:
                MinChild = 2*i if self.list[2*i] < self.list[2*i+1] else 2*i+1
            '''移动'''
            if tmp < self.list[MinChild]:
                break
            self.list[i] = self.list[MinChild]
            i = MinChild
        self.list[i] = tmp
    def DelMin(self):
        self.list[1] = self.list[self.currentsize]
        self.currentsize -= 1
        self.list.pop()
        self.PercDown(1)
    def Construct(self,alist):
        it = iter(alist)
        try:
            while True:
                self.list.append(next(it))
        except StopIteration:
            pass
        for i in range(1,self.currentsize//2 + 1):
            self.PercDown(i)
    def __str__(self):
        return str(self.list)
    
if __name__ == '__main__':
    H = MinHeap()
    H.insert(5)
    H.insert(4)
    H.insert(3)
    H.insert(2)
    H.insert(1)
    print(H)

            

###### 运行结果及报错内容 

![img](https://img-mid.csdnimg.cn/release/static/image/mid/ask/427266441246139.png "#left")

Answer 1

单从insert中看，就有两个问题：
1.循环判断条件出错：不应该是while (i // 2 > 0 and value < self.list[i])，应该是while (i > 0 and self.list[i] < self.list[i//2])。
2.循环内部没有数据交换swap。
我改编了你的代码，具体代码如下所示：

import os
class MinHeap:
    def __init__(self):
        self.list = []
        self.currentsize = 0

    def insert(self, value):
        self.list.append(value)
        self.currentsize += 1
        i = self.currentsize - 1
        while (i > 0 and self.list[i] < self.list[i//2]):
            reg = self.list[i//2]
            self.list[i//2] = self.list[i]
            self.list[i] = reg
            i = i // 2
        # self.list[i] = value

    def PercDown(self, i):
        tmp = self.list[i]
        while 2 * i <= self.currentsize:
            '''找到孩子中的较小者'''
            if 2 * i == self.currentsize:
                MinChild = 2 * i
            else:
                MinChild = 2 * i if self.list[2 * i] < self.list[2 * i + 1] else 2 * i + 1
            '''移动'''
            if tmp < self.list[MinChild]:
                break
            self.list[i] = self.list[MinChild]
            i = MinChild
        self.list[i] = tmp

    def DelMin(self):
        self.list[1] = self.list[self.currentsize]
        self.currentsize -= 1
        self.list.pop()
        self.PercDown(1)

    def Construct(self, alist):
        it = iter(alist)
        try:
            while True:
                self.list.append(next(it))
        except StopIteration:
            pass
        for i in range(1, self.currentsize // 2 + 1):
            self.PercDown(i)

    def __str__(self):
        return str(self.list)


if __name__ == '__main__':
    H = MinHeap()
    H.insert(5)
    H.insert(4)
    H.insert(3)
    H.insert(2)
    H.insert(1)
    print(H)

有如下输出：
[1, 2, 3,4, 5]