详解堆的javascript实现方法

详解堆的javascript实现方法

堆的定义

堆是一种特殊的树形数据结构，其每一个节点都有一个值，通常所表达的语义是“子节点的值都不小于（或都不大于）父节点的值”。堆可以用数组或者树形表示。堆的某个节点与其子节点之间还有一定的大小关系，因此堆又分为最大堆和最小堆。

堆的属性

• 最大堆：对于所有节点i的值均不小于它的子节点的值，根节点为最大值；
• 最小堆：对于所有节点i的值均不大于它的子节点的值，根节点为最小值。

堆的常见操作

• 插入
• 删除堆顶元素
• 堆排序
• 调整节点位置
• 堆的建立

堆的javascript实现方法

将堆转化为数组表示，定义如下：

[1,2,3,4,5,6,7]

插入节点

将节点插入到数组末尾：

var heap = [1,2,3,4,5,6,7];
heap.push(8);

为了保持堆的属性，需要调整节点位置：

function adjustHeap(heap) {
  for(var i=Math.floor((heap.length-1)/2); i>=0; i--) {
    adjustNode(heap, i, heap.length);
  }
  return heap;
}

function adjustNode(heap, index, length){
  var left = index*2 + 1, right = index*2 + 2;
  var maxIndex = index;
  if(left < length && heap[left] > heap[maxIndex]) {
    maxIndex = left;
  }
  if(right < length && heap[right] > heap[maxIndex]) {
    maxIndex = right;
  }
  if(maxIndex !== index) {
    swap(heap, maxIndex, index);
    adjustNode(heap, maxIndex, length);
  }
}

function swap(heap, i, j){
  var temp = heap[i];
  heap[i] = heap[j];
  heap[j] = temp;
}

console.log(adjustHeap(heap));
// [8, 5, 7, 4, 2, 6, 3, 1]

删除堆顶元素

将堆顶元素和数组末尾的元素交换，然后弹出末尾元素，最后调整堆：

function removeMax(heap){
  var max = heap[0];
  heap[0] = heap[heap.length - 1];
  heap.pop();
  adjustHeap(heap);
  return max;
}

console.log(removeMax(heap)); // 8
console.log(heap); // [7, 5, 6, 4, 2, 3, 1]

示例说明

假设有一个数组[2,1,5,4,3]，将它转化为堆：

var heap = [2,1,5,4,3];
console.log(adjustHeap(heap)); // [5, 4, 2, 1, 3]

删除堆顶元素，并将剩余元素重新调整为堆：

console.log(removeMax(heap)); // 5
console.log(adjustHeap(heap)); // [4, 3, 2, 1]

以上就是堆的javascript实现方法的详解攻略，希望对您有所帮助！