算法随笔 — 树结构基础 — 堆与优先队列

古城微笑少年丶 2022-10-16 07:49 196阅读 0赞

# 堆与优先队列定义 #

在二叉树一文中讲到了完全二叉树，在这里复习一下完全二叉树的概念

完全二叉树是只允许最后一层右侧有空的二叉树，其有如下性质：

1.  编号为 i 的节点(i=1开始)，其左孩子节点编号为  2 ∗ i 2\*i 2∗i，其右孩子编号为  2 ∗ i + 1 2\*i+1 2∗i\+1  
    若 i 从0开始，则其左孩子节点编号为  2 ∗ i + 1 2\*i+1 2∗i\+1，其右孩子编号为  2 ∗ i + 2 2\*i+2 2∗i\+2
2.  基于第一条性质，完全二叉树可以用数组来表示

![完全二叉树示例1][1]  
**堆** 就是通过完全二叉树实现的，通常将堆分为大顶堆和小顶堆

> **大顶堆**

![大顶堆][20210528132011105.png]  
上图为一个简单的大顶堆，其有以下特点：

1.  任意子顶堆的父节点的值比子节点的都大
2.  堆只维护上下关系，也就是说次大值在第二层，第三大值可能在第二层或第三层，第四大值可能在2、3、4层，以此类推；换一个角度来说，只有父子间能比较大小，兄弟间比较不了

> **小顶堆**

![小顶堆][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]  
上图为一个简单的小顶堆，性质类比大顶堆

> **优先队列**

回顾一下队列的性质，队列是一种先进先出的数据结构，最常用的是 push 和 pop 两个方法，而堆也有这两个方法。

不同的是，堆 pop() 出来的元素是整个堆元素中的最值，比如大顶堆依次把数据吐出来之后得到的是一个有序的降序序列，因此堆也被称作优先队列，依据此性质我们可以解决和有关维护最值的问题。

--------------------

# 堆的实现方式 #

上文提到过，根据完全二叉树的性质我们可以将堆用数组的方式实现

*  pop()  
    弹出数组首位元素，将原数组的最后一位进行数组头部的部位，然后进行**下沉**以维护堆的性质
 *  push()  
    在数组的最后一位推入元素，然后对数组的最后一位进行**上浮**以维护堆的性质

**性质维护**

*  上浮  
    找到当前节点的父节点并进行比较，以小顶堆举例，如果当前节点的值比父节点的值小，说明要进行交换(如果条件不符合，退出遍历)
 *  下沉  
    找到当前节点的左右子节点，以小顶堆举例，先标记当前节点，然后和左子节点比较，如果左子节点的值比当前节点小则标记该左子节点，如果右子节点的值比标记点小则标记右子节点，最后交换标记节点和当前节点(如果左右子节点都不符合要求，则退出遍历)

class Heap { 
      public heap: number[]
      private readonly kind: boolean
      constructor(arr: number[], kind: 'big' | 'small') { 
        this.kind = kind === 'big'
        this.heap = arr
    
        this.init()
      }
    
      private init() { 
        for (let i = 1; i < this.heap.length; i++) this.sortUp(i)
      }
    
      size() { 
        return this.heap.length
      }
    
      peek() { 
        return this.size() ? this.heap[0] : null
      }
    
      push(n: number) { 
        this.heap.push(n)
        this.sortUp(this.heap.length - 1)
      }
    
      pop() { 
        if (!this.heap.length) return null
        if (this.heap.length === 1) return this.heap.pop()
        const res = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.sortDown(0)
        return res
      }
    
      private sortUp(index: number) { 
        let parentIndex: number
        while (index > 0) { 
          parentIndex = (index - 1) >> 1
          if (this.kind) { 
            // 大顶堆
            if (this.heap[parentIndex] < this.heap[index]) this.swap(index, parentIndex)
            else break
          } else { 
            // 小顶堆
            if (this.heap[parentIndex] > this.heap[index]) this.swap(index, parentIndex)
            else break
          }
          index = parentIndex
        }
      }
    
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target = index
        while (index < this.heap.length - 1) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          if (this.kind) { 
            // 大顶堆
            if (leftIndex < this.heap.length && this.heap[leftIndex] > this.heap[target]) target = leftIndex
            if (rightIndex < this.heap.length && this.heap[rightIndex] > this.heap[target]) target = rightIndex
          } else { 
            // 小顶堆
            if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[target]) target = leftIndex
            if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[target]) target = rightIndex
          }
          if (target === index) break
          this.swap(target, index)
          index = target
        }
      }
    
      private swap(i: number, j: number) { 
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
      }
    }

