Python 3 中的堆实现

Question

什么是堆？

堆是一种特殊的基于树的数据结构，其中树是一棵完全二叉树。一般来说，Heaps可以分为两种类型：

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

Min-Heap: 在 Min-Heap 中，出现在根节点的键必须是出现在它所有子节点的键中的最小值。对于该二叉树中的所有子树，相同的属性必须递归为真。

我的代码：

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，堆变成这样：

```
     0
   /
  1
```

类似地，如果我们按照所有步骤进行操作，则每一步中的堆将如下所示：（每个步骤见下文）

```
        0
      /   \
     1     3
```

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

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

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

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

此时，19 的父级更大，因此我们将其与 21 交换。因此正确的堆应该是这样的：

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

现在，如果我们执行水平顺序遍历，您将获得正确的输出作为当前输出。

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

Python 3 中的堆实现

Heap Implementation in Python 3

python

heap

python-3.x