2022年 11月 3日

Python 堆

堆是一类特殊的树，堆的通用特点就是父节点会大于或小于所有子节点（儿子不分左右）。一个最小堆（min-heap）就是其中的每一个节点都小于或等于其两个子节点的一个二叉树。一个最大堆（max-heap）将最大的节点放置到最靠近根节点的位置。

注意：不能把这种类型的堆和计算机用于管理动态内存的堆搞混了。下面是区别：

数据结构中：栈是一种具有后进先出的数据结构，堆是一种经过排序的树形数据结构，每个节点都有一个值。通常我们所说的堆的数据结构是指二叉树。堆的特点是根节点的值最小（或最大），且根节点的两个树也是一个堆。由于堆的这个特性，常用来实现优先队列。

内存分配中：栈是系统自动分配空间的，堆则是程序员根据需要自己申请的空间。由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。使用栈就像我们去饭馆里吃饭，只管点菜（发出申请）、付钱、吃（使用），吃饱了就走，不必理会切菜，洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处就是快捷，但是自由度小。使用堆就像是自己动手做喜欢的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

堆接口

我们将使用堆来实现一个优先队列，堆接口应该包含返回其大小、添加项、删除项和查看项的方法。

堆接口中的方法
方法 作用
heap.isEmpty() 如果堆为空，返回True，否则，返回False
heap.__len__() 等同于len(heap)，返回堆中项的数目
heap.__iter__() 等同于iter(heap)或for item in heap；从最小到最大地访问各项
heap.__str__() 等同于str(heap)，返回一个字符串，表示堆的形状
heap.__contains__(item) 等同于item in heap。如果item在堆中，返回True
heap.__add__(otherHeap) 等同于heap + otherHeap，返回一个新的堆，其内容是heap和otherHeap的内容
heap.__eq__(anyObject) 等同于heap == otherObject，如果堆等于anyObject的话，返回True。如果两个堆包含相同的项，那么它们相等
heap.peek() 返回heap最顶部的项。先验条件：heap不为空
heap.add(item) 将item插入到其在heap中适当的位置
heap.pop() 返回heap最顶部的项。先验条件：heap不为空

两个最为重要的堆操作是add和pop。add方法接收一个可比较的元素作为参数，并且将该元素插入到堆中合适的位置。这个位置通常位于一个比它大的元素之上的一层，并且位于一个比它小的元素之下。重复的元素会放置在之前输入的那个元素之下。pop方法删除堆中最顶端的元素，并返回最顶端的元素，并且维护堆的属性。peek操作返回堆最顶端的元素，但是不会删除它。

add方法（插入）和pop方法（删除）在整个堆实现都会使用，它们定义于ArrayHeap类中。在基于数组的实现中，这两个方法都需要在数组中维护堆的结构（实际上，使用了一个Python列表，但是在如下的讨论中，我们将这个结构称为一个数组）。

堆的实现

插入操作add

目标是在堆中找到新元素的合适位置，并且将其插入。下面是插入的策略：

（1）首先在堆的底部插入该元素，在数组实现中，这是数组中当前最后一个元素之后的位置

（2）然后，进入一个循环，只要新元素的值小于其父节点的值，循环就让这个新元素沿着堆向上“走”，将新的元素和其父节点交换。当这个过程停止的时候（要么新的元素大于或等于其父节点，要么到达了顶部的节点），新的元素就位于其适当的位置。

注意：数组一个元素的父节点的位置是通过将元素的位置减去1并且将结果除以2计算得到的。堆的最顶端在数组中的位置是0。

  1.     def add(self, item):
  2.         self._size += 1
  3.         self._heap.append(item)
  4.         curPos = len(self._heap) - 1
  5.         while curPos > 0:
  6.             parent = (curPos - 1) // 2
  7.             parentItem = self._heap[parent]
  8.             if parentItem <= item:
  9.                 break
  10.             else:
  11.                 self._heap[curPos] = self._heap[parent]
  12.                 self._heap[parent] = item
  13.                 curPos = parent

该方法的快速分析揭示了，你最多需要进行log2N次比较，就可以从底部移动至树的上面，因此，一次add操作是O(logN)。该方法偶尔会触发底层数组的大小翻倍，当发生翻倍的情况时，该操作就是O(n)，但这是将所有的相加操作都累计到一起，而每次相加操作都是O(1)。

删除操作pop

删除的目标是在删除根节点之后，返回该节点中的元素，并且调整其他节点的位置以维护堆属性。下面是删除操作的策略：

（1）首先，保存堆中的顶部元素和底部元素的指针，并且将该元素从堆的底部移动到顶部

（2）从堆的顶部往下走，将最小的元素向上移动一层，直到到达堆的底部

  1.     def pop(self):
  2.         if self.isEmpty():
  3.             raise Exception("Heap is empty")
  4.         self._size -= 1
  5.         topItem = self._heap[0]
  6.         bottomItem = self._heap.pop(len(self._heap) - 1)
  7.         if len(self._heap) == 0:
  8.             return bottomItem
  9.            
  10.         self._heap[0] = bottomItem
  11.         lastIndex = len(self._heap) - 1
  12.         curPos = 0
  13.         while True:
  14.             leftChild = 2 * curPos + 1 
  15.             rightChild = 2 * curPos + 2
  16.             if leftChild > lastIndex:
  17.                 break
  18.             if rightChild > lastIndex:
  19.                 maxChild = leftChild;
  20.             else:
  21.                 leftItem  = self._heap[leftChild]
  22.                 rightItem = self._heap[rightChild]
  23.                 if leftItem < rightItem:
  24.                     maxChild = leftChild
  25.                 else:
  26.                     maxChild = rightChild
  27.             maxItem = self._heap[maxChild]
  28.             if bottomItem <= maxItem:
  29.                 break
  30.             else:
  31.                 self._heap[curPos] = self._heap[maxChild]
  32.                 self._heap[maxChild] = bottomItem
  33.                 curPos = maxChild
  34.         return topItem

分析显示了删除所需的比较次数最多为log2N，因此pop操作为O(logN)。

本文是数据结构（用Python实现）这本书的读书笔记！