堆是一种特殊的完全二叉树。除了最后一层必须填满，最后一层可以不填满

  • 所有节点都大于等于(最大堆)或者小于等于它的子节点 (最小堆)
  • js中使用数组表示堆

image.png

  • 左侧子节点的位置是2 * index + 1
  • 右侧子节点的位置是2 * index + 2
  • 父节点的位置是 Math.floor((index - 1) /2 )

应用

  • 堆能高效快速的查找出最大值最小值。时间复杂度为O(n)
  • 找出第K个最大(小)值

算法

第k个最大元素(leetcode 215)

时间复杂度O(n * logk)
空间复杂度O(k)

  • 构建一个最小堆，并将元素一次插入堆中
  • 当堆的容量超过k，就删除堆顶

  • 插入结束后，堆顶就是第k个最大元素 ```javascript class MinHeap{ constructor(){

    1.   this.heap = []

    }

    getParentIndex(index) {

    1.   return Math.floor((index - 1) / 2)

    }

    insert(value){

    1.   this.heap.push(value)
    2.   this.shiftUp(this.heap.length - 1)

    }

    swap(i1, i2) {

    1.   const temp = this.heap[i1]
    2.   this.heap[i1] = this.heap[i2]
    3.   this.heap[i2] = temp

    }

    shiftUp(index) {

    1.   if(index === 0 ) return 
    2.   const parentIndex = this.getParentIndex(index)
    3.   if(this.heap[parentIndex] > this.heap[index]) {
    4.       this.swap(parentIndex, index)
    5.       this.shiftUp(parentIndex)
    6.   }

    }

    getLeftIndex(index) {

    1.   return index * 2 + 1

    }

    getRightIndex(index) {

    1.   return index * 2 + 2

    }

    shiftDown(index) {

    1.   const leftIndex = this.getLeftIndex(index)
    2.   const rightIndex = this.getRightIndex(index)
    3.   if(this.heap[leftIndex] < this.heap[index]) {
    4.       this.swap(leftIndex, index)
    5.       this.shiftDown(leftIndex)
    6.   }
    8.   if(this.heap[rightIndex] < this.heap[index]) {
    9.       this.swap(rightIndex, index)
    10.       this.shiftDown(rightIndex)
    11.   }

    }

    pop(){

    1.   this.heap[0] = this.heap.pop()
    2.   this.shiftDown(0)

    }

    peek(){

    1.   return this.heap[0]

    }

    size(){

    1.   return this.heap.length

    } }

/**

  • @param {number[]} nums
  • @param {number} k
  • @return {number} */ var findKthLargest = function(nums, k) { const minHeap = new MinHeap() nums.forEach(item=>{
    1.  minHeap.insert(item)
    2.  if(minHeap.size() > k) {
    3.      minHeap.pop()
    4.  }
    }) console.log(‘minP’, minHeap) return minHeap.peek() }; ```

    前k个高频元素(leetcode 347)

    ```javascript /**
  • @param {number[]} nums
  • @param {number} k
  • @return {number[]}

  • 时间复杂度O(n logn) / var topKFrequent = function(nums, k) { const map = new Map() nums.forEach(item=>{

    1.  map.set(item, map.has(item) ?  map.get(item) + 1: 1)

    }) const array = Array.from(map) // 原生排序算法最快时间复杂度O(n*logn) // 这里进行了全排序，所以时间复杂度较高，实际上不需要 array.sort((a, b ) => {

    1.  return b [1] - a[1]

    }) return array.slice(0, k).map(item=>{

    1.  return item[0]

    }) }; javascript class MinHeap{ constructor(){

    1.  this.heap = []

    }

    getParentIndex(index){

    1.  return Math.floor((index - 1) / 2)

    }

    getLeftIndex(index){

    1.  return index * 2 + 1

    }

    getRightIndex(index){

    1.  return index * 2 + 2

    }

    insert(value){

    1.  this.heap.push(value)
    2.  this.shiftUp(this.heap.length - 1)

    }

    swap(i1, i2) {

    1.  const temp = this.heap[i1]
    2.  this.heap[i1] = this.heap[i2]
    3.  this.heap[i2] = temp

    }

    shiftUp(index) {

    1.  if(index === 0 ) return
    2.  const parentIndex = this.getParentIndex(index)
    3.  if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
    4.      this.swap(parentIndex, index)
    5.      this.shiftUp(parentIndex)
    6.  }

    }

    shiftDown(index) {

    1.  const leftIndex = this.getLeftIndex(index)
    2.  const rightIndex = this.getRightIndex(index)
    3.  if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){
    4.      this.swap(leftIndex, index)
    5.      this.shiftDown(leftIndex)
    6.  }
    7.  if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value){
    8.      this.swap(rightIndex, index)
    9.      this.shiftDown(rightIndex)
    10.  }

    }

    pop(){

    1.  this.heap[0] = this.heap.pop()
    2.  this.shiftDown(0)

    } size(){

    1.  return this.heap.length

    } }

/**

  • @param {number[]} nums
  • @param {number} k
  • @return {number[]}

  • 时间复杂度O(n logk) / var topKFrequent = function(nums, k) { const map = new Map() const minHeap = new MinHeap() nums.forEach(item=>{

    1.  map.set(item, map.has(item) ?  map.get(item) + 1: 1)

    })

    // O(n) map.forEach((value, key) => {

    1.  //时间复杂度O(logk)
    2.  minHeap.insert({
    3.      value,
    4.      key
    5.  })
    6.  //时间复杂度O(logk)
    7.  if(minHeap.size() > k) {
    8.      minHeap.pop()
    9.  }

    })

    return minHeap.heap.map(item=>{

    1.  return item.key

    }) }; ```

    合并k个排序链表(leetcode 23)

    ```javascript class MinHeap{ constructor(){

    1.  this.heap = []

    }

    getParentIndex(index){

    1.  return Math.floor((index - 1) / 2)

    }

    getLeftIndex(index){

    1.  return index * 2 + 1

    }

    getRightIndex(index){

    1.  return index * 2 + 2

    }

    insert(value){

    1.  this.heap.push(value)
    2.  this.shiftUp(this.heap.length - 1)

    }

    swap(i1, i2) {

    1.  const temp = this.heap[i1]
    2.  this.heap[i1] = this.heap[i2]
    3.  this.heap[i2] = temp

    }

    shiftUp(index) {

    1.  if(index === 0 ) return
    2.  const parentIndex = this.getParentIndex(index)
    3.  if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) {
    4.      this.swap(parentIndex, index)
    5.      this.shiftUp(parentIndex)
    6.  }

    }

    shiftDown(index) {

    1.  const leftIndex = this.getLeftIndex(index)
    2.  const rightIndex = this.getRightIndex(index)
    3.  if(this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val){
    4.      this.swap(leftIndex, index)
    5.      this.shiftDown(leftIndex)
    6.  }
    7.  if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val){
    8.      this.swap(rightIndex, index)
    9.      this.shiftDown(rightIndex)
    10.  }

    }

    pop(){

    1.  if(this.size() === 1) {
    2.      return this.heap.shift()
    3.  }
    4.  const top = this.heap[0]
    5.  this.heap[0] = this.heap.pop()
    6.  this.shiftDown(0)
    7.  return top

    }

    size(){

    1.  return this.heap.length

    } }

/**

  • Definition for singly-linked list.
  • function ListNode(val, next) {
  • this.val = (val===undefined ? 0 : val)
  • this.next = (next===undefined ? null : next)
  • } / /*
  • @param {ListNode[]} lists
  • @return {ListNode}
  • 时间复杂度O(n * logk)
  • 时间复杂度O(k) h */ var mergeKLists = function(lists) { const h = new MinHeap() const res = new ListNode(0) // 定义指针p let p = res lists.forEach(item => {
    1.  if(item) h.insert(item);
    }) while(h.size()){
    1.  console.log(h)
    2.  const n = h.pop()
    3.  p.next = n
    4.  p = p.next
    5.  if(n.next) {
    6.      h.insert(n.next)
    7.  }
    } return res.next }; ```