安琪拉教鲁班学堆排序

77 阅读 0 评论 51 点赞

我是靠谱客的博主殷勤心情，最近开发中收集的这篇文章主要介绍安琪拉教鲁班学堆排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

《安琪拉与面试官二三事》系列文章
一个HashMap能跟面试官扯上半个小时
一个synchronized跟面试官扯了半个小时

《安琪拉教鲁班学算法》系列文章

安琪拉教鲁班学算法之动态规划

安琪拉教鲁班学算法之BFS和DFS

安琪拉教鲁班学算法之堆排序
《安琪拉教妲己学分布式》系列文章
安琪拉教妲己分布式限流

堆排序属于算法中比较常见的一种，本文希望通过使用王者峡谷二位脆皮英雄对话的方式讲解动态规划，让大家在轻松愉快的氛围中搞懂堆排序。

鲁班：安琪拉，你知道堆吗？

安琪拉：知道啊！堆在计算机里是一种数据结构，是一个近似完全二叉树，当然咯，在JVM内存模型中堆也是存放运行时数据的区域，这里说的堆指的是数据结构中的堆结构。

鲁班：那堆排序又是怎么一回事？

安琪拉：因为堆有一个非常????的特性，堆中选任一节点A，它的左右子节点的值都大于A的值（小根堆），或者左右子节点的值都大于A的值（大根堆），以小根堆为例，如下图所示：

安琪拉：因为堆的这个特性，因此可以用于做排序，以及解决一些类型top K的问题。

鲁班：你给我具体讲讲堆排序怎么实现的呗。

安琪拉：好的。首先说一下堆排序元素的存储方式：

构建节点类，节点类中包含左节点和右节点的指针/引用，通过根节点遍历；
使用数组维护堆，其中当前节点的下标为 i , 左节点下标为 i * 2 + 1, 右节点下标为 i * 2 + 2, 父节点下标为

（i - 1） / 2.

因此????这张图在数组中是 int[] arr = [3, 7, 16, 10, 21, 23, 37, 15], 将下标都标注上去之后，如下图所示：

那么我们要正式开始了，堆排序主要分三步：

第一步：构造堆结构
第二步：保存根节点，调整剩下堆，迭代进行

开始第一步，来看一下给定一个数组，如何将数组调整成符合堆特性的数组（子节点都比当前节点大）。

例如：现在数组数据为： 9, 3, 7, 6, 5, 1, 10, 2 刚开始的树型结构如下图所示：

我们需要把这颗树构造成最小堆，需要做些调整，使得满足最小堆的特性：任一节点A的左右子节点都比A大。

思考第一个问题：从哪里开始调整？如何调整。

既然要满足任一节点A的左右子节点都比A大，那首先节点需要有子节点才行，那我们从最后一个不是叶子节点的元素开始，（叶子节点没有左右子节点），最后一个不为叶子节点的元素是 6 这个数，然后让它跟左右节点比较，与左右节点中小的交换，这样局部满足最小堆特性了，如下图：

然后往上走，开始调整元素 7，让7 与左右子节点比较，如下图：

然后是元素3，最后是根节点9，如下图：

另外很重要的一点，局部调整完成之后，需要递归子节点是否同意满足最小堆特性，如上图，1 和 9交换之后，9与子节点不满足最小堆特性，也要做调整，最后结果如下：

这个最小堆的构建过程通过代码编写，如下：

private void buildMinHeap(int[] arr, int len) {
  //因此前面说从最后一个不为叶子节点的元素开始，这里((len - 1) -1) / 2 就是最后一个不为叶子节点的元素的下标
  //因为最后一个节点下标为len -1，最后一个叶子节点的父节点就是最后一个有子节点的元素 ，父节点下标为（len -1 -1） 很多程序直接从 (len -1) /2 开始也是可以的，不影响最终结果，因为很有可能(len -1) /2 是个叶子节点
  for (int i = ((len - 1) -1) / 2; i >= 0; i--) {
    heapify(arr, i, len);
  }
}

private void heapify(int[] arr, int i, int len) {
  if (i >= len) return;

  int min = i;
  //求左子节点下标 c1
  int c1 = 2 * i + 1;
  //求右子节点下标 c2
  int c2 = 2 * i + 2;
	
  //取最小者 和 节点替换
  if (c1 < len && arr[c1] < arr[min]) {
    min = c1;
  }
  if (c2 < len && arr[c2] < arr[min]) {
    min = c2;
  }

  //如果当前节点子节点中有比自己小的，替换，然后调整子树。
  if (min != i) {
    swap(arr, i, min);
    heapify(arr, min, len);
  }
}

上面构建的过程说完了，后面排序的部分就很简单了。构建完成的堆，根节点是最小值，我们第k = 1次可以通过将根节点和数组最后一个节点进行替换，把根节点存储起来，把如下图：

现在数组最后一个元素是最小值，我们对堆的前 n -k 个元素做调整，让它满足最小堆，然后不断把根节点和数组倒数第n-k个元素交换，最后数组就成了一个倒叙排列的数组，如果需要顺序排列，就按照大根堆构建，然后不断调整就可以了，实现完整代码如下：

public int[] dumpSort(int[] arr){
  int len = arr.length;
  //构建最小堆
  buildMinHeap(arr, len);

  //将根节点保存到数组最后，调整堆
  for (int i = len - 1; i >= 0; i--) {
    swap(arr, 0, i);
    heapify(arr, 0, --len);
  }
  return arr;
}

private void buildMinHeap(int[] arr, int len) {
  /**
         * 因此前面说从最后一个不为叶子节点的元素开始，这里((len - 1) -1) / 2 就是最后一个不为叶子节点的元素的下标
         * 因为最后一个节点下标为len -1，最后一个叶子节点的父节点就是最后一个有子节点的元素 ，父节点下标为（len -1 -1）
         * 很多程序直接从 (len -1) /2 开始也是可以的，不影响最终结果，因为很有可能(len -1) /2 是个叶子节点
         */
  for (int i = ((len - 1) -1) / 2; i >= 0; i--) {
    heapify(arr, i, len);
  }
}

private void heapify(int[] arr, int i, int len) {
  if (i >= len) return;

  int min = i;
  //求左子节点下标 c1
  int c1 = 2 * i + 1;
  //求右子节点下标 c2
  int c2 = 2 * i + 2;

  //取最小者 和 节点替换
  if (c1 < len && arr[c1] < arr[min]) {
    min = c1;
  }
  if (c2 < len && arr[c2] < arr[min]) {
    min = c2;
  }

  //如果当前节点子节点中有比自己小的，替换，然后调整子树。
  if (min != i) {
    swap(arr, i, min);
    heapify(arr, min, len);
  }
}

private void swap(int[] arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}