图与堆

图结构

堆结构

使用数组来存储，是一个完全二叉树

🏢 提示

公式 最后一个非叶子节点 Math.floor((size-1)/2) I的左节点 2*i +1 I的右节点 2*i +2 关键思路：

1. 上滤操作 用于插入数据时，放在数组最后位置，然后与父节点比较，交互，直到小于父节点
2. 下滤操作 用于提取元素，与子节点比较，交换，知道小于子节点
3. 原地建堆 自底而上的建堆方法，找到最后一个非叶子节点（也就是叶子节点与非叶子节点的分界，小于这个索引的都是非叶子节点，大于都是叶子节点），然后下滤，递归去下滤其他非叶子节点

最大堆

所有的父节点比子节点大的完全二叉树

最小堆

所有父节点都比子节点小的完全二叉树

代码实现

已兼容最大堆和最小堆

class Heap<T> {
  private data:T[]=[]
  /**最大堆 */
  private isMax: boolean
  constructor(arr:T[]=[],isMax = true){
    this.isMax = isMax
    if(arr.length>0){
      this.buildheap(arr)
    }
  }
  get lenght(){
    return this.data.length
  }
  

  isEmpty(){
    return this.lenght <= 0
  }

  /**
   * 插入一个元素
   * @param value 
   */
  insert(value:T){
    this.data.push(value)
    // 上滤操作
    this.heapify_up(this.lenght-1)
  }

  extract():T|null {
    if(this.isEmpty()) return  null
    this.swap(0,this.lenght-1) //交换顺序
    const res = this.data.pop()! //弹出元素
    this.heapify_down(0) //堆顶元素下滤
    return res
  }

  buildheap(arr:T[],isMax = true){
    this.data = arr
    this.isMax = isMax
    let i = this.get_parent(this.lenght-1)
    // i === 0 的时候，说明已经到根节点了，下滤一次后即可退出
    while(i>=0){
      this.heapify_down(i) //非叶子节点元素下滤
      i-- 
      // 最后一个非叶子节点往前，都是非叶子节点，[0, Math.floor((lenght-1)/2) ] 区间都是非叶子节点的索引，
      // [Math.floor((lenght-1)/2)+1,lenght-1]都是叶子节点
    }
 
  }
  /**
   * 下滤
   * @param i 
   */
  heapify_down(i:number){
    
    let maxIndex = i //假设当前的就是最大的
    while (true){
      const leftIndex = this.get_left(i)
      const rightIndex = this.get_right(i)
      if( leftIndex < this.lenght  && this.compare_fn(maxIndex,leftIndex)) maxIndex = leftIndex // 左子节点索引没有越界，且大于当前的最大值
      if( rightIndex < this.lenght && this.compare_fn(maxIndex,rightIndex)) maxIndex = rightIndex // 右子节点索引没有越界，且大于当前的最大值
      if(maxIndex===i){ // 说明左右子节点不大于的当前节点了，即可退出
        break
      }
      this.swap(i,maxIndex) // 最大值的子节点与当前节点 交换
      i = maxIndex // 拿最大值的子节点的索引，再次执行下滤
    }

  }

  /**
   * 上滤
   * @param i 
   */
  heapify_up(start:number){
    /**
     * 两个退出条件
     * 1. 子节点的值小于父节点，说明已经符合条件
     * 2. 当前节点已经是根节点了，说明上滤到堆顶了
     */
    let index = start
    while( index>0 ){
      let parentIndex = this.get_parent(index)
      if(this.compare_fn(index,parentIndex)){
        break
      }else{
        this.swap(index,parentIndex)
        index = parentIndex
      }
    }
  }
  /**
   * 
   */
  swap(i:number,j:number){
    const temp = this.data[i]
    this.data[i]=this.data[j]
    this.data[j] = temp

  }
  /**
   * 比较索引的值是否已在正确的位置，兼容最大堆和最小堆
   * @param i myIndex
   * @param j parentIndex
   */
  compare_fn(i:number,j:number):boolean {
    if(this.isMax){
      return this.data[i] <= this.data[j]
    }else{

      return this.data[i] >= this.data[j]
    }
  }

  get_parent(i:number):number {
    return Math.floor((i-1)/2) 
  }
  get_left(i:number):number {
    return 2*i + 1 
  }
  get_right(i:number):number {
    return 2*i + 2 
  }
  print(){
    console.log('this.data', this.data)
  }
}