**注意**  
获取父节点的时候代码使用了位运算，以下三种写法效果等同

parenIndex = (index - 1) >> 1
    parenIndex = (index - 1) / 2 | 0
    parenIndex = Math.floor((index - 1) / 2)

在初始化的时候，初始化操作是从头开始的，因为如果从尾开始，当遇到当前节点和父节点值相等时，就可能会使堆的性质被破坏  
![错误的初始化][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 1]  
以上代码实现的堆的节点只是一个数字，但是在解决问题的时候，我们通常会使用更加复杂的数据结构，具体见以下习题

--------------------

# 习题 #

在解决以下习题的时候，每次需要用到的堆我都会手动写一遍而不是单纯的复制粘贴。

刚学堆的时候我感觉这是我目前学过最简单的数据结构了，但是实际编写代码的时候出现了不少错误，有很多细节也只有错了之后才发现自己还有那么多细节没有掌握，所以读者希望能掌握这种数据结构的话，建议多写多练

当然有的时候堆并不是题目最优的解决方式，但是本文的习题都会尽量以堆来解决，因为本文的目的是练习堆的使用

> ## leetCode 剑指Offer 40 最小的k个数 ##

看到“最”字，首先想到的就是堆维护最值的性质，所以这道题我们可以建一个小顶堆，前k个弹出的元素就是题目答案

class Heap { 
      public heap: number[]
      private readonly kind: boolean
      constructor(arr: number[], kind: 'big' | 'small') { 
        this.kind = kind === 'big'
        this.heap = arr
        
        this.init()
      }
      
      private init() { 
        for (let i = 1; i < this.heap.length; i++) this.sortUp(i)
      }
      
      push(n: number) { 
        this.heap.push(n)
        this.sortUp(this.heap.length - 1)
      }
      
      pop() { 
        const res = this.heap.length ? this.heap[0] : null
        this.heap[0] = this.heap.pop()
        this.sortDown(0)
        return res
      }
      
      private sortUp(index: number) { 
        let parentIndex: number
        while (index > 0) { 
          parentIndex = (index - 1) >> 1
          if (this.kind) { 
            // 大顶堆
            if (this.heap[parentIndex] < this.heap[index]) this.swap(index, parentIndex)
            else break
          } else { 
            // 小顶堆
            if (this.heap[parentIndex] > this.heap[index]) this.swap(index, parentIndex)
            else break
          }
          index = parentIndex
        }
      }
      
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target = index
        while (index < this.heap.length - 1) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          if (this.kind) { 
            // 大顶堆
            if (leftIndex < this.heap.length && this.heap[leftIndex] > this.heap[target]) target = leftIndex
            if (rightIndex < this.heap.length && this.heap[rightIndex] > this.heap[target]) target = rightIndex
          } else { 
            // 小顶堆
            if (leftIndex < this.heap.length && this.heap[leftIndex] < this.heap[target]) target = leftIndex
            if (rightIndex < this.heap.length && this.heap[rightIndex] < this.heap[target]) target = rightIndex
          }
          if (target === index) break
          this.swap(target, index)
          index = target
        }
      }
      
      private swap(i: number, j: number) { 
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
      }
    }
    
    function getLeastNumbers(arr: number[], k: number): number[] { 
      const smallHeap = new Heap(arr, 'small')
      const res: number[] = []
      for (let i = 0; i < k; i++) { 
        res.push(smallHeap.pop())
      }
      return res
    }

![leetCode剑指offer40结果][leetCode_offer40]

> ## leetCode 1046 最后一块石头的重量 ##

![leetCode1046题目][leetCode1046]  
根据题目可知，我们需要一个大顶堆，每次取出两块石头进行操作，最后返回最后一块石头的重量，如果最后没有石头则返回0

class BigHeap { 
      public data: number[]
      constructor(data: number[]) { 
        this.data = data
        this.init()
      }
      
      init() { 
        for (let i = 1; i < this.data.length; i++) this.softUp(i)
      }
      
      size() { 
        return this.data.length
      }
      
      push(val: number) { 
        this.data.push(val)
        this.softUp(this.data.length - 1)
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop()
        this.softDown(0)
        return res
      }
      
      softUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.data[parentIndex] < this.data[index]) { 
            this.swap(index, parentIndex)
            index = parentIndex
          } else break
        }
      }
      
      softDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          target = index
          if (leftIndex < this.data.length && this.data[leftIndex] > this.data[target]) { 
            target = leftIndex
          }
          if (rightIndex < this.data.length && this.data[rightIndex] > this.data[target]) { 
            target = rightIndex
          }
          if (index === target) break
          this.swap(index, target)
          index = target
        }
      }
      
      swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
    }
    
    function lastStoneWeight(stones: number[]): number { 
      const stoneHeap = new BigHeap(stones)
      let x: number, y: number, diff: number
      while (stoneHeap.size() > 1) { 
        x = stoneHeap.pop()
        y = stoneHeap.pop()
        diff = Math.abs(x - y)
        if (diff === 0) continue
        stoneHeap.push(diff)
      }
      return !stoneHeap.size() ? 0 : stoneHeap.pop()
    }

