堆及相关算法

二叉堆

• 堆就是完全二叉树

  完全二叉树：除了深度最深的一层外所有层节点数都满员
  深度：从根节点到该节点经历的节点个数
  

• 每一个节点都比左右子节点大–>最大堆，最大值在根节点

• 每一个节点都比左右子节点小–>最小堆，最小值在根节点

• 完全二叉树可以使用数组来存储

建立堆

• 将节点与父节点比较

//小顶堆
function buildHeap(items,heapSize){
  while(heapSize<items.length - 1){
  // items 第一个是<empty item>
    heapSize++
    heapify(items,heapSize)
  }
}
function heapify(items,i){
  while(Math.floor(i/2) > 0 && items[i] < items[Math.floor(i/2)]){
    [items[i],items[Math.floor(i/2)]] =  [items[Math.floor(i/2)],items[i]]
    // 交换位置
    i = Math.floor(i/2)
  } 
}

• 将节点与子节点比较

//大顶堆
function buildHeap(items){
  const heapSize = items.length - 1  // <-- items.length - 1 !
  // 最后叶子节点的索引值
  for(let i = Math.floor(heapSize/2) ; i >= 1 ; i--){ // <-i>=1 !
    // i 为最后一个非 叶子 节点的索引，i还有子节点
    heapify(items,heapSize,i)
  }
}
function heapify(items, heapSize, i) {
  // 自上而下式堆化
  while (true) {
      var maxIndex = i;
      if(2*i <= heapSize && items[maxIndex] < items[i*2] ) {
        // 这里的等号意味着万一这个节点是最后的节点呢
          maxIndex = i*2;
      }
      if(2*i+1 <= heapSize && items[maxIndex] < items[i*2+1] ) {
          maxIndex = i*2+1;
      }
      if (maxIndex === i) break;
      [items[i],items[maxIndex]] = [items[maxIndex],items[i]]
      i = maxIndex; 
  }
}

堆排序

1. 建立大顶堆/小顶堆
2. 则索引1位置为当前堆的 最大值/最小值
3. 循环将[1]与[末尾]交换位置，并且缩小堆的大小（相当于将上一次的最值移出堆）
4. 一直堆化
5. 大顶堆得到升序 / 小顶堆得到降序排列

function heapSort(arr){
  // 输入需要为[,]
  // const heap = [,]
  // let i = 0
  // while(i<arr.length){
  //   heap.push(arr[i++])
  // }

  const heapSize  =  arr.length - 1
  buildHeap(arr,heapSize)
  
  for(let i = heapSize ; i>1 ;i--){
    [arr[i],arr[1]]=[arr[1],arr[i]]
    heapSize --
    heapify(arr,heapSize,1)
  }
  return arr
}

topK问题

求出前k个最大/最小值，或者出现次数最多/最少的k个值

• 求大值，建立最小堆
• 求小值，建立最大堆

  
  // 比如求前k个最大值
  // 先用前k个数据建立小顶堆
  // 为什么求前k大建立小顶堆？？？
  // 如果建立大顶堆，交换堆顶后，堆顶依然是最大的，依次比较之后的数据只会改变堆顶而已，收集不了别的值
  
  function topK(data,k){
    let heap = [,...data]
    const heapSize = k
    buildHeap(heap,heapSize)
  
    for(let j = k ; j <data.length ;j++){
      // 将余下的数据依次与堆顶比较
      // 比小顶堆的堆顶大则交换
      if(heap[1] < data[j]){
        heap[1] = data[j]
        heapify(heap,k,1)
      }
    }
  
    heap.shift()
    return heap
  }
  
  function buildHeap(items ,heapSize){
    for(let i = Math.floor(heapSize/2) ; i >= 1 ; i--){
      heapify(items,heapSize,i)
    }
  }
  
  function heapify(items,heapSize,i){
    while(true){
      let minIndex = i
      if(2*i <= heapSize && items[minIndex] > items[i*2] ) {
          // 这里的等号意味着万一这个节点是最后的节点呢
          minIndex = i*2;
        }
        if(2*i+1 <= heapSize && items[minIndex] > items[i*2+1] ) {
          minIndex = i*2+1;
        }
        if (minIndex === i) break;
        [items[i],items[minIndex]] = [items[minIndex],items[i]]
        i = minIndex; 
    }
  }
  
  
  
  

中位数问题

n个数据中的中位数

  [1,2,3] => 2
  [1,2,3,4] => 2,3
  当 n % 2 !== 0 时，中位数为：arr[(n-1)/2]
  当 n % 2 === 0 时，中位数为：arr[n/2], arr[n/2 + 1]

• 将前n/2//偶数||（Math.floor(n/2)）+ 1//奇数堆化为大顶堆，后Math.floor(n/2)堆化为小顶堆。

• 结果分别为两个堆顶偶数/前面的堆顶奇数

