AcWing 838. 堆排序 ( JavaScript )
原题链接
简单
作者:
gaobowen
,
2019-11-23 13:25:03
,
所有人可见
,
阅读 848
//从1开始, 小根堆
let inArr = [];
let size = 0;
let swap = (a, b) => {
let t = inArr[a];
inArr[a] = inArr[b];
inArr[b] = t;
}
let down = k => {
let t = k, l = 2 * k, r = 2 * k + 1;
if (l <= size && inArr[l] < inArr[t]) t = l;//左
if (r <= size && inArr[r] < inArr[t]) t = r;//右
if (t !== k) swap(t, k), down(t); //调整后继续比较,维持堆的性质
}
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
let m = 0;
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
let a = getInputNums(line);
size = a[0];
m = a[1];
} else if (lineIdx === 1) {
inArr = getInputNums(line);
inArr.unshift(0);
// 容易出错 size / 2 变成了小数
for (let i = parseInt(size / 2); i > 0; i--) down(i);
//每次取出根节点放在outArr中
let outArr = [];
for (let i = 0; i < m; i++) {
outArr.push(inArr[1]);
swap(1, size--);
down(1);
}
//console.log(outArr.join(' '));
//第二种写法,把根节点与末尾互换 size--, 整个循环完成后会呈现出一个倒序的状态
//这种写法对整个数组的 升序用大顶堆,降序用小顶堆 比较方便
//inArr => 4 5 3 2 1
console.log(inArr.reverse().slice(0, m).join(' '));
}
});
});