排序算法|堆排序

2022-4-26

堆其实是一种特殊的树。只要满足这两点，它就是一个堆。

堆是一个完全二叉树。完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。也可以说：堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作大顶堆。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作小顶堆。

实现思路：

整体主要由构建初始堆与交换堆顶元素并重建堆两部分组成。

其中构建初始堆经推到复杂度为O(n)
交换堆顶元素并重建堆，将循环n - 1次，每次都是从根节点往下循环查找，所以每一次时间是logn，总时间：logn(n-1) = nlogn-logn;
即时间复杂度为O(nlogn)

步骤：

构建大顶堆，堆顶为n个元素的最大值（从第一个非叶子节点开始（len/2） -1）

function buildMaxHeap(arr) { //建立大顶堆

len = arr.length;

for (let i = Math.floor(len/2)-1; i >= 0 ; i--) {//从第一个非叶子节点开始

heapify(arr, i);

}

将堆顶和末尾元素交换，使剩余n-1个元素序列又重新构成一个新的大顶堆（从交换后的堆顶开始“堆化”）

for (var i = arr.length - 1; i > 0; i--) {

swap(arr, 0, i);

len--;

heapify(arr, 0);

}

var len;
function buildMaxHeap(arr) { //建立大顶堆
  len = arr.length;
  for (let i = Math.floor(len/2); i >= 0 ; i--) {//从第一个非叶子节点开始
    heapify(arr, i);
  }
}
function heapify(arr, i) {
  var left = 2 * i + 1,
    right = 2 * i + 2,
    largest = i;//设置堆顶元素为largest
  
  if (left < len && arr[left] > arr[largest]) {//界限：left和right最多等于len-1，即数组的末尾元素
    largest = left;
  }

  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {//如果左右子节点找到largest
    swap(arr, i, largest);//交换
    heapify(arr, largest);//进入largest的索引递归
  }
}
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
function heapSort(arr) {
  buildMaxHeap(arr);//初始化大顶堆
  for (var i = arr.length - 1; i > 0; i--) {//从最后一个元素开始与堆顶交换，
    swap(arr, 0, i);
    len--;//将已经交换的最大元素排除
    heapify(arr, 0);
  }
  return arr;
}

阅读剩余

作者：chun

链接：https://chun53.top/977.html

文章版权归作者所有，未经允许请勿转载。

THE END