【算法】堆排序

堆排序

堆在存储形式上和完全二叉树的层序遍历一样

            50
      45          40
    20    25      35  30
  10  15

对堆中的节点按层进行编号，映射到数组中为：

[50, 45, 40, 20, 25, 35, 30, 10 15]

这样存储的堆有如下特点：

• 第 n 个元素的 左子节点 为 2*n+1
• 第 n 个元素的 右子节点 为 2*n+2
• 第 n 个元素的 父节点 为 Math.floor((n-1)/2)
• 最后一个非叶子节点为 Math.floor(arr.length/2)-1

算法题目

• 215.数组中的第 k 个最大元素.js

var findKthLargest = function (nums, k) {
  let heapSize = nums.length;
  buildMaxHeap(nums, heapSize); // 构建好了一个大顶堆
  // 进行下沉 大顶堆是最大元素下沉到末尾
  for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
    swap(nums, 0, i);
    --heapSize; // 下沉后的元素不参与到大顶堆的调整
    // 重新调整大顶堆
    maxHeapify(nums, 0, heapSize);
  }
  return nums[0];
  // 自下而上构建一颗大顶堆
  function buildMaxHeap(nums, heapSize) {
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      maxHeapify(nums, i, heapSize);
    }
  }
  // 从左向右，自上而下的调整节点
  function maxHeapify(nums, i, heapSize) {
    let l = i * 2 + 1;
    let r = i * 2 + 2;
    let largest = i;
    if (l < heapSize && nums[l] > nums[largest]) {
      largest = l;
    }
    if (r < heapSize && nums[r] > nums[largest]) {
      largest = r;
    }
    if (largest !== i) {
      swap(nums, i, largest); // 进行节点调整
      // 继续调整下面的非叶子节点
      maxHeapify(nums, largest, heapSize);
    }
  }
  function swap(a, i, j) {
    let temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }
};

参考

写给前端同学的题解，一文讲懂堆排序，解决 topK 问题