SOURCE

// O(nlogk)

    // function GetLeastNumbers_Solution(input, k) {
    //   if (k > input.length) {
    //     return [];
    //   }
    //   createHeap(input, k);
    //   for (let i = k + 1; i < input.length; i++) {
    //     // 当前值比最小的k个值中的最大值小
    //     if (input[i] < input[0]) {
    //       [input[i], input[0]] = [input[0], input[i]];
    //       ajustHeap(input, 0, k);
    //     }
    //   }
    //   return input.splice(0, k);
    // }

    // // 构建大顶堆
    // function createHeap(arr, length) {
    //   for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
    //     ajustHeap(arr, i, length);
    //   }
    // }

    // function ajustHeap(arr, index, length) {
    //   for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
    //     if (i + 1 < length && arr[i + 1] > arr[i]) {
    //       i++;
    //     }
    //     if (arr[index] < arr[i]) {
    //       [arr[index], arr[i]] = [arr[i], arr[index]];
    //       index = i;
    //     } else {
    //       break;
    //     }
    //   }
    // }

function getLargestKNum(arr, k) {
  if (k > arr.length) {
    return [];
  }
  createHeap(arr, k);
  for (let i = k; i < arr.length; i++) {
    // 当前值比堆顶小
    if (arr[i] < arr[0]) {
      [arr[i], arr[0]] = [arr[0], arr[i]];
      ajustHeap(arr, 0, k);
    }
  }
  
  // 最小的k个
  return arr.splice(0, k);

  // 第k小的一个
  return arr[0];
}

// 构建大顶堆
function createHeap(arr, length) {
  // 从第一个非叶子节点开始，找到（改节点，左子、右子）最大的，和该节点交换 adjustHeap
  // 循环--，（右->左，下->上），前k个都堆化
  for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
    ajustHeap(arr, i, length);
  }
}

// logk  
function ajustHeap(arr, index, length) {
  // 左子节点i = 2 * index + 1, 完成后去下一层 i = 2*i+1
  for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {

    // 如果左子>左子，i++，因为要取大的子 和该节点交换
    if (i + 1 < length && arr[i + 1] > arr[i]) {
      i++;
    }
    if (arr[index] < arr[i]) {
      [arr[index], arr[i]] = [arr[i], arr[index]];

      // index = i，保证改节点及以下是一个堆
      index = i;
    } else {
      break;
    }
  }
}

    const arr = [5,3,7,1,8,2,9,4,7,2,6,6];

    console.log(getLargestKNum(arr, 4))