题目
群里有个人发的,题目很简单
随手写的
//debug print
function DB(obj) {
// console.log(obj);
}
//debug print maxHeap
function DBPMH(maxHeap) {
if(!maxHeap || MaxHeap != maxHeap.constructor) {
DB("DBPMH the input is not MaxHeap");
return;
}
let arr = maxHeap.arr;
let len = maxHeap.len;
DB(" \tlen is " + len);
for(let i = 0;i < len;i++) {
DB(" \t\tthe index " + i + " is " + arr[i]);
}
}
//define MaxHeap
let MaxHeap = function() {
this.len = 0;
this.arr = [];
}
MaxHeap.prototype.popMax = function() {
if(!this.len)
return undefined;
let value = this.arr[0];
let arr = this.arr;
let len = --this.len;
arr[0] = this.arr[len];
let index = 0;
let maxIndex = len - 1;
DB("pop the num = " + value + ", len = " + len + ", index = " + index + ", maxIndex = " + maxIndex);
while(1) {
let son1 = 2 * index + 1 <= maxIndex ? 2 * index + 1 : null;
let son2 = 2 * index + 2 <= maxIndex ? 2 * index + 2 : null;
let sonIndex = null;
if(null === son1 && null === son2)
return value;
if(null === son1 && null !== son2) {
sonIndex = 2 * index + 2;
} else if(null !== son1 && null === son2) {
sonIndex = 2 * index + 1;
} else {
sonIndex = son1 > son2 ? 2 * index + 1 : 2 * index + 2;
}
arr[sonIndex] ^= arr[index];
arr[index] ^= arr[sonIndex];
arr[sonIndex] ^= arr[index];
index = sonIndex;
}
return value;
}
MaxHeap.prototype.push = function() {
if(1 !== arguments.length) {
return undefined;
}
if("number" !== typeof(arguments[0])) {
return undefined;
}
let arr = this.arr;
arr[this.len++] = arguments[0];
let len = this.len;
let index = len - 1;
DB("push the num = " + arguments[0] + ", len = " + len + ", index = " + index);
while(1) {
if(0 == index)
return true;
let parentIndex = parseInt((index - 1) / 2);
if(arr[parentIndex] > arr[index])
return true;
arr[parentIndex] ^= arr[index];
arr[index] ^= arr[parentIndex];
arr[parentIndex] ^= arr[index];
index = parentIndex;
}
return true;
}
let maxHeap = new MaxHeap();
maxHeap.push(1);
maxHeap.push(6);
DBPMH(maxHeap);
maxHeap.push(3);
DBPMH(maxHeap);
maxHeap.popMax();
maxHeap.push(5);
let len = maxHeap.len;
for(let i = 0;i < len;i++) {
console.log(maxHeap.popMax());
}