简单的最小堆实现

gistfile1.txt

/**
 * Heap 简单的最小堆实现
 *
 * @returns {undefined}
 */
var Heap = function() {
  this.data = [];
};
Heap.prototype = {

  /**
   * 比较key值的大小
   * 较小的越优先级较高
   *
   * @param objA
   * @param objB
   * @returns {boolean}
   */
  comparator: function(objA, objB) {
    return +objA.key < +objB.key;
  },

  /**
   * 插入元素
   *
   * @param obj
   * @returns {undefined}
   */
  push: function(obj) {
    this.data.push(obj);
    this.siftUp(this.size() - 1);
  },

  /**
   * 弹出key最小元素
   *
   * @returns {object}
   */
  pop: function() {
    var ret = data[0];
    data[0] = this.data.pop();
    this.siftDown(0);
    return ret;
  },

  /**
   * 获得当前堆的大小
   *
   * @returns {number}
   */
  size: function() {
    return this.data.length;
  },

  /**
   * 清空堆
   *
   * @returns {undefined}
   */
  clear: function() {
    this.data.length = 0;
  },

  /**
   * 对下标为index的元素上浮调整
   *
   * @param index
   * @returns {undefined}
   */
  siftUp: function(index) {
    var item,
        parent,
        parentIndex;
        data = this.data;
    item = data[index];
    while (index > 0) {
      parentIndex = (index - 1) >> 1;
      parent = data[parentIndex];
      if (this.comparator(item, parent)) {
        data[index] = parent;
        index = parentIndex;
      } else {
        break;
      }
    }
    data[index] = item;
  },

  /**
   * 对下标为index的元素下沉调整
   *
   * @param index
   * @returns {undefined}
   */
  siftDown: function(index) {
    var childIndex, item, rightIndex;
        end = this.size(),
        data = this.data;
    item = data[index];
    childIndex = 2 * index + 1;
    while (childIndex < end) {
      rightIndex = childIndex + 1;
      if (rightIndex < end
          && !(this.comparator(data[childIndex], data[rightIndex]))) {
        childIndex = rightIndex;
      }
      data[index] = data[childIndex];
      index = childIndex;
      childIndex = 2 * index + 1;
    }
    data[index] = item;
  }
};