![leetCode1046结果1][leetCode1046_1]  
还有一种方法是通过 Array.sort() 对数组进行排序之后取出两个最大的元素进行操作，如此反复直到数组的长度小于2 (只剩一块石头或者没有石头)

function lastStoneWeight(stones: number[]): number { 
      let x: number, y: number, diff: number
      while (stones.length > 1) { 
        stones = stones.sort((i, j) => j - i)
        x = stones.shift()
        y = stones.shift()
        diff = x - y
        if (!diff) continue
        stones.push(Math.abs(x - y))
      }
      return stones.length ? stones[0] : 0
    }

![leetCode1046结果2][leetCode1046_2]

> ## leetCode 703 数据流中的第k大元素 ##

从题目可知，我们可以通过构建一个大顶堆，其吐出来的第k个元素即题目所求

注意这里的元素不能吐出来就丢了，得到结果之后还得让大顶堆吞回去

class BigHeap { 
        public data: number[]
        constructor(data: number[]) { 
            this.data = data
            this.init()
        }
        
        init() { 
            for (let i = 1; i < this.data.length; i++) this.sortUp(i)
        }
        
        peek() { 
            return this.data.length ? this.data[0] : null
        }
        
        push(val: number) { 
            this.data.push(val)
            this.sortUp(this.data.length - 1)
        }
        
        pop() { 
            if (!this.data.length) return null
            if (this.data.length === 1) return this.data.pop()
            const res = this.data[0]
            this.data[0] = this.data.pop()
            this.sortDown(0)
            return res
        }
        
        private sortUp(index: number) { 
            let parentIndex: number
            while (index) { 
                parentIndex = (index - 1) >> 1
                if (this.data[index] > this.data[parentIndex]) { 
                    this.swap(index, parentIndex)
                    index = parentIndex
                } else break
            }
        }
        
        private sortDown(index: number) { 
            let leftIndex: number, rightIndex: number, target: number
            while (index < this.data.length) { 
                target = index
                leftIndex = (index << 1) + 1
                rightIndex = (index << 1) + 2
                if (leftIndex < this.data.length && this.data[leftIndex] > this.data[target]) target = leftIndex
                if (rightIndex < this.data.length && this.data[rightIndex] > this.data[target]) target = rightIndex
                if (target === index) break
                this.swap(index, target)
                index = target
            }
        }
        
        private swap(i: number, j: number) { 
            [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
        }
    }
    
    class KthLargest { 
        private nums: BigHeap
        private readonly k: number
        constructor(k: number, nums: number[]) { 
            this.nums = new BigHeap(nums)
            this.k = k
        }
    
        add(val: number): number { 
            const temp: number[] = []
            this.nums.push(val)
            for (let i = 0; i < this.k - 1; i++) { 
                temp.push(this.nums.pop())
            }
            const res = this.nums.peek()
            const data = this.nums.data
            this.nums = new BigHeap([...temp, ...data])
            return res
        }
    }

这道题通过堆去做的话在提交的时候有一个测试用例没有通过，提示运行时间超出限制，这个也是堆的一个弊端，数据量一大的话处理起来就会特别费劲

在经过多次尝试后我依然没有找到优化方法以通过提交测试用例，所以这道题用堆的题解先写到这，大神们可以在评论区给出更优的解法

另外一种方法也是利用 Array.sort()，先让数组排好序再直接取

class KthLargest { 
      private nums: number[]
      private readonly k: number
      constructor(k: number, nums: number[]) { 
        this.nums = nums
        this.k = k
      }
    
      add(val: number): number { 
        this.nums.push(val)
        this.nums = this.nums.sort((i, j) => j - i)
        return this.nums[this.k - 1]
      }
    }

![leetCode703结果2][leetCode703_2]  
从提交结果来看原生的 sort() 在面对大量数据时表现出来的性能也一般，后面文章会介绍排序算法，希望大家能继续支持

> ## leetCode 215 数组中的第k大元素 ##

这道题可以用排序、大顶堆、小顶堆的方法解答

先介绍最简单的排序，使用排序的方法在函数中只要写1行代码即可

function findKthLargest(nums: number[], k: number): number { 
      return nums.sort((i, j) => j - i)[k - 1]
    }

![leetCode215结果1][leetCode215_1]  
使用大顶堆的话只要弹  k − 1 k-1 k−1 次堆，最后堆顶元素即题目所求

class Heap { 
      public data: number[]
      private readonly kind: boolean
      constructor(data: number[], kind: 'big' | 'small') { 
        // 为了能用小顶堆解题而使用了深拷贝
        this.data = [...data]
        this.kind = kind === 'big'
        this.init()
      }
      
