二叉堆与优先队列

二叉堆本质上是一种完全二叉树，它分为两种类型：1. 最大堆；2. 最小堆。最大堆的任何一个父节点的值，都大于或等于它左右孩子节点的值。最小堆的任何一个父节点的值，都小于或等于它左右孩子节点的值。

二叉堆的代码实现

// 上浮调整
function upAdjust(array){
  var childIndex = array.length - 1
  var parentIndex = parseInt((childIndex - 1) / 2)
  var temp = array[childIndex]
  while(childIndex > 0 && temp < array[parentIndex]){
    array[childIndex] = array[parentIndex]
    childIndex = parentIndex
    parentIndex = parseInt((parentIndex - 1) / 2)
  }
  array[childIndex] = temp
}

// 下沉调整
function downAdjust(array, parentIndex, length){
  var temp = array[parentIndex]
  var childIndex = 2 * parentIndex + 1
  while(childIndex < length){
    if(childIndex + 1 < length && array[childIndex + 1] < array[childIndex]){
      childIndex++
    }
    if(temp <= array[childIndex]) break
    array[parentIndex] = array[childIndex]
    parentIndex = childIndex
    childIndex = 2 * childIndex + 1
  }
  array[parentIndex] = temp
}

// 构建最小二叉堆
function buildHeap(array){
  for(var i = parseInt((array.length - 2) / 2); i >= 0; i--){
    downAdjust(array, i, array.length)
  }
}

var array = [7, 1, 3, 10, 5, 2, 8, 9, 6]
buildHeap(array)
console.log(array)
// [1, 5, 2, 6, 7, 3, 8, 9, 10]

// 插入节点
var array = [1, 5, 2, 6, 7, 3, 8, 9, 10]
array.push(0)
upAdjust(array)
console.log(array)
// [0, 1, 2, 6, 5, 3, 8, 9, 10, 7]

最小优先队列的实现

function enQueue(arr, key){
  arr.push(key)
  upAdjust(arr)
}

function deQueue(arr){
  if(!arr.length){
    console.error('the queue is empty!')
  }
  var head = arr[0]
  arr[0] = arr.pop()
  downAdjust(arr, 0, arr.length)
  return head
}

var arr = []
enQueue(arr, 3)
enQueue(arr, 5)
enQueue(arr, 10)
enQueue(arr, 2)
enQueue(arr, 7)
console.log(arr)
// [2, 3, 10, 5, 7]
deQueue(arr)
console.log(arr)
// [3, 5, 10, 7]