Python 3中的堆实现

Question

什么是堆？

堆是一种特殊的基于树的数据结构，其中树是一个完整的二叉树.一般来说，堆可以有两种类型：

Max-Heap :在Max中，存在于根节点的键必须是其所有子节点上存在的键中最大的。对于该二叉树中的所有子树，相同的属性必须是递归的。

Min:在Min中的位于根节点的键必须是其所有子节点上的键中的最小值。对于该二叉树中的所有子树，相同的属性必须是递归的。

我的代码：

class Heap:
    def __init__(self,type1 = False):
        self.type1 = type1
        self.array = []
        self.array.append(-1)

    def comparePush(self,parentIndex,currIndex):
        if self.type1 is False:
            return self.array[parentIndex] > self.array[currIndex]  # this is for minHeap
        else:
            return self.array[parentIndex] < self.array[currIndex]  # this is for maxHeap

    def push(self,item):
        self.array.append(item)
        currIndex = len(self.array)-1
        parentIndex = currIndex // 2

        
        while currIndex != 1 and self.comparePush(parentIndex,currIndex):
            # swapping elements
            temp = self.array[currIndex]
            self.array[currIndex] = self.array[parentIndex]
            self.array[parentIndex] = temp

            #changing the indices
            currIndex = parentIndex
            parentIndex = currIndex // 2

    def compareHeapify(self,childIndex,newIndex):
        if self.type1 is False: #minHeap check for minindex
            return self.array[childIndex] < self.array[newIndex]
        else:
            return self.array[childIndex] > self.array[newIndex]

    def heapify(self,currIndex):
        newIndex = currIndex
        last = len(self.array) - 1
        left = 2*newIndex
        right = 2*newIndex+1

        if left <= last and self.compareHeapify(left,newIndex):
            newIndex = left
        if right <= last and self.compareHeapify(right,newIndex):
            newIndex = right

        if newIndex!=currIndex:
            #swap
            temp = self.array[newIndex]
            self.array[newIndex] = self.array[currIndex]
            self.array[currIndex] = temp

            self.heapify(newIndex)

    def pop(self): # pops the max element in maxHeap and min element in minHeap44
        # swap item at index 1 with item at the last idex
        lastIndex = len(self.array) - 1
        temp = self.array[1]
        self.array[1] = self.array[lastIndex]
        self.array[lastIndex] = temp

        # pop element at the last index
        self.array.pop()

        #heapify
        self.heapify(1)

# q3 = Heap()
# q3.push(35)
# q3.push(33)
# q3.push(42)
# q3.push(10)
# q3.push(14)
# q3.push(19)
# q3.push(27)
# q3.push(44)
# q3.push(26)
# q3.push(31)
# print(q3.array)
# q3.pop()
# print(q3.array)

q3 = Heap()
q3.push(0)
q3.push(1)
q3.push(3)
q3.push(17)
q3.push(21)
q3.push(36)
q3.push(7)
q3.push(25)
q3.push(100)
q3.push(19)
print(q3.array)

电流输出：

[-1, 0, 1, 3, 17, 19, 36, 7, 25, 100, 21]

预期输出：

[-1,0,1,3,17,21,36,7,25,100,19]

我的想法：

在我看来，推送操作一定是错误的，然而，逻辑似乎是非常好的，这让我很困惑。此外，数组必须类似于水平顺序遍历，根据我的输出，这完全不是真。我应该如何解决这个问题呢？注意：只有19和21偏离了它们正确的位置或索引。

Answer 1

通过查看您的代码和输入，我感到您当前的输出是正确的，而您的预期输出实际上是错误的。

详细的解释如下：

最初，我们推0，所以堆只有顶部有0。

我们推1，堆就变成了这样：

1. 0 / 1

同样，如果我们遵循所有步骤，则每个步骤中的堆将如下所示：(每个步骤请参阅下面)

1. 0 / \ 1 3

1. 0 / \ 1 3 / 17

1. 0 / \ 1 3 / \ 17 21

1. 0 / \ 1 3 / \ / 17 21 36

1. 0 / \ 1 3 / \ / \ 17 21 36 7

1. 0 / \ 1 3 / \ / \ 17 21 36 7 / 25

1. 0 / \ 1 3 / \ / \ 17 21 36 7 / \ 25 100

1. 0 / \ / \ 1 3 / \ / \ / \ / \ 17 21 36 7 / \ / 25 100 19

现在，19岁的父母更大了，所以我们用21来交换。因此，正确的堆应该是这样的：

             0
           /   \
          /     \
         1        3
       /   \     /  \
      /     \   /    \
     17     19 36     7
    / \     /
   25 100  21

现在，如果您执行级别顺序遍历，您将得到正确的输出作为当前输出。

我认为输入"2“而不是"21”的预期输出是正确的，这可能就是您的困惑开始的地方