      private init() { 
        for (let i = 1; i < this.data.length; i++) this.sortUp(i)
      }
      
      peek() { 
        return this.data.length ? this.data[0] : null
      }
      
      size() { 
        return this.data.length
      }
      
      push(val: number) { 
        this.data.push(val)
        this.sortUp(this.data.length - 1)
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop()
        this.sortDown(0)
        return res
      }
      
      private sortUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.kind) { 
            // 大顶堆
            if (this.data[index] > this.data[parentIndex]) this.swap(index, parentIndex)
            else break
          } else { 
            // 小顶堆
            if (this.data[parentIndex] > this.data[index]) this.swap(index, parentIndex)
            else break
          }
          index = parentIndex
        }
      }
      
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          target = index
          if (this.kind) { 
            // 大顶堆
            if (leftIndex < this.data.length && this.data[leftIndex] > this.data[target]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex] > this.data[target]) target = rightIndex
          } else { 
            // 小顶堆
            if (leftIndex < this.data.length && this.data[leftIndex] < this.data[target]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex] < this.data[target]) target = rightIndex
          }
          if (target === index) break
          this.swap(target, index)
          index = target
        }
      }
      
      private swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
    }
    
    function findKthLargest(nums: number[], k: number): number { 
      const numsHeap = new Heap(nums, "big")
      for (let i = 0; i < k - 1; i++) { 
        numsHeap.pop()
      }
      return numsHeap.peek()
    }

![leetCode215结果2][leetCode215_2]  
使用小顶堆的话只要弹  l e n g t h − k length-k length−k 次堆，最后返回堆顶即题目所求

class Heap { 
      public data: number[]
      private readonly kind: boolean
      constructor(data: number[], kind: 'big' | 'small') { 
        // 为了能用小顶堆解题而使用了深拷贝
        this.data = [...data]
        this.kind = kind === 'big'
        this.init()
      }
      
      private init() { 
        for (let i = 1; i < this.data.length; i++) this.sortUp(i)
      }
      
      peek() { 
        return this.data.length ? this.data[0] : null
      }
      
      size() { 
        return this.data.length
      }
      
      push(val: number) { 
        this.data.push(val)
        this.sortUp(this.data.length - 1)
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop()
        this.sortDown(0)
        return res
      }
      
      private sortUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.kind) { 
            // 大顶堆
            if (this.data[index] > this.data[parentIndex]) this.swap(index, parentIndex)
            else break
          } else { 
            // 小顶堆
            if (this.data[parentIndex] > this.data[index]) this.swap(index, parentIndex)
            else break
          }
          index = parentIndex
        }
      }
      
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          target = index
          if (this.kind) { 
            // 大顶堆
            if (leftIndex < this.data.length && this.data[leftIndex] > this.data[target]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex] > this.data[target]) target = rightIndex
          } else { 
            // 小顶堆
            if (leftIndex < this.data.length && this.data[leftIndex] < this.data[target]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex] < this.data[target]) target = rightIndex
          }
          if (target === index) break
          this.swap(target, index)
          index = target
        }
      }
      
      private swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
    }
    
    function findKthLargest(nums: number[], k: number): number { 
      const numsHeap = new Heap(nums, "small")
      for (let i = 0; i < nums.length - k; i++) { 
        numsHeap.pop()
      }
      return numsHeap.peek()
    }

![leetCode215结果3][leetCode215_3]

> ## leetCode 373 查找和最小的k对数字 ##

![leetCode373题目][leetCode373]  
既然要找最小的元素，自然想到用小顶堆

当然本题不能像之前一样创建出来的堆的节点的数据类型是数字，在这里我定义节点的数据类型为 \[\[number, number\], number\]

第一个元素是一个数组，值为题目所提供的数字对；第二个元素是两个数字的和，进行上浮和下沉操作时比较的是节点的第二个元素

class SmallHeap { 
      public data: [[number, number], number][]
      constructor(data: [[number, number], number][]) { 
        this.data = data
      }
      
      private init() { 
        for (let i = 1; i < this.data.length; i++) this.sortUp(i)
      }
      
      size() { 
        return this.data.length
      }
      
