树的应用3—二叉堆

二叉堆实现优先队列

定义：优先队列，优先级高的放在队首，优先级低的放在队尾，优先级高的先出队。

1. 复杂度分析：
   可将入队与出队的复杂度都保持在O(logN)，排序复杂度为O(NlogN)
   对比正常用有序表实现入队与出队的操作，入队的复杂度为O(1~N)，出队的复杂度为O(N)

2. 采用方法：完全二叉树
   完全二叉树： 最底层的叶节点都集中在最左，内部节点都有两个子节点，最多有一个节点例外。

   
   image.png
   

   满二叉树：所有的内部节点都有左右两个子节点。特殊的完全二叉树

3. 方法特点：
   ①采用完全二叉树来实现对数复杂度。
   ②节点若为N，左子节点为2N，右子节点为2N+1
   ③堆次序：从叶节点至根节点的次序是从大到小排好次序的结构。
   ④实际是用一个列表来表示二叉堆的次序。
   ⑤新节点加入为叶节点，并逐步上浮
   ⑥最小节点出队，将最后一项提至根节点，并逐级下沉；未排序的堆列表也通过逐级下沉，获得排序好的二叉堆

# -------------------最小二叉堆的实现--------------------
class BinHeap:
    def __init__(self):
        # 设置一个下标0占位但不用，根节点从1开始
        self.heapList = [0]
        self.currentSize = 0

    def insert(self,key):
        self.heapList.append(key)
        self.currentSize += 1
        # 新节点加入，从叶节点加入，调整次序，逐步上浮，与各级父节点比较
        self.percup(self.currentSize)

    def minchild(self, i):
        if i*2 + 1 > self.currentSize:
            # 如果只有一个子节点，就只能与该子节点下沉
            return i*2
        elif self.heapList[i*2 + 1] > self.heapList[i*2]:
            # 从较小的子节点下沉
            return i*2
        else:
            return i*2 + 1

    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[i] = tmp

            i = i//2

    def perDown(self, i):
        while i*2 <= self.currentSize:
            div_num = self.minchild(i)
            if self.heapList[i] > self.heapList[div_num]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[div_num]
                self.heapList[div_num] = tmp
            i = div_num

    # 删除最小的节点，即将最底层的节点值赋予根节点，同时删除最底层节点，调整次序，逐步下沉，与各级子节点比较
    def delMin(self):
        reval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize -= 1
        self.heapList.pop()
        self.percDown(1)
        return reval

    # 直接对无序表进行下沉，从倒数第二层开始逐层进行下沉
    def buildHeap(self,alst):
        i = len(alst) // 2
        self.currentSize = len(alst)
        self.heapList = [0] + alst[:]
        print(self.heapList, i)
        while i > 0:
            self.perDown(i)
            i -= 1
        print(self.heapList, i)