• 动态数组，则把插入的数据与堆顶比较

  • 【升序】大于大顶堆的顶则加入小顶堆
  • 【降序】小于小顶堆则加入大顶堆
  • 加入后再次堆化，如果堆大小不满足分割中位数要求则继续调整

function Median(){
  this.maxHeap = new MaxHeap()
  this.minHeap = new MinHeap()
}
Median.prototype.addNum = function(num){
  if(num < this.maxHeap.getTop() || !this.maxHeap.getSize()){
    this.maxHeap.insert(num)
  }else{
    this.minHeap.insert(num)
  }

  if(this.maxHeap.getSize() - this.minHeap.getSize() > 1){
    //奇数分布
    //大顶堆size比小顶堆大1
    this.minHeap.insert(this.maxHeap.rmTop())
    //不符合则大顶堆顶插入小顶堆
  }
  if(this.minHeap.getSize() > this.maxHeap.getSize()){
    this.maxHeap.insert(this.minHeap.rmTop())
    // 
  }
}
Median.prototype.getMedianNum = function(){
  // return console.log(this.maxHeap.getSize());
  if(this.maxHeap.getSize() && this.maxHeap.getSize() === this.minHeap.getSize()){
    console.log(1);
    return (this.maxHeap.getTop() + this.minHeap.getTop())/2
  }
  return this.maxHeap.getTop()
}

// 大顶堆
function MaxHeap(){
  const heap = [,]
  this.getSize = () => heap.length - 1
  this.getTop = () => heap.length > 1 ? heap[1] : null
  this.insert = num => {
    //插入式建堆
    heap.push(num)
    let i = heap.length - 1
    // push 进去的索引
    while(Math.floor(i/2)>0 && heap[i] > heap[Math.floor(i/2)]){
      // 大顶堆，与父节点比较，大于则交换
      [heap[i],heap[Math.floor(i/2)]] = [heap[Math.floor(i/2)],heap[i]]
      i = Math.floor(i/2)
    }
  }
  this.rmTop = () => {
    if(!heap.length > 1) return null
    if(heap.length === 2) return heap.pop()
    const num = heap[1]
    heap[1] = heap.pop()// 拿走了top值，并用末尾节点填充
    heapify(1)
    return num
  }
  const heapify = i => {
    // 堆化
    const heapSize = heap.length - 1
    while(true){
      let maxIndex = i
      if(2*1 <= heapSize && heap[2*i] > heap[i]) maxIndex = 2*i
      if(2*i+1 <= heapSize && heap[2*i+1] > heap[maxIndex]) maxIndex = 2*i+1 // !!!!!!
      if(maxIndex === i) break
      [heap[i],heap[maxIndex]] = [heap[maxIndex],heap[i]]
      // 重新赋值i开始下级循环
      i = maxIndex
    }
  }
}


// 小顶堆
function MinHeap(){
  const heap = [,]
  this.getSize = () => heap.length - 1
  this.getTop = () => heap.length > 1 ? heap[1] : null
  this.insert = num => {
    heap.push(num)
    let i = heap.length - 1
    while(Math.floor(i/2)>0 && heap[i] < heap[Math.floor(i/2)]){
      // 小顶堆，与父节点比较，小于则交换
      [heap[i],heap[Math.floor(i/2)]] = [heap[Math.floor(i/2)],heap[i]]
      i = Math.floor(i/2)
    }
  }
  this.rmTop = () => {
    if(!heap.length>1) return null
    if(heap.length === 2) return heap.pop()
    const num = heap[1]
    heap[1] = heap.pop()
    heapify(1)
    return num
  }
  const heapify = i => {
    const heapSize = heap.length - 1
    while(true){
      let minIndex = i
      if(2*1 <= heapSize && heap[2*i] < heap[i]) minIndex = 2*i
      if(2*i+1 <= heapSize && heap[2*i+1] < heap[minIndex]) minIndex = 2*i+1
      if(minIndex === i) break
      [heap[i],heap[minIndex]] = [heap[minIndex],heap[i]]
      // 重新赋值i开始下级循环
      i = minIndex
    }
  }
}


// 二分查找法
const MedianFinder = function(){
  this.data = []
}
MedianFinder.prototype.addMun = function (num){
  const data = this.data
  if(data.length<1){
    data.push(num)
    return 
  }
  let L = 0
  let R = data.length - 1
  while(L<=R){
    let M = Math.floor((L+R)/2)
    if(data[M]===num){
      data.splice(M,0,num)
      return 
    }
    if(data[M]<num){
      L ++
    }else{
      R --
    }
  }
  data.splice(R+1,0,num)
}
MedianFinder.prototype.findMedian = function() {
  const len = this.data.length
  if(!len) return null
  const mid = Math.floor((len-1)/2)
  if(len%2===0){
    return (this.data[mid]+ this.data[mid+1])/2
  }else{
    return this.data[mid]
  }
}