      push(val: [[number, number], number]) { 
        this.data.push(val)
        this.sortUp(this.data.length - 1)
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop()
        this.sortDown(0)
        return res
      }
      
      private sortUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.data[index][1] < this.data[parentIndex][1]) { 
            this.swap(index, parentIndex)
            index = parentIndex
          } else break
        }
      }
      
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          target = index
          if (leftIndex < this.data.length && this.data[leftIndex][1] < this.data[target][1]) target = leftIndex
          if (rightIndex < this.data.length && this.data[rightIndex][1] < this.data[target][1]) target = rightIndex
          if (target === index) break
          this.swap(index, target)
          index = target
        }
      }
      
      private swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
      
    }
    
    function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] { 
      const smallHeap = new SmallHeap([])
      nums1.forEach(n1 => nums2.forEach(n2 => smallHeap.push([[n1, n2], n1 + n2])))
      const res: number[][] = []
      while (k--) { 
        if (smallHeap.size()) res.push(smallHeap.pop()[0])
      }
      return res
    }

![leetCode373结果][leetCode373 1]

> ## leetCode 692 前k个高频单词 ##

这道题可以使用大顶堆来解题，堆中节点的数据类型为 \[string, number\]，第一个元素是单词，第二个单词是出现次数

这里的节点比较操作有两点，首先是比较出现次数，当出现次数相同时比较字符串，比较字符串的呃时候优先比较首字母的排序顺序，如果首字母相同则比较字符串长度，长度较小的优先

在 js 中字符串比较直接使用比较符号即可，其会按照上述规则进行比较

function topKFrequent(words: string[], k: number): string[] { 
      const counter: {  [key: string]: number } = { }
      const smallHeap: [string, number][] = []
      words.forEach(word => counter[word] = counter[word] ? ++counter[word] : 1)
      let i = 0
      for (let key in counter) { 
        if (i < k) { 
          smallHeap.push([key, counter[key]])
          if (i === k - 1) initHeap(counter, smallHeap, k)
        } else if (counter[key] > smallHeap[0][1] || (counter[key] === smallHeap[0][1] && key < smallHeap[0][0])) { 
          smallHeap[0] = [key, counter[key]]
          sortDown(counter, smallHeap, k, 0)
        }
        i++
      }
      const temp = smallHeap.sort((a, b) => { 
        if (a[1] > b[1]) return -1
        else if (a[1] < b[1]) return 1
        else { 
          if (a[0] > b[0]) return 1
          else if (a[0] < b[0]) return -1
        }
      })
      return temp.map(item => item[0])
    }
    
    function initHeap(map: {  [key: string]: number }, arr: [string, number][], len: number) { 
      for (let i = len >> 1; i >= 0; i--) sortDown(map, arr, len, i)
    }
    
    function sortDown(map: {  [key: string]: number }, arr: [string, number][], len: number, index: number) { 
      const leftIndex = (index << 1) + 1, rightIndex = (index << 1) + 2
      let target = index
      
      if (leftIndex < len && (
        (map[arr[leftIndex][0]] < map[arr[target][0]]) ||
        ((map[arr[leftIndex][0]] === map[arr[target][0]]) && (arr[leftIndex][0] > arr[target][0]))
      )) { 
        target = leftIndex
      }
      if (rightIndex < len && (
        (map[arr[rightIndex][0]] < map[arr[target][0]]) ||
        ((map[arr[rightIndex][0]] === map[arr[target][0]]) && (arr[rightIndex][0] > arr[target][0]))
      )) { 
        target = rightIndex
      }
      if (target !== index) { 
        swap(arr, target, index)
        sortDown(map, arr, len, target)
      }
    }
    
    function swap(arr: any[], i: number, j: number) { 
      [arr[i], arr[j]] = [arr[j], arr[i]]
    }

> ## leetCode 295 数据流的中位数 ##

![中位数性质][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 2]  
从上图可以发现，中位数的前一个数字是前半段的最大值，中位数的后一个数字是后半段的最小值，因此我们需要一个大顶堆维护前半段的数字，一个小顶堆维护后半段的数字

为了维护整个数列的有序性，在插入时我们需要以下规则

1.  h1为空或者当前加入值≤h1堆顶时往h1里推，否则往h2里推
2.  使  h 1 数 量 ≥ h 2 数 量 + 1 h1数量≥h2数量+1 h1数量≥h2数量\+1
3.  当h1和h2的数量和为奇数时，中位数就是h1堆顶;  
    当h1和h2的数量和为偶数时，中位数就是两个堆顶和的平均值

class Heap { 
      public data: number[]
      private readonly kind: boolean
      constructor(data: number[], kind: 'big' | 'small') { 
        this.data = [...data]
        this.kind = kind === 'big'
        this.init()
      }
      
