JavaScript数据结构笔记-堆

堆

堆一般来说指的是二叉堆，在 二叉堆中每个元素都要保证大于（小于）等于子节点的元素。当一棵二叉堆的每个节点都符合这个条件时，它的根节点即这个二叉堆的最大值（最小值）

使用数组来存储一棵二叉堆，由于它是一颗完全二叉树。根据数组以及完全二叉树的特点，我们可以通过计算数组的索引在树中上下移动：从a[k]向上一层移动就令k等于k/2，向下一层移动则令k等于2k或者2k+1。利用这种数据结构我们可以实现对数级别的插入元素和删除最大元素的操作。

下面是一个最大堆的实现：

class Heap {
  constructor() {
    this.heap = [];
  }
  creat = (array) => {
    for(let i = 0; i < array.length; i++) {
      this.insert(array[i]);
    }
    this.print();
  }

// 交换i,j的数据
  swap = (i, j) => {
    let temp = this.heap[i];
    this.heap[i] = this.heap[j];
    this.heap[j] = temp;
  }
  // 插入一个新元素
  // 堆的上浮操作
  // 先将新元素添加到数组最后
  // 判断新元素与其父元素的大小，如果比父元素大则交换
  insert = (item) => {
    this.heap.push(item);
    let cur = this.heap.length - 1;
    let pre = Math.floor(cur/2); //父节点
    
    while(pre >= 0 && this.heap[cur] > this.heap[pre]) {
      this.swap(cur, pre);
      cur = pre;
      pre = Math.floor(pre/2);
    }
  }
// 删除最大元素、删除堆顶元素
// 堆的下沉操作
  removeMax = () => {
    // 移除堆顶元素，将最后一个元素放到堆顶
    let nIndex = 0;
	  let nValue = this.heap[nIndex];
    let nMaxIndex = this.heap.length-1;

    let nLeaf = this.heap.pop();
    this.heap[nIndex] = nLeaf;

    // 将顶部元素，与其子元素比较，大的元素交换到下面
    while(nIndex < nMaxIndex) {
      let nLeftIndex = 2 * (nIndex + 1) - 1;
      let nRightIndex = 2 * (nIndex + 1);

      let nSelectIndex = nLeftIndex;
      if (nRightIndex < nMaxIndex) {
        nSelectIndex = (this.heap[nLeftIndex] > this.heap[nRightIndex]) ? nLeftIndex : nRightIndex;
      }

      if (nSelectIndex < nMaxIndex && this.heap[nIndex] < this.heap[nSelectIndex] ){
        this.swap(nIndex, nSelectIndex);
      }

      nIndex = nSelectIndex;
    }
    return nValue;
  }

  print = () => {
    console.log(this.heap);
  }
}

function testheap() {
  const heap = new Heap();
  heap.insert(23);
  heap.insert(654);
  heap.insert(35);
  heap.insert(3);
  heap.insert(112);
  heap.insert(20);
  heap.insert(4);
  heap.insert(87);
  heap.insert(46);
  heap.insert(0);
  heap.print();

  // heap.creat([23,654,35,3,112,20,4,87,46,0]);

  console.log(heap.removeMax());
  heap.print();
  console.log(heap.removeMax());
  heap.print();
}

(10) [654, 112, 46, 87, 35, 20, 3, 4, 23, 0]
654
(9) [112, 87, 46, 23, 35, 20, 3, 4, 0]
112
(8) [87, 35, 46, 23, 0, 20, 3, 4]