为 HackerRank QHEAP1 优化 node.js 解决方案

Question

您好，我正在努力让自己更好地熟悉 Heaps，因此想尝试使用基元实现 HackerRanks>Practice>Data Structures>Heaps>QHEAP1 的解决方案，但是我遇到了两个测试的超时错误。

快速总结：我需要能够解析标准化输入并处理以下 3 种类型的查询：

向堆中添加一个元素。
从堆中删除特定元素。
打印堆中所有元素的最小值。

我想知道在哪里可以优化？据我所知，我的 del() 将在 O(n) 中执行，因为我需要搜索提供的元素。

// search for and delete specific element {x} from heap
function del(arr, x){
  let i = 0;
  let found = false;
  let n = arr.length;
  while(!found && i < n){
      if(arr[i] == x) found = true;
      i++;
  }
  if(found){
      arr[i-1] = arr[n-1];  // take the last element and overwrite to delete
      arr.length = n - 1;  // shorten array
      downHeap(arr, i);  // perform downHeap opertaion from index deleted
  }
}
// NOTE: customized for minHeap due to requirement to print minimum value
function downHeap(arr, t){
  // use array as binary tree - next index looking down is double current index
  // NOTE: i and t are 1 indexed for heap lookahead
  let i = 2 * t;  
  if(i >= arr.length) return;  // no more room
  // checkes if right child is smallest - if so updates index to right child
  if(i < arr.length - 1 && arr[i - 1] > arr[i]) i = i + 1;
  
  // if lower element is smaller than current element, swap em
  if(arr[i-1] < arr[t-1]){
      swap(arr, i-1, t-1);
      downHeap(arr,i);  // downHeap again at the next level
  } 
}

// insert x into heap 
function insert(arr, x){
  const n = arr.length;
  arr.length = n + 1;  // increasing array size
  arr[n] = x;  // adding el to end of array
  upHeap(arr, arr.length)
}

//NOTE: customized as minHeap due to requirement to print minimum value.
function upHeap(arr, t){
  // using array as binary tree - looking up - parant is half of current index
  const i = Math.floor(t/2);
  // if we've hit zero gone too far - NOTE: i, and t are 1 indexed for heap reference
  // also nothing to do if parent is smaller than current index
  if(i == 0 || arr[i-1] <= arr[t-1]) return;
  
  // child is smaller than parent swap and upHeap from parent
  swap(arr, t-1, i-1)
  upHeap(arr, i)
}

// swahp 
function swap(arr, l, r){
  const t = arr[l];
  arr[l] = arr[r];
  arr[r] = t;
}

PS。作为一个附带问题，我有点在为堆操作索引的 1 和为数组操作索引的 0 之间切换（例如，你会注意到里面有很多 i-1 语句up 和 downHeap 方法）- 想知道是否有更聪明的方法来做到这一点？

支持代码：

function processData(input) {
    //Enter your code here
    const inputs = input.split('\n');
    const n = inputs[0];
    let arr = [];
    for(let i = 1; i <= n; i++){
        const query = inputs[i].split(' ');
        const op = query[0];
        if(op == "1"){
            insert(arr, parseInt(query[1]))
        } else if(op == "2"){
            del(arr, parseInt(query[1]))
        } else if(op == "3"){
            console.log(arr[0])
        } else {
            console.log("Error reading op");
        }
    }
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

示例输入

22
1 286789035
1 255653921
1 274310529
1 494521015
3
2 255653921
2 286789035
3
1 236295092
1 254828111
2 254828111
1 465995753
1 85886315
1 7959587
1 20842598
2 7959587
3
1 -51159108
3
2 -51159108
3
1 789534713

Answer 1

代码确实令人困惑，因为（如您所写）它有时使用基于 1 的索引，而其他时候使用基于 0 的索引。

例如，在 insert 中，以下行表明您打算将 t 和 i 设为基于 1 的索引，因为您会即时转换它们到基于 0 的索引：

if(arr[i-1] < arr[t-1])

...但是在这一行中，您将 i 视为基于 0 的索引（如果 arr.length 是基于 1 的，则 i 是可接受的值):

if(i >= arr.length) return;  // no more room

同样的混淆发生在这里：

if(i < arr.length - 1 && arr[i - 1] > arr[i]) i = i + 1;

结果你会得到错误的结果。

当 JavaScript 期望在所有使用索引的地方使用基于 0 的索引时，使用基于 1 的索引会令人困惑。我没有勇气在那种状态下进一步调试你的代码。我建议在整个代码中使用基于 0 的索引，这意味着索引 t 处的值的左子节点位于索引 t*2+1.

一些其他备注：

要查找堆中某个值出现的索引，您不必编写显式循环。只需使用内置的 indexOf 方法。
递归很好，但是 downHeap 和 upHeap 函数将使用迭代方法更有效地工作，因为那样 - 而不是交换值 - 您可以获取值的副本向上或向下冒泡，然后仅移动（不交换）冲突的值，最终将复制的值插入到正确的位置。这将执行比重复交换更少的分配。
要插入一个值，您只需使用 push 方法，而不是“手动”更新 length。
除以 2 的整数除以 Math.floor，您可以使用移位运算符。

所以这是对您的代码的更正：

function del(arr, x) {
    const i = arr.indexOf(x); // This will be faster
    if (i >= 0) {
        const value = arr.pop();
        if (i < arr.length) { // Only assign back when it was not last
            arr[i] = value;
            downHeap(arr, i);
        }
    }
}

function downHeap(arr, t) {
    const val = arr[t];
    while (true) {
        let i = t * 2 + 1;
        if (i < arr.length - 1 && arr[i] > arr[i + 1]) i = i + 1;
        if (i >= arr.length || arr[i] >= val) break;
        arr[t] = arr[i]; // Don't swap to gain time
        // No recursion to save stack space
        t = i;
    }
    arr[t] = val;
}

function insert(arr, x) {
    arr.push(x);  // adding element to end of array
    upHeap(arr, arr.length - 1);
}

function upHeap(arr, t) {
    const val = arr[t];
    while (true) {
        let i = (t - 1) >> 1; // Shift operator may give some speed increase
        if (i < 0 || arr[i] <= val) break;
        arr[t] = arr[i]; // Don't swap to gain time
        // No recursion to save stack space
        t = i;
    }
    arr[t] = val;
}

为 HackerRank QHEAP1 优化 node.js 解决方案

Optimizing node.js solution for HackerRank QHEAP1

javascript

arrays

algorithm

heap