      private init () { 
        for (let i = 1; i < this.data.length; i++) this.sortUp(i)
      }
      
      size() { 
        return this.data.length
      }
      
      peek() { 
        return this.data.length ? this.data[0] : null
      }
      
      push(val: number) { 
        this.data.push(val)
        this.sortUp(this.data.length - 1)
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop()
        this.sortDown(0)
        return res
      }
      
      private sortUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.kind) { 
            // 大顶堆
            if (this.data[index] > this.data[parentIndex]) this.swap(index, parentIndex)
            else break
          } else { 
            // 小顶堆
            if (this.data[index] < this.data[parentIndex]) this.swap(index, parentIndex)
            else break
          }
          index = parentIndex
        }
      }
      
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          target = index
          
          if (this.kind) { 
            // 大顶堆
            if (leftIndex < this.data.length && this.data[leftIndex] > this.data[target]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex] > this.data[target]) target = rightIndex
          } else { 
            // 小顶堆
            if (leftIndex < this.data.length && this.data[leftIndex] < this.data[target]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex] < this.data[target]) target = rightIndex
          }
          
          if (target === index) break
          this.swap(target, index)
          index = target
        }
      }
      
      private swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
    }
    
    class MedianFinder { 
      public front: Heap
      public last: Heap
      constructor() { 
        this.front = new Heap([], 'big')
        this.last = new Heap([], 'small')
      }
      
      addNum(num: number): void { 
        //* 1.推入添加数字
        if (!this.front.size() || num <= this.front.peek()) this.front.push(num)
        else this.last.push(num)
        //* 2.平衡左右堆
        if (this.front.size() > this.last.size() + 1) this.last.push(this.front.pop())
        if (this.last.size() > this.front.size()) this.front.push(this.last.pop())
      }
      
      findMedian(): number { 
        const even = ((this.front.size() + this.last.size()) % 2) === 0
        if (even) { 
          return (this.front.peek() + this.last.peek()) / 2
        }
        return this.front.peek()
      }
    }

![leetCode295结果][leetCode295]  
**扩展**  
我们可以通过调整前后堆的数量关系维护数据流的任意位置，比如前三分之一后三分之一的位置

> ## leetCode 1753 移除石子的最大得分 ##

![leetCode1753题目][leetCode1753]  
这道题其实就是一道脑筋急转弯的题目，这里给出的是一种解决方法，可能有其他解法

![leetCode1753解题思路][leetCode1753 1]

1.  首先给三个石堆排序为有序递增
2.  取c与b的差和a的最小值，得分增加该最小值，a减去该最小值(从逻辑上来看c也要减去该最小值，但是之后c就没用上，所以这里只要对a操作即可)
3.  当a为奇数时自减1使其变成偶数，b、c平分a，得分加a，b减去a的一半
4.  最后得分加b就是题目所求

上图并没有展示所有情况，但是所有情况经过上述步骤都能得到正解，读者想到其他情况的话可以套用上述步骤进行验证

function maximumScore(a: number, b: number, c: number): number { 
      let ans = 0
      const sorted = [a, b, c].sort((a, b) => a - b)
      const min = Math.min(sorted[0], sorted[2] - sorted[1])
      ans += min
      sorted[0] -= min
      
      if (sorted[0] > 0) { 
        if (sorted[0] % 2 === 1) sorted[0]--
        ans += sorted[0]
        sorted[1] -= sorted[0] / 2
      }
      
      return ans + sorted[1]
    }

![leetCode1753结果][leetCode1753 2]

> ## leetCode 1801 积压订单的订单总数 ##

这道题的题目比较复杂，这里简单解释一下

题目会给出两种订单类型，购买订单和销售订单，在这两种订单中会给出价格和数量，最后我们要求出没有处理的订单总数

处理订单的原则只有一个：购买价格要≥销售价格 (不能赔本)

利 润 = 购 买 价 格 − 销 售 价 格 利润=购买价格-销售价格 利润=购买价格−销售价格  
为了使利益最大化，我们可以使用大顶堆来维护购买订单，使用小顶堆来维护销售订单

![leetCode1801解题思路][leetCode1801]  
此题的堆的节点数据结构为 \[number, number\]，第一个元素表示价格，第二个元素表示订单数，在维护堆的时候比较的是价格

class Heap { 
      // [价格, 订单数]
      public data: [number, number][]
      private readonly kind: boolean
      constructor(data: [number, number][], kind: 'big' | 'small') { 
        this.data = data
        this.kind = kind === 'big'
        this.init()
      }
      private init() { 
        for (let i = 1; i < this.data.length; i++) this.sortUp(i)
      }
      
