/**
* 堆排序 时间复杂度O(nlogn)
* 初始化建堆O(n) 排序重建堆O(nlogn)
*
* @param {any} arr
* @returns
*
* @memberof sort
*/
sort7(arr){
var len = arr.length;
var tem;
this.buildMaxHeap(arr);
for(var i = len - 1; i > 0; i --){
tem = arr[i];
arr[i] = arr[0];
arr[0] = tem;
this.maxHeap(arr, 0 , --len);
}
return arr;
}
/**
* 建立最大堆
*
* @param {any} arr
*
* @memberof sort
*/
buildMaxHeap(arr){
var lastFather = Math.floor(arr.length / 2) - 1;//堆的最后一个父节点
for(var i = lastFather; i > 0; i --){
this.maxHeap(arr, i, arr.length);
}
}
/**
* 对重建堆排序
*
* @param {any} arr
* @param {any} index
* @param {any} heapSize
*
* @memberof sort
*/
maxHeap(arr, index, heapSize){
var tem = index; //记录入参元素下标
var leftChildIndex = 2 *index + 1; //元素的左子树的元素下标
var rightChildeIndex = 2 * index + 2;//元素的右子树的元素下标
if( leftChildIndex < heapSize && arr[leftChildIndex] > arr[index]){
index = leftChildIndex;
}
if( rightChildeIndex < heapSize && arr[rightChildeIndex] > arr[index]){
index = rightChildeIndex;
}
if(index != tem){
var t = arr[tem];
arr[tem] = arr[index];
arr[index] = t;
this.maxHeap(arr, index, heapSize);
}
}
