【啊哈！算法】算法11：堆——神奇的优先队列（上）

堆是什么？是一种特殊的完全二叉树，就像下面这棵树一样。

        有没有发现这棵二叉树有一个特点，就是所有父结点都比子结点要小（注意：圆圈里面的数是值，圆圈上面的数是这个结点的编号，此规定仅适用于本节）。符合这样特点的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆。那这一特性究竟有什么用呢？

        假如有 14 个数分别是 99 、 5 、 36 、 7 、 22 、 17 、 46 、 12 、 2 、 19 、 25 、 28 、 1 和 92 。请找出这 14个数中最小的数，请问怎么办呢？最简单的方法就是将这 14个数从头到尾依次扫一遍，用一个循环就可以解决。这种方法的时间复杂度是 O(14) 也就是 O(N) 。