堆1:堆与堆排序
堆(Heap)
堆分为大顶堆和小顶堆,堆是一颗完全二叉树。
规定如下:
- 堆是一颗完全二叉树
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
第一点,堆必须是一个完全二叉树。完全二叉树要求,除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。
第二点,堆中的每个节点的值必须大于等于(或者小于等于)其子树中每个节点的值。实际上,我们还可以换一种说法,堆中每个节点的值都大于等于(或者小于等于)其左右子节点的值。这两种表述是等价的。
对于每个节点的值都大于等于子树中每个节点值的堆,我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫做“小顶堆”。