再次认识堆排序

之前自己写了一个堆排序, 然后发现边界条件测试竟然无法通过, 然后一通调整, 主要是各种边界.

参考:

• https://www.cnblogs.com/chengxiao/p/6129630.html
• wiki也可以作为参考.

我自己的代码样例:

//这个是测试用例.
let testcase=[
	[],
[1],
	[2,1],
	[1,2],
	[4,3,2],
	[3,2,1],
	[2,3,1],
	[1,3,2],
	[1,2,3],
	[4,3,2,1],
	[3,2,1,4],
	[1,2,3,4],
	[2,1,4,3],
	[4,3,2,1,5],
	[5,3,2,1,4],
	[1,5,2,3,4],
	[2,1,5,4,3],
	[6,2,1,5,4,3],
	[2,6,1,5,4,3],
	[2,1,6,5,4,3],
	[2,1,5,6,4,3],
	[2,1,5,4,6,3],

]
const log=console.log;
//function log() {};

for (let i = 0; i < testcase.length; i++) {

	let e = testcase[i];
	log("排序之前: ", e);
	e=littletop(e, f);
	log("---------------排序之后: ", e);

}
function f(p) {
	return p;
}

//这里是代码
function littletop(arra, f, top = Infinity) {
	top = arra.length > top ? top : arra.length;
	function swap(i, j) {
		let tmp = arra[i];
		arra[i] = arra[j];
		arra[j] = tmp;
	}
	function min(dad, l) {
		let son = (dad << 1) + 1;
		if (son >= l) return; //没有儿子跳出去.
		if (son + 1 < l && f(arra[son]) > f(arra[son + 1])) son++; //找到小儿子.
		if (f(arra[dad]) > f(arra[son])) { //爸爸不是最小的, 证明没排好.
			swap(dad, son);
			min(son, l);
		}
	}
	let l = arra.length;
	for (let i = ((l - 1) >> 1); i > -1; i--) {
		min(i, l); //初始化
	}
	for (let i = l-1; i > l - top; i--) {
		swap(0, i);
		min(0, i);
	}
	return arra; //尾部的top个元素是排好的.
}