      size() { 
        return this.data.length
      }
      
      peek() { 
        return this.data.length ? this.data[0] : null
      }
      
      push(val: [number, number]) { 
        this.data.push(val)
        this.sortUp(this.data.length - 1)
      }
      
      pop() { 
        if (!this.data.length) return null
        if (this.data.length === 1) return this.data.pop()
        const res = this.data[0]
        this.data[0] = this.data.pop()
        this.sortDown(0)
        return res
      }
      
      private sortUp(index: number) { 
        let parentIndex: number
        while (index) { 
          parentIndex = (index - 1) >> 1
          if (this.kind) { 
            // 大顶堆
            if (this.data[index][0] > this.data[parentIndex][0]) this.swap(index, parentIndex)
            else break
          } else { 
            // 小顶堆
            if (this.data[index][0] < this.data[parentIndex][0]) this.swap(index, parentIndex)
            else break
          }
          index = parentIndex
        }
      }
      
      private sortDown(index: number) { 
        let leftIndex: number, rightIndex: number, target: number
        while (index < this.data.length) { 
          leftIndex = (index << 1) + 1
          rightIndex = (index << 1) + 2
          target = index
          if (this.kind) { 
            // 大顶堆
            if (leftIndex < this.data.length && this.data[leftIndex][0] > this.data[target][0]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex][0] > this.data[target][0]) target = rightIndex
          } else { 
            // 小顶堆
            if (leftIndex < this.data.length && this.data[leftIndex][0] < this.data[target][0]) target = leftIndex
            if (rightIndex < this.data.length && this.data[rightIndex][0] < this.data[target][0]) target = rightIndex
          }
          if (target === index) break
          this.swap(index, target)
          index = target
        }
      }
      
      private swap(i: number, j: number) { 
        [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
      }
    }
    
    function getNumberOfBacklogOrders(orders: number[][]): number { 
      let res = 0, min = 0
      const buy = new Heap([], "big")
      const sell = new Heap([], 'small')
      
      // 0 buy 1 sell
      orders.forEach(([price, amount, orderType]) => { 
        if (orderType) { 
          // sell
          while (amount) { 
            if (buy.size() && buy.peek()[0] >= price) { 
              min = Math.min(buy.peek()[1], amount)
              buy.peek()[1] -= min
              amount -= min
              if (buy.peek()[1] === 0) buy.pop()
            } else { 
              sell.push([price, amount])
              break
            }
          }
        } else { 
          // buy
          while (amount) { 
            if (sell.size() && price >= sell.peek()[0]) { 
              min = Math.min(amount, sell.peek()[1])
              sell.peek()[1] -= min
              amount -= min
              if (sell.peek()[1] === 0) sell.pop()
            } else { 
              buy.push([price, amount])
              break
            }
          }
        }
      })
      
      // 处理积压订单
      while (buy.size() && sell.size() && buy.peek()[0] >= sell.peek()[0]) { 
        min = Math.min(buy.peek()[1], sell.peek()[1])
        buy.peek()[1] -= min
        sell.peek()[1] -= min
        if (!buy.peek()[1]) buy.pop()
        if (!sell.peek()[1]) sell.pop()
      }
      
      while (buy.size()) res += buy.pop()[1]
      while (sell.size()) res += sell.pop()[1]
      
      return res % 1000000007
    }

![leetCode1801结果][leetCode1801 1]

> ## leetCode 355 设计推特 ##

这道题要注意的是我们要维护一个用户列表，这个用户列表维护的是每个用户的关注和自己发的推特，注意每个用户的关注中必须有自己(这样可以在获取推特的时候更方便处理)

由于测试用例只能一条一条执行，所以我们可以定义一个整形的数字来记录推特发表的时间

使用大顶堆来维护最新发表的10条推特，这个大顶堆的节点的数据结构为 \[number, number\]，第一个元素为推特id，第二个元素为推特发表时间，在维护堆的时候只要比较时间即可

class TweetsHeap { 
        // [tweetId, time]
        public data: [number, number][]
        constructor() { 
            this.data = []
        }
        
        size() { 
            return this.data.length
        }
        
        push(val: [number, number]) { 
            this.data.push(val)
            this.sortUp(this.data.length - 1)
        }
        
        pop() { 
            if (!this.data.length) return null
            if (this.data.length === 1) return this.data.pop()
            const res = this.data[0]
            this.data[0] = this.data.pop()
            this.sortDown(0)
            return res
        }
        
        clear () { 
            this.data = []
        }
        
