堆排序分为两个过程:
1.建堆。
堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆分为:大根堆和小根堆,升序排序采用大根堆,降序排序采用小根堆。
如果是大根堆,则通过调整函数将值最大的节点调整至堆根。
2.将堆根保存于尾部,并对剩余序列调用调整函数,调整完成后,再将最大跟保存于尾部-1(-1,-2,…,-i),再对剩余序列进行调整,反复进行该过程,直至排序完成。
代码如下:
//调整函数
function headAdjust(elements, pos, len){
//将当前节点值进行保存
var swap =