Lstmxx的空间

703. 数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

链接

Tips

求TopK的问题可以用大堆根或者小堆根来解决问题

最小堆

• 题目中要求求出第K个大的元素，那么用小堆根就可以一直保持数组的第一个值为第K大个数

• 数组index与树位置的对应关系可以用一下以下公式来计算

  • 父节点：(index - 1) / 2

  • 左子点：index * 2 + 1

  • 右子点：index * 2 + 2

class KthLargest {
  k: number = -1;
  heap = new minHeap();
  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) {
      this.add(x);
    }
  }

  add(val: number): number {
    this.heap.offer(val)
    if (this.heap.size() > this.k) {
      this.heap.poll()
    }
    console.log(this.heap.data)
    return this.heap.peek()
  }
}

class minHeap {
  data: number[] = [];
  constructor(data = []) {
    this.data = data;
    this.heapify();
  }
  comparator(a: number, b: number): number {
    return a - b;
  }

  heapify() {
    if (this.size() < 2) return;
    for(let i = 1; i < this.size(); i++) {
      this.bubbleUp(i);
    }
    console.log(this.data)
  }

  peek() {
    if (this.size() === 0) return null
    return this.data[0]
  }

  offer(value) {
    this.data.push(value)
    this.bubbleUp(this.size() - 1)
  }

  poll() {
    if (this.size() === 0) {
      return null
    }
    const result = this.data[0]
    const last = this.data.pop()
    if (this.size() !== 0) {
      this.data[0] = last
      this.bubbleDown(0)
    }
    return result
  }

  swap(index1: number, index2: number) {
    [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]
  }

  bubbleUp(index: number) {
    while(index > 0) {
      const parentIndex = (index - 1) >> 1
      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
        this.swap(index, parentIndex)
        index = parentIndex
      } else {
        break
      }
    }
  }

  bubbleDown(index: number) {
    const lastIndex = this.size() - 1
    while(true) {
      const leftIndex = index * 2 + 1
      const rightIndex = index * 2 + 2
      let findIndex = index
      if (leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0) {
        findIndex = leftIndex
      }
      if (rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0) {
        findIndex = rightIndex
      }
      if (index !== findIndex) {
        this.swap(index, findIndex)
        index = findIndex
      } else {
        break
      }
    }
  }

  size() {
    return this.data.length
  }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */