1. let findKthLargest = function(nums, k) {
  2.     // 从 nums 中取出前 k 个数，构建一个小顶堆
  3.     let heap = [,], i = 0
  4.     while(i < k) {
  5.        heap.push(nums[i++]) 
  6.     }
  7.     buildHeap(heap, k)
  9.     // 从 k 位开始遍历数组
  10.     for(let i = k; i < nums.length; i++) {
  11.         if(heap[1] < nums[i]) {
  12.             // 替换并堆化
  13.             heap[1] = nums[i]
  14.             heapify(heap, k, 1)
  15.         }
  16.     }
  18.     // 返回堆顶元素
  19.     return heap[1]
  20. };
  22. // 原地建堆，从后往前，自上而下式建小顶堆
  23. let buildHeap = (arr, k) => {
  24.     if(k === 1) return
  25.     // 从最后一个非叶子节点开始，自上而下式堆化
  26.     for(let i = Math.floor(k/2); i>=1 ; i--) {
  27.         heapify(arr, k, i)
  28.     }
  29. }
  31. // 堆化
  32. let heapify = (arr, k, i) => {
  33.     // 自上而下式堆化
  34.     while(true) {
  35.         let minIndex = i
  36.         if(2*i <= k && arr[2*i] < arr[i]) {
  37.             minIndex = 2*i
  38.         }
  39.         if(2*i+1 <= k && arr[2*i+1] < arr[minIndex]) {
  40.             minIndex = 2*i+1
  41.         }
  42.         if(minIndex !== i) {
  43.             swap(arr, i, minIndex)
  44.             i = minIndex
  45.         } else {
  46.             break
  47.         }
  48.     }
  49. }
  51. // 交换
  52. let swap = (arr, i , j) => {
  53.     let temp = arr[i]
  54.     arr[i] = arr[j]
  55.     arr[j] = temp
  56. }

构建最小堆

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  8. class MinHeap {
  9.     constructor() {
  10.         this.heap = [];
  11.     }
  12.     getParentIndex(i) {
  13.         return (i - 1) >> 1; // 二进制
  14.     }
  15.     getLeftIndex(i) {
  16.         return i * 2 + 1;
  17.     }
  18.     getRightIndex(i) {
  19.         return i * 2 + 2;
  20.     }
  21.     shiftUp(index) {
  22.         if (index === 0) { return; }
  23.         const parentIndex = this.getParentIndex(index);
  24.         if (this.heap[parentIndex] > this.heap[index]) {
  25.             this.swap(parentIndex, index);
  26.             this.shiftUp(parentIndex);
  27.         }
  28.     }
  29.     swap(i1, i2) {
  30.         const temp = this.heap[i1];
  31.         this.heap[i1] = this.heap[i2];
  32.         this.heap[i2] = temp;
  33.     }
  34.     insert(value) {
  35.         this.heap.push(value);
  36.         this.shiftUp(this.heap.length - 1);
  37.     }
  38.     pop() {
  39.         this.heap[0] = this.heap.pop();
  40.         this.shiftDown(0);
  41.     }
  42.     shiftDown(index) {
  43.         const leftIndex = this.getLeftIndex(index);
  44.         const rightIndex = this.getRightIndex(index);
  45.         if (this.heap[leftIndex] < this.heap[index]) {
  46.             this.swap(leftIndex, index);
  47.             this.shiftDown(leftIndex);
  48.         }
  49.         if (this.heap[rightIndex] < this.heap[index]) {
  50.             this.swap(rightIndex, index);
  51.             this.shiftDown(rightIndex);
  52.         }
  53.     }
  54.     peek() {
  55.         return this.heap[0];
  56.     }
  57.     size() {
  58.         return this.heap.length;
  59.     }
  60. }
  62. // 大根堆排序
  64. let findKthLargest = function(nums, k) {
  65.     let h = new MinHeap();
  66.     nums.forEach(c => {
  67.         h.insert(c);
  68.         while(h.size()>k){
  69.             h.pop()
  70.         }
  71.     })
  73.     return h.peek();
  74. };

堆排序

https://github.com/sisterAn/JavaScript-Algorithms/issues/60