JS数据结构与算法之《堆》

封装一下，完整的代码如下：

function Heap(type = 'max') {
  this.type = type
  this.arr = []
}

Heap.prototype.build = function() {
  this.arr.unshift(null)
  let lastParentIndex = Math.floor((this.arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    this.heapify(i, this.arr.length - 1)
  }
  this.arr.shift()
}

Heap.prototype.heapify = function(i, size) {
  let left = 2 * i
  let right = left + 1

  //左右孩子中较大或较小的一个
  let lr = -1

  //无左右孩子节点
  if (left > size && right > size) {
    return
  }
  //只有左孩子节点
  if (left <= size && right > size) {
    lr = left
  }
  //只有右孩子节点
  if (right <= size && left > size) {
    lr = right
  }
  //同时有左右孩子节点
  if (left <= size && right <= size) {
    lr = this.type === 'max' ? (this.arr[left] < this.arr[right] ? right : left) : (this.arr[left] > this.arr[right] ? right : left)
  }

  if ((this.type === 'max' && this.arr[i] < this.arr[lr]) || (this.type === 'min' && this.arr[i] > this.arr[lr])) {
    this.swap(i, lr)
    this.heapify(lr, size)
  }
}

Heap.prototype.sort = function() {
  this.arr[0] !== null && this.arr.unshift(null)
  for (let j = this.arr.length - 1; j > 0; j--) {
    this.swap(1, j)
    this.heapify(1, j - 1)
  }
  this.arr.shift()
}

Heap.prototype.add = function(elem) {
  this.arr.push(elem)
  this.arr[0] !== null && this.arr.unshift(null)
  let lastParentIndex = Math.floor((this.arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    this.heapify(i, this.arr.length - 1)
  }
  this.arr.shift()
}

Heap.prototype.pop = function() {
  this.arr[0] !== null && this.arr.unshift(null)
  this.swap(1, this.arr.length - 1)
  const top = this.arr.pop()

  let lastParentIndex = Math.floor((this.arr.length - 1) / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    this.heapify(i, this.arr.length - 1)
  }
  this.arr.shift()
  return top
}

Heap.prototype.swap = function(i, j) {
  let temp = this.arr[i]
  this.arr[i] = this.arr[j]
  this.arr[j] = temp
}

var heap = new Heap()
heap.add(5)
heap.add(2)
heap.add(8)
heap.add(3)
heap.add(1)
heap.add(6)
heap.add(9)
console.log(heap.arr)

//heap.build()
//console.log(heap.arr)

heap.add(10)
console.log(heap.arr)

heap.pop()
console.log(heap.arr)

heap.sort()
console.log(heap.arr)
复制代码

const maxHeap = new Heap('max');
const minHeap = new Heap('min');
let count = 0;
function Insert(num) {
  count++;
  if (count % 2 === 1) {
    maxHeap.add(num);
    minHeap.add(maxHeap.pop());
  } else {
    minHeap.add(num);
    maxHeap.add(minHeap.pop());
  }
}
function GetMedian() {
  if (count % 2 === 1) {
    return minHeap.value[0];
  } else {
    return (minHeap.value[0] + maxHeap.value[0]) / 2
  }
}
复制代码

function getLeastNumbers(arr, k) {
  if (k > arr.length) {
    return []
  }
  arr.unshift(null)
  buildMaxHeap(arr, k + 1)

  for (let i = k + 1; i < arr.length; i++) {
    if (arr[i] < arr[1]) {
      [arr[i], arr[1]] = [arr[1], arr[i]]

      let lastParentIndex = Math.floor(k / 2)
      for (let j = lastParentIndex; j > 0; j--) {
        maxHeapify(arr, j, k)
      }
    }
  }
  return arr.slice(1, k + 1)
}

function buildMaxHeap(arr, size) {
  let lastParentIndex = Math.floor(size / 2)
  for (let i = lastParentIndex; i > 0; i--) {
    maxHeapify(arr, i, size)
  }
}

function maxHeapify(arr, i, size) {
  let left = 2 * i
  let right = left + 1

  //左右孩子中较大的一个
  let maxlr = -1

  //无左右孩子节点
  if (left > size && right > size) {
    return
  }
  //只有左孩子节点
  if (left <= size && right > size) {
    maxlr = left
  }
  //只有右孩子节点
  if (right <= size && left > size) {
    maxlr = right
  }
  //同时有左右孩子节点
  if (left <= size && right <= size) {
    maxlr = arr[left] < arr[right] ? right : left
  }

  if (arr[i] < arr[maxlr]) {
    [arr[i], arr[maxlr]] = [arr[maxlr], arr[i]]
    maxHeapify(arr, maxlr, size)
  }
}


var arr = [4, 5, 1, 6, 2, 7, 3, 8]
var result = getLeastNumbers(arr, 4)
console.log(result)
//[4,3,1,2]
复制代码