在 Javascript 中实现最小堆？

Question

我的一个测试用例有问题，我不明白为什么。任何帮助，将不胜感激。我尝试用数字类型实现一个最小堆，但似乎有些不对劲。我试图让 class 尽可能清楚。最小堆的预期顺序在删除元素时应按升序排列，例如：1,2,3,4,5,6.

最小堆 Class:

class MinHeap {
  
  constructor() {
    this.heap = [];
  }
  
  getLeftChildIndex(parentIndex) { return 2 * parentIndex + 1; }
  getRightChildIndex(parentIndex) { return 2 * parentIndex + 2; }
  getParentIndex(childIndex) { return Math.floor((childIndex - 1) / 2); }
    
  hasLeftChild(index) { return this.getLeftChildIndex(index) < this.heap.length; }
  hasRightChild(index) { return this.getRightChildIndex(index) < this.heap.length; }
  hasParent(index) { return this.getParentIndex(index) > 0 };
    
  leftChild(index) { return this.heap[this.getLeftChildIndex(index)]; }
  rightChild(index) { return this.heap[this.getRightChildIndex(index)]; }
  parent(index) { return this.heap[this.getParentIndex(index)]; }

  heapifyUp() {
    var index = this.heap.length - 1;
    while(this.hasParent(index) && this.parent(index) > this.heap[index]) {
      this.swap(this.getParentIndex(index), index);
      index = this.getParentIndex(index); 
    }
  }
    
  heapifyDown() {
    var index  = 0;
    while(this.hasLeftChild(index)) {
      var smallerChildIndex = this.getLeftChildIndex(index);
      if(this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
        smallerChildIndex = this.getRightChildIndex(index);
      }
        
      if(this.heap[index] < this.heap[smallerChildIndex]) {
        // No need to continue, we are in order
        break;
      } 
        
      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
        
    }
  }
      
  swap(index1, index2) {
    var temp = this.heap[index1];
    this.heap[index1] = this.heap[index2];
    this.heap[index2] = temp;
  }
    
  peek() {
    if(this.heap.length === 0) throw Error("Error: Heap underflow");
    return this.heap[0];
  }
    
  getSize() {
    return this.heap.length;
  }
    
  isEmpty() {
    return this.heap.length === 0;
  }
    
  remove() {
    if(this.heap.length === 0) throw Error("Error: Heap underflow");
    var item = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapifyDown();
    return item;
  }
    
  add(item) {
    this.heap.push(item);
    this.heapifyUp();
  }
}

测试用例失败：

var heap = new MinHeap();
var list = [];
heap.add(1);
heap.add(1);
heap.add(2);
list.push(heap.remove());
heap.add(4);
list.push(heap.remove());
heap.add(3);
list.push(heap.remove());
heap.add(6);
list.push(heap.remove());
heap.add(3);
list.push(heap.remove());
heap.add(4);
list.push(heap.remove());
heap.add(5);
list.push(heap.remove());
list.push(heap.remove());
list.push(heap.remove());
console.log(list); // logs [1,1,2,3,4,3,4,5,6]

我的逻辑有问题，但似乎无法弄清楚。

Answer 1

问题出在行

hasParent(index) { return this.getParentIndex(index) > 0 };

应该是

hasParent(index) { return this.getParentIndex(index) >= 0 };

或

hasParent(index) { return index > 0 };

使用损坏的实现，将 3 添加到堆 [4, 6] 不会正确向上传播它，因为索引 2 不被认为具有父级。

Answer 2

Bergi 指出，在这个特定的实现中，hasParent() 可以简化为一个非常小的表达式，内联它可能更好。

为了解决这个问题并寻找在 JavaScript 中对最小堆进行编程的好方法的开发人员，我致力于实现一个尽可能清晰的实现：

class MinHeap {
  constructor() {
    this.data = [];
  }

  peak() {
    return this.data[0];
  }

  push(value) {
    this.data.push(value);

    let i = this.data.length - 1;
    while (i > 0) {
      const parentIndex = Math.ceil((i / 2) - 1);
      if (this.data[i] < this.data[parentIndex]) {
        this.swap(i, parentIndex);
        i = parentIndex;
      } else {
        break;
      }
    }
  }

  pop() {
    // 1 or no remaining items is a special case
    if (this.data.length < 2) {
      return this.data.pop();
    }

    const min = this.data[0];
    this.data[0] = this.data.pop();

    let i = 0;
    while (true) {
      const [leftIndex, rightIndex] = [(i * 2) + 1, (i * 2) + 2];
      const leftValue = this.data[leftIndex] ?? Infinity;
      const rightValue = this.data[rightIndex] ?? Infinity;

      // If both children are larger than the candidate, we're done.
      if (leftValue > this.data[i] && rightValue > this.data[i]) {
        break;
      }

      // Otherwise pick the index of the smallest value
      const smallestIndex = leftValue < rightValue ? leftIndex : rightIndex;

      this.swap(i, smallestIndex);
      i = smallestIndex;
    }

    return min;
  };

  swap(i1, i2) {
    const val1 = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = val1;
  }
}

用法和行为：

const heap = new MinHeap();
heap.push(2);
heap.push(1);
heap.push(3);

heap.pop(); // 1
heap.pop(); // 2
heap.pop(); // 3

欢迎提出改进建议！对于不熟悉 array-backed-tree 和“sink”和“float”堆算法的人，还有一个 full explanation of the approach。

在 Javascript 中实现最小堆？

Implementing a Min Heap in Javascript?

javascript

heap