13.堆Heap

目录:
1.堆的概念
2.堆的性质
3.堆定义操作
4.堆的实现

1.堆的概念

1.1 优先队列：Priority Queue

优先队列的出队跟队列一样从队首出队；
但在优先队列内部，数据项的次序却是由“优先级”来确定：
  高优先级的数据项排在队首，而低优先级的数据项则排在后面；这样，优先队列的入队操作就比较复杂，需要将数据项根据其优先级尽量挤到队列前方。

1.2 堆

1. 实现优先队列的经典方案是采用堆数据结构，堆能够将优先队列的入队和出队复杂度都保持在O(log n)
2. 堆一般是由数组实现的，逻辑上堆可以被看做一个完全二叉树(除底层元素外是完全充满的，且底层元素是从左到右排列的)。
3. 堆分为最大堆和最小堆，最大堆是指每个根结点的值大于左右孩子的结点值；最小堆则是根结点的值小于左右孩子的值。

大顶堆和小顶堆.jpg

2.堆的性质

1.为了是堆操作能保持在对数水平上，就必须采用二叉树结构；
2.为保持操作始终在对数数量级上，保持平衡，采用“完全二叉树”的结构来近似实现“平衡”
3.完全二叉树，叶子结点最多只出现在最底层和次底层，而且最底层的叶结点都连续集中在最左边，每个内部结点都有两个子结点，最多只有一个结点例外
4.完全二叉树由于其特殊性，可以用非嵌套列表，以简单方式实现：
    # 此时在列表0号索引位置，放置一个哨兵，并不加入计算，故下边满足如下关系：
    结点下标：p
    左子结点：2p
    右子结点：2p+1
    其父结点下标：p // 2

image.png

3.堆定义操作

BinaryHeap()：创建一个空二叉堆对象；
insert(k)：将新key加入到堆中；
findMin()：返回堆中的最小项，最小项仍保留在堆中；
delMin()：返回堆中的最小项，同时从堆中删除；
isEmpty()：返回堆是否为空；
size()：返回堆中key的个数；
buildHeap(list)：从一个key列表创建新堆

4.堆的实现

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def perUp(self,i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                self.heapList[i] , self.heapList[i // 2] = self.heapList[i // 2] , self.heapList[i]
            i = i // 2

    def insert(self,k):
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.perUp(self.currentSize)

    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 percDown(self,i):
        while (i*2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                self.heapList[i] , self.heapList[mc] = self.heapList[mc] , self.heapList[i]
            i = mc

    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[:]
        # print(len(self.heapList),i)
        while (i > 0):
            # print(self.heapList,i)
            self.percDown(i)
            i = i - 1
        print(self.heapList,i)

if __name__ == '__main__':
    bh = BinHeap()
    bh.buildHeap([100,43,79,0,12])

    print(bh.delMin())
    print(bh.delMin())
    print(bh.delMin())
    print(bh.delMin())
    print(bh.delMin())

# 运行结果
[0, 0, 12, 79, 43, 100] 0
0
12
43
79
100