        private sortUp(index: number) { 
            let parentIndex: number
            while (index) { 
                parentIndex = (index - 1) >> 1
                if (this.data[index][1] > this.data[parentIndex][1]) this.swap(index, parentIndex)
                else break
                index = parentIndex
            }
        }
        
        private sortDown(index: number) { 
            let leftIndex: number, rightIndex: number, target: number
            while (index < this.data.length) { 
                leftIndex = (index << 1) + 1
                rightIndex = (index << 1) + 2
                target = index
                if (leftIndex < this.data.length && this.data[leftIndex][1] > this.data[target][1]) target = leftIndex
                if (rightIndex < this.data.length && this.data[rightIndex][1] > this.data[target][1]) target = rightIndex
                if (target === index) break
                this.swap(index, target)
                index = target
            }
        }
        
        private swap(i: number, j: number) { 
            [this.data[i], this.data[j]] = [this.data[j], this.data[i]]
        }
    }
    
    class Twitter { 
        private time: number
        private users: { [key: number]: { followees: any, tweets: [number, number][]}}   // [tweetId, time]
        private tweetHeap: TweetsHeap
        constructor() { 
            this.users = { }
            this.time = 0
            this.tweetHeap = new TweetsHeap()
        }
    
        postTweet(userId: number, tweetId: number): void { 
            if (!this.users[userId]) this.users[userId] = { followees: new Set([userId]), tweets: []}
            this.users[userId].tweets.push([tweetId, this.time++])
        }
    
        getNewsFeed(userId: number): number[] { 
            if (!this.users[userId]) this.users[userId] = { followees: new Set([userId]), tweets: []}
            this.users[userId].followees.forEach(followee => this.users[followee]?.tweets.forEach(t => this.tweetHeap.push(t)))
            const res: number[] = []
            while (this.tweetHeap.size() && res.length < 10) res.push(this.tweetHeap.pop()[0])
            this.tweetHeap.clear()
            return res
        }
    
        follow(followerId: number, followeeId: number): void { 
            if (!this.users[followerId]) this.users[followerId] = { tweets: [], followees: new Set([followerId])}
            this.users[followerId].followees.add(followeeId)
        }
    
        unfollow(followerId: number, followeeId: number): void { 
            this.users[followerId].followees.delete(followeeId)
        }
    }

![leetCode355结果][leetCode355]

--------------------

# 结语 #

这个系列会坚持更新，感谢支持

[1]: /images/20221014/b0ed968ba0b74441a52ae01c0070c30b.png
[20210528132011105.png]: /images/20221014/c13ac2a56cc341628c1318b76a06e4f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70]: /images/20221014/34e4e960b681463eb93b9fb0444e8b78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 1]: /images/20221014/44e8440713c44f43ac7077e4e2e823ea.png
[leetCode_offer40]: /images/20221014/52a9eb2a9a0145b385eb3c18440b20e7.png
[leetCode1046]: /images/20221014/f3c5c13b0b9a47608d33415cebaedf0a.png
[leetCode1046_1]: /images/20221014/139f29c7c40b4beaa2d27e7132c7c8ea.png
[leetCode1046_2]: /images/20221014/e4b89b1321294ec592f1ad605080d3ca.png
[leetCode703_2]: /images/20221014/a5248b6eefae4f0cb8a1124e521ca91b.png
[leetCode215_1]: /images/20221014/2fb484c64a3d41f5ad11af316e09dc9d.png
[leetCode215_2]: /images/20221014/67eeae9c008a45198f70d2eb07bf7371.png
[leetCode215_3]: /images/20221014/323e00576f044ea49f98e576f34981c4.png
[leetCode373]: /images/20221014/86f2124390bb412795fc97048ff35562.png
[leetCode373 1]: /images/20221014/eb1c1624556d454fb4e4922a2f2ca1c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RNX0dvZHNwZWVk_size_16_color_FFFFFF_t_70 2]: /images/20221014/2eb425e7abee42a2897408ccfe00121d.png
[leetCode295]: /images/20221014/5bb7b84c16794097b4e8b4954cf33cdd.png
[leetCode1753]: /images/20221014/2be69a54fa764762853ab2a2391ca07e.png
[leetCode1753 1]: /images/20221014/d672b6f2b02442959c5f1b7e1ffaf8b4.png
[leetCode1753 2]: /images/20221014/9ebe25dcce5d45e785dfe1c0f2f1f481.png
[leetCode1801]: /images/20221014/bbafb45d5fbd425280077723d2d0deaf.png
[leetCode1801 1]: /images/20221014/eb6efd77745c43439ab0556517275a20.png
[leetCode355]: /images/20221014/bf7b11fc58b1431eb0562785e2e1b029.png