堆

计算机数据结构中的堆，是什么？

堆是一种特殊的二叉树。二叉树是一棵树分叉的树，这棵树从根部开始分两条叉，每条叉又分出两条叉，每条叉的端点叫结点。树根是根结点。

堆是一种二叉树，它的结点排序是从上到下，同一行是从左到右，而且要求子结点必须大于父结点。所以最小值总是位于最上面。当结点有变化时，堆会自动调整来满足的以上规则。

当有结点插入时，首先会放入最后的一层的最右边。如果最后一层结点是满的，那么将它作为最后一层的最左结点的左子结点。然后与父结点比较，如果小于父结点，则与父结点交换位置，直至满足条件。自我调整结束。

那么，堆能用来做什么呢？它可以用来排序。将需要排序的数据构造成堆，处于最顶层的总是堆中最小的值。一次次将堆中根结点的值拿出顺序，即是这些数据从小到大的排序顺序。