二叉堆（binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。
二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。

python

class Heap(object):
    def __init__(self):
        self.heap = [0]
        self.size = 0

    def isEmpty(self):
        return self.size == 0

    def findMin(self):
        return self.heap[1]

    def percUp(self, i):
        while (i // 2) > 0:
            if self.heap[i] < self.heap[i // 2]:
                tmp = self.heap[i // 2]
                self.heap[i // 2] = self.heap[i]
                self.heap[i] = tmp
            i = i // 2

    def insert(self, k):
        self.heap.append(k)
        self.size = self.size + 1
        self.percUp(self.size)

    def percDown(self, i):
        while (i * 2) <= self.size:
            mc = self.minChild(i)
            if self.heap[i] > self.heap[mc]:
                tmp = self.heap[i]
                self.heap[i] = self.heap[mc]
                self.heap[mc] = tmp
            i = mc

    def minChild(self, i):
        if i * 2 + 1 > self.size:
            return i * 2
        else:
            if self.heap[i * 2] < self.heap[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retval = self.heap[1]
        self.heap[1] = self.heap[self.size]
        self.size = self.size - 1
        self.heap.pop()
        self.percDown(1)
        return retval

    def buildHeap(self, lst):
        i = len(lst) // 2
        self.size = len(lst)
        self.heap = [0] + lst[:]
        while i > 0:
            self.percDown(i)
            i = i - 1


bh = Heap()
bh.buildHeap([9, 5, 6, 2, 3])
print(bh.delMin())
print(bh.findMin())
print(bh.size)