BinaryHeap
2分木による最大ヒープ
PriorityQueueの実装に利用
code: BinaryHeap.js
/* ２分木による最大ヒープ */
class BinaryHeap {
constructor() {
this._data = [];
this._length = 0;
}
/* データ追加 priority value */
push(priority, value) {
const data = this._data;
data.push({p: priority, v: value});
let i = this._length;
let p = (i - 1) >> 1; // parent
// up heap
while (p >= 0 && datap.p < datai.p) { const tmp = datai; datai = datap; datap = tmp; i = p;
p = (i - 1) >> 1;
}
++this._length;
}
/* データ取出 */
pop() {
if (this.lngth <= 0) {
return null;
}
const length = this._length - 1;
const data = this._data;
const _top = this.top;
data.pop();
let i = 0;
let c1 = (i<<1) + 1; let c2 = (i<<1) + 2;
// down heap
let p0,p1,p2;
while(c1 < length) {
if (c2 < length) {
// both child exists
p0 = datai.p; p1 = datac1.p; p2 = datac2.p; if ((p1 < p2) && (p0 < p2)) {
// swap 0 & 2
const tmp = datai; datai = datac2; datac2 = tmp; i = c2;
}
else {
// swap 0 & 1
const tmp = datai; datai = datac1; datac1 = tmp; i = c1;
}
c1 = (i<<1) + 1; c2 = (i<<1) + 2;
}
else {
// right child not exists
p0 = datai.p; p1 = datac1.p; if (p0 < p1) {
// swap
const tmp = datai; datai = datac1; datac1 = tmp; }
break;
}
}
this._length = length;
return _top;
}
/* 最大の要素 */
get top() {
}
/* 要素数 */
get length() {
return this._length;
}
}
サンプル
AtCoder ABC 116 - D Various Sushi
code: abc116_d.js
class Main {
solve() {
const nums = input.nextIntArr();
const table = input.nextIntRange(nums0); const score = [];
table.sort((a,b) => a1 - b1).reverse(); const s = _.first(table, k);
const kinds = {};
s.forEach(e => kinds[e0] = (kinds[e0] ? kinds[e0] + 1: 1)); let kind = Object.keys(kinds).length;
scorekind = _.sum(s.map(s => s1)); const heap = new BinaryHeap();
s.forEach(e => {
}
});
let cur = k;
while (heap.length > 0 && cur < table.length) {
const target = heap.pop();
if (kinds[target0] >= 2) { do {
++cur;
if (kinds[next0] === undefined) { ++kind;
break;
}
} while(cur < table.length);
}
}
const scores = score.map((e,i) => e ? (e + i * i) : 0);
console.log(_.max(scores));
}
}
なお、この問題は最初にソートすればBinaryHeapを用いずとも配列で解くことができる