堆排序
二叉堆是一个数组,可以被看作一个近似的完全二叉树。二叉堆可以分为两种形式:最大堆和最小堆。
在最大堆中,最大堆性质是指除了根以外的所有结点i都满足:$A[PARENT[i]]>=A[i]$
也就是说,某节点的值之多与其父结点一样大,因此,堆中的最大元素存放在根结点,并且,在任意子树中,该子树所包含的所有结点的数值都不大于该子树根结点的值。
最小堆性质是指除了根以外的所有结点i都满足:$A[PARENT[i]]<=A[i]$
堆中最小元素存放在根结点中。
堆的高度是$\lg n$,n是结点数量
1 | """维护堆的性质: |