Binary Heap 二叉堆

优先队列在图算法中有着广泛应用。
如何构建优先队列呢？
使用列表？
在列表中，插入操作为 O(n) ,排序操作为 O(nlogn) 。
但是，我们可以做的更好。
这种数据结构是二叉堆。
由二叉堆构建的优先队列的出队入队操作为 O(lgn)
二叉堆分为最小堆，最大堆。
最小堆为在堆顶放置最小元素的堆结构。最顶端就是最小值。

binary heap operations 二叉堆的操作

(1) BinaryHeap() 构建实例
(2) insert(k) 插入k
(3) findmin() 找到最小值
(4) delmin() 删除最小值
(5) isEmpty() 是否为空
(6) size() 元素个数
(7) buildHeap(list) 为列表构建堆

Binary heap implement 二叉堆的实现

堆是利用索引值之间的关系表示节点的父子关系的。
比如，一列数组中，索引值为 p 的元素中存放一个节点。
那么，索引值为 2p 和 2p+1 的位置上分别存放左子节点，右子节点。

The Heap Order Property 堆中元素顺序的特性

作为最小堆，对于索引为 x 上的节点，其父节点的索引为 p ，则 p 中的元素小于等于 x 中的元素。

heap operation 堆中操作

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

    def percUp(self,i):   # the index cut down by 2 to find the parent index
        while i >=2:
            upper = i//2
            if self.heapList[upper] > self.heapList[i]:
                self.heapList[upper], self.heapList[i] = self.heapList[i], self.heapList[upper]
            i = upper

    def insert(self, k): # insert the new one at the bottom the pull it up
        self.heapList.append(k)
        self.curSize += 1
        self.percUp(self.curSize)

    def minChildIdx(self, father): # find the min child index watch out the index out of range
        if father * 2 + 1 > self.curSize:
            return father*2
        else:
            if self.heapList[father*2] < self.heapList[father*2+1]:
                return father*2
            else:
                return father*2+1

    def percDown(self,i): # from top to bottom exchange the parent with the min child
        while (i * 2) <= self.curSize:
            mc = self.minChildIdx(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 delMin(self): # exchange the bottom and the top, the percDown the new top to downside
        minVal = self.heapList[1]
        self.heapList[1] = self.heapList[self.curSize]
        self.curSize -= 1
        self.heapList.pop()
        self.percDown(1)
        return minVal

    def buildHeap(self, aList): # percDown from bottom to top
        self.curSize = len(aList)
        idx = len(aList) // 2
        aList.insert(0,0)
        self.heapList = aList
        while idx > 0:
            self.percDown(idx)
            idx -= 1


bh = BinHeap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

bh.buildHeap([2,3,6,1,0,9,7,4,3])
print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

print(bh.delMin())

3
5
7
11
0
1
2
3