二叉树（Binary Tree）和堆（Heap）

应用开发一般不会直接撸二叉树，Binary Tree，各种库和底层接口已经把它封装好了，但这个东西却是很多系统性能的关键，必须要深刻理解。Heap相对比较简单，很多时候需要我们自己直接手搓heap。

Terminologies，术语

定义：Binary Tree要么是empty，或者是一个Node，这个Node的左右两边包含value和reference，其reference指向的也是一颗Binary Tree，即子树，subtree。

计算node height时，要么数node，要么数edge，根据场景看那种方便，height要么最小为1，要么最小为0。

Perfect Binary Tree，完美二叉树

All internal nodes have 2 children, and all leaves have the same depth. 所有中间节点都有2个子结点，所有叶子节点的深度相同。

Full Binary Tree，满二叉树

Perfect Binary Tree is Full Binary Tree, but not vice versa. 完美二叉树是满二叉树，但反过来不成立。

Complete Binary Tree，完全二叉树

Every level is completely filled maybe except the bottom. Nodes in the bottom level are packed towards the left side. 除了最后一层，其它层的节点是满的，而且最后一层的节点全部靠向左侧。

Perfect Binary Tree is Complete Binary Tree, but not vice versa. 完美二叉树是完全二叉树，但反过来不成立。Full Binary Tree may not be Complete Binary Tree. 满二叉树不一定是完全二叉树。

Heap，堆

Heap是由Complete Binary Tree构建的数据结构，有两种类型的Heap，如下：

以上任何操作执行之后，都必须保证heap结构的特性不变（invariant）：

观察到Heap结构的存储是一个array，但此array并非完全有序。Heap结构并非要求所有元素有序，仅仅是要求parent与children的关系。所谓堆排序算法，Heapsort算法，就是利用Heap结构，对一组数据，先执行add，然后执行pop，得到的序列就是排好序的了。

Priority Queue，优先级队列

与普通Queue不一样的地方，在于pop（dequeue）出来的总是具有最大的（或最小的）优先级的元素。实现Priority Queue的方式很多，但性能最好的，是基于Heap的实现。排序算法怎么也要\(N\cdot\log{N}\)，而Heap这种结构，不追求完全有序，它可以在add和pop的时候，做到\(\log{N}\)。

下面是一个较通用的Heap参考实现和测试，如果保持默认的K，它就是个max heap：

class Heap:
    def __init__(self, key=lambda x:x):
        self.data = []
        self.K  = key

    @staticmethod
    def _parent(idx):
        assert idx > 0
        return (idx-1) // 2  # same as >>1, not int()

    @staticmethod
    def _left(idx):
        return idx*2 + 1

    @staticmethod
    def _right(idx):
        return idx*2 + 2

    def heapify(self, data):
        self.data = data
        for i in reversed(range(len(data)//2)):
            self._trickle_down(i)

    def _trickle_down(self, idx=0):
        """ trickle down start at idx """
        while idx < len(self.data):
            left, right = Heap._left(idx), Heap._right(idx)
            tidx = idx
            if left<len(self.data) and self.K(self.data[tidx])<self.K(self.data[left]):
                tidx = left
            if right<len(self.data) and self.K(self.data[tidx])<self.K(self.data[right]):
                tidx = right
            if tidx == idx:
                return
            self.data[idx], self.data[tidx] = self.data[tidx], self.data[idx]
            idx = tidx

    def add(self, x):
        """ bubble up """
        idx = len(self.data)
        self.data.append(x)
        while idx > 0:
            parent = Heap._parent(idx)
            if self.K(self.data[idx]) > self.K(self.data[parent]):
                self.data[idx], self.data[parent] = self.data[parent], self.data[idx]
                idx = parent
                continue
            return

    def peek(self):
        ret = None
        if self.data:
            ret = self.data[0]
        return ret

    def pop(self):
        ret = None
        if self.data:
            ret = self.data[0]
            self.data[0] = self.data[-1]
            del self.data[-1]
            self._trickle_down()
        return ret

    def __bool__(self):
        return len(self.data) > 0

    def __len__(self):
        return len(self.data)

    def __repr__(self):
        return repr(self.data)


import random
h = Heap()
a = [i for i in range(16)]
random.shuffle(a)
for i in a:
    h.add(i)
print(h)
for i in range(len(a)+1):
    print(h.peek())
    assert h.peek() == h.pop()


h = Heap(lambda x:-x)
a = [i for i in range(16)]
random.shuffle(a)
for i in a:
    h.add(i)
print(h)
for i in range(len(a)+1):
    print(h.peek())
    assert h.peek() == h.pop()

h = Heap(lambda x:len(x))
a = [str(i)*i for i in range(9)]
random.shuffle(a)
for i in a:
    h.add(i)
b = [h.pop() for _ in range(len(h))]
print(b)

给上面的实现，增加了一个heapify接口，如上！将一个任意的list，直接原地转换成heap结构。下面是测试代码，check_heap是个通用的heap结构checker！

def heap_check(data, K=lambda x:x):
    if (size:=len(data)) == 0:
        return True
    idx = (size//2) - 1
    i2 = idx * 2
    if size & 1:
        t = data[i2+2] if K(data[i2+1])<K(data[i2+2]) else data[i2+1]
        if K(data[idx]) < K(t):
            return False
    else:
        if K(data[idx]) < K(data[i2+1]):
            return False
    for i in range(idx-1,-1,-1):
        i2 = i * 2
        t = data[i2+2] if K(data[i2+1])<K(data[i2+2]) else data[i2+1]
        if K(data[i]) < K(t):
            return False
    return True


import random
for n in range(2000):
    a = [i for i in range(n)]
    random.shuffle(a)
    h = Heap()
    h.heapify(a)
    assert len(h) == n
    assert heap_check(h.data)


K = lambda x: -x
for n in range(2000):
    a = [i for i in range(n)]
    random.shuffle(a)
    h = Heap(K)
    h.heapify(a)
    assert len(h) == n
    assert heap_check(h.data, K)

除了priority queue的存储只能基于array，一般的queue和stack都可以采用linked-list方式存储。

Python官方的heapq模块

这里面有两个接口有点意思：nlargest和nsmallest，分别搜索一个iterable中最大或最小的n个元素。这两个接口背后的原理，就是heap，对任意iterable执行heapify后，每次pop，都是\(O(\log{N})\)。这两个接口在n比较小的时候使用，如果n太大，直接sorted排序然后slicing，如果n==1，用max或min。

LeetCode第23题

我在LeetCode第23题（合并K个有序单链表）中应用了heap数据结构，但实现与本文代码稍有不同，更加高效优雅...C和C++版本的heap实现也在此题内，供参考。