4.5.2 实践演练——实现二叉堆操作_Python算法详解-QQ阅读男生武侠网

上QQ阅读APP看书，第一时间看更新

4.5.2 实践演练——实现二叉堆操作

一种实现优先队列的经典方法便是采用二叉堆（Binary Heap），二叉堆能将优先队列的入队和出队复杂度都保持为O(log2n)。二叉堆的逻辑结构像二叉树，但用非嵌套的列表来实现。二叉堆有两种：键值总是最小的排在队首，称为“最小堆”（min heap）；反之，键值总是最大的排在队首，称为“最大堆”（max heap）。

在Python语言中，用于二叉堆操作的函数如下。

· binaryHeap()：创建一个空的二叉堆对象。

· insert(k)：将新元素压入堆中。

· findMin()：返回堆中的最小项，最小项仍保留在堆中。

· delMin()：返回堆中的最小项，同时从堆中删除。

· isEmpty()：返回堆是否为空。

· size()：返回堆中节点的个数。

· buildHeap(list)：从一个包含节点的列表里创建新堆。

下面的实例文件brackets.py演示了实现二叉堆操作的过程。

源码路径：daima\第4章\brackets.py

class BinHeap:
     def __init__(self):
          self.heapList = [0]
          self.currentSize = 0
     def percUp(self,i):
          while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                tmp = self.heapList[i // 2]
                self.heapList[i // 2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2
     def insert(self,k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
     def percDown(self,i):
        while (i * 2) <= self.currentSize:
             mc = self.minChild(i)
             if self.heapList[i] > self.heapList[mc]:
                   tmp = self.heapList[i]
                   self.heapList[i] = self.heapList[mc]
                   self.heapList[mc] = tmp
             i = mc
     def minChild(self,i):
        if i * 2 + 1 > self.currentSize:
             return i * 2
        else:
             if self.heapList[i*2] < self.heapList[i*2+1]:
                   return i * 2
             else:
                   return i * 2 + 1
     def delMin(self):
       retval = self.heapList[1]
       self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
     def buildHeap(self,alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

执行后会输出：