[M] 3066. Minimum Operations to Exceed Threshold Value II

輸入：nums = [2,11,10,1,3], k = 10
輸出：2
解釋：
- 第一次操作，移除 `1` 和 `2`，然後加入 `1 * 2 + 2 = 4`，nums 變為 `[4, 11, 10, 3]`。
- 第二次操作，移除 `3` 和 `4`，然後加入 `3 * 2 + 4 = 10`，nums 變為 `[10, 11, 10]`。
- 此時所有數字都大於等於 `10`，可以停止操作。
最少需要 2 次操作使所有數字都大於等於 `10`。

輸入：nums = [1,1,2,4,9], k = 20
輸出：4
解釋：
- 第一次操作後，nums 變為 `[2, 4, 9, 3]`。
- 第二次操作後，nums 變為 `[7, 4, 9]`。
- 第三次操作後，nums 變為 `[15, 9]`。
- 第四次操作後，nums 變為 `[33]`。
- 此時所有數字都大於等於 `20`，可以停止操作。
最少需要 4 次操作使所有數字都大於等於 `20`。

// @/types/Heap.ts
export class MinHeap<T> {
  private heap: T[] = [];
 
  private getParentIndex(i: number): number {
    return Math.floor((i - 1) / 2);
  }
 
  private getLeftChildIndex(i: number): number {
    return 2 * i + 1;
  }
 
  private getRightChildIndex(i: number): number {
    return 2 * i + 2;
  }
 
  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
 
  private heapifyUp(): void {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      if (this.heap[index] >= this.heap[parentIndex]) break;
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
 
  private heapifyDown(): void {
    let index = 0;
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
 
      if (
        rightChildIndex < this.heap.length &&
        this.heap[rightChildIndex] < this.heap[smallerChildIndex]
      ) {
        smallerChildIndex = rightChildIndex;
      }
 
      if (this.heap[index] <= this.heap[smallerChildIndex]) break;
 
      this.swap(index, smallerChildIndex);
      index = smallerChildIndex;
    }
  }
 
  push(value: T): void {
    this.heap.push(value);
    this.heapifyUp();
  }
 
  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
 
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.heapifyDown();
    return minValue;
  }
 
  peek(): T | undefined {
    return this.heap[0];
  }
 
  size(): number {
    return this.heap.length;
  }
 
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
}

import { MinHeap } from '@/types/Heap';
 
function minOperations(nums: number[], k: number): number {
  // handle edge case
  if (nums.length < 2) {
    return -1;
  }
 
  // declare new nums array
  const heap = new MinHeap<number>();
 
  for (let num of nums) {
    heap.push(num);
  }
 
  let count = 0;
  // run while loop until array length smaller than h
  // check whether all new nums larger or equal to k
  while (heap.size() >= 2 && heap.peek()! < k) {
    const x = heap.pop()!;
    const y = heap.pop()!;
    const newNum = Math.min(x, y) * 2 + Math.max(x, y);
 
    heap.push(newNum);
    count++;
  }
 
  // return minimum operation count
  return heap.peek()! < k ? -1 : count;
}