堆排序是什么？

95次阅读

没有评论

共计 1486 个字符，预计需要花费 4 分钟才能阅读完成。

堆排序是一种常见的排序算法，时间复杂度是 O(nlgn)，与归并排序一样，但它又与插入排序一样具有 空间原址性：任何时候都只需要常数个额外的元素空间存储临时数据。

什么是堆？

一般堆用数组存储，表现出近似完全二叉树形式，树上的每一个结点对应数组中的一个元素。除了最底层外，该树是完全充满的且从左至右填充。

最大堆和最小堆

最大堆：除了根以外的所有节点 i 都要满足A[parent(i)]>=A[i]，即堆中最大元素是根节点。
最小堆：除了根以外的所有节点 i 都要满足A[parent(i)]<=A[i]，即堆中最小元素是根节点。

堆中节点的高度

与二叉树的高度相同，定义为该节点到叶节点最长简单路径上边的数目。则包含 n 个元素的堆其高度为 lgn。

维护堆的性质与方法（数组下标都从 1 开始）

maxHeapify

时间复杂度为 O(lgn)。通过让 A[i] 的值在最大堆中“逐级下降”，从而使得以下标 i 为根节点的子树重新遵循最大堆性质。代码如下:

function maxHeapify(arr, i) {
  let largest;
  let left = i * 2; // leftChild
  let right = i * 2 + 1; // rightChild
  if(left <= arr.length && arr[i] < arr[left] ) {largest = left;} else {largest = i;}
  if(right <= arr.length && arr[largest] < arr[right] ) {largest = right;}
  if (largest !== i) { // 把左右子节点中最大的元素与当前节点 i 交换
    arr[i] = arr[i] + arr[largest];
    arr[largest] = arr[i] - arr[largest];
    arr[i] = arr[i] - arr[largest];
    maxHeapify(arr, largest);
  }
}

buildMaxHeap

时间复杂度为 O(n)。用 自底向上 的方法利用 maxHeapify 把大小为 n 的数组转换为最大堆。

因为最后一个叶节点序号为 n，则其父节点序号为 n /2, 所以子数组 [n/2+1,....,n] 都是堆的叶节点，所以循环从 n / 2 开始递减到 1，每一次都保证节点 i +1,i+2…,n 都是一个最大堆的根节点的性质。

function buildMaxHeap(arr) {for (var i = arr.length / 2; i >= 1; i--) {maxHeapify(arr,i);
  }
}

heapSort: 堆排序算法。

有了上述两个函数方法，我们就可以实现堆排序。

先将数组 arr 建为一个最大堆，因为最大堆的根节点总是最大的。

通过把它与 arr[n]互换可以得到正确位置，保证 arr[n]总是当前堆中最大元素，然后将 arr[n]存储到新的数组中。

可以算出时间复杂度为 O(nlgn)。

function heapSort(arr) {let arrSort = [];
  buildMaxHeap(arr);  // 先建一个最大堆
  let length = arr.length;
  for (var i = length; i >= 2; i--) {arr[1] = arr[i];
    arrSort.push(arr[i]);
    maxHeapify(arr, 1); // 每次交换后重新维护最大堆，复杂度为 O(lgn)
  }
  arrSort.push(arr[1]);
  return arrSort;
}