【面试知识点】史上最全面讲解----堆排序

堆放排序的过程

1. parent(3) = (i - 1) / 2;
2. c1(5) = 2 * i + 1;
3. c2(6) = 2 * i + 2;

在建堆过程中，我们需要知道一个函数heapify()[这里的heapify不代表最终版本]

public static void heapify(int[] tree, int n, int i) { if (i >= n) {return;}int max = i;int c1 = 2 * i + 1;int c2 = 2 * i + 2;if (c1 < n && tree[c1] > tree[max]) {max = c1;}if (c2 < n && tree[c2] > tree[max]) {max = c2;}if (max != i) {duiSwap(tree, max, i);}}

该函数用于3、5、6中，最大数与3交换

我们用heapify作为每个结点，这样我们就能得到一个完整的堆吗？

让我们往下看。3和6交换后，我们将交换结点2、2和7，然后交换结点4、6和4，最后1和7。让我们看看最终的结果

让我们考虑一下堆的定义：一棵完全二叉树，父节点大于或小于或等于子节点

如下图所示，我们可以看到明明5和3是4的子节点，为什么4还小于6？

同样，5和2也是1的子节点，为什么1还小于5？

这说明我们对堆的建立有错误，是不是我们的heapify有错误，我们从头开始分析:

首先，当我们交换3和6时，我们只改变3-5-6之间的关系，这是合理的，然后我们以2为父节点，改变2-5-7之间的关系，

当我们用节点4heapify时，我们将更换6和4的位置

这个时候，聪明的你有没有看到我们的建堆错误是什么错误造成的？

答案是:当我们对结点4进行heapify时，我们将4转换为子节点，破坏以下小堆

也就是说，交换后，我们原来排序好的堆就失去了稳定性。有没有办法让我们原来排序好的堆也是有序的？

聪明的你可能会想，我们可以再次heapify。是的，我们只需要在交换节点后再次使用heapify，即上图中的heapify，得到以下内容

根据以上想法，我们将再次在节点1中heapifyy

这个时候聪明的你，能不能想到我们的heapify少了点什么？

是的，我们最初的heapify没有heapify来改变子节点，我们是如何实现的？

这里只需递归即可，即对变化的子节点进行heapifyy

public static void heapify(int[] tree, int n, int i) {if (i >= n) {return;}int max = i;int c1 = 2 * i + 1;int c2 = 2 * i + 2;if (c1 < n && tree[c1] > tree[max]) {max = c1;}if (c2 < n && tree[c2] > tree[max]) {max = c2;}if (max != i) {duiSwap(tree, max, i);heapify(tree, n, max);}}

这时，我们的堆就建好了，我们可以进行下一步的操作，堆排序

我们使用堆排序的方法是：

每次将root与末尾交换，然后对root进行heapifyy

让我们看看图表：

这种操作依次进行，我们最终得到的数组从小到大排序良好

注：当我们进行堆排序时，每次我们重新使用heapify时，我们都会对节点进行排序，所以下次我们进行heapify时，n(即heapify的范围)可以直接删除一个7，后面也是如此

public static void duiSwap(int[] tree, int i, int j) {int x = tree[i];tree[i] = tree[j];tree[j] = x;}public static void heapify(int[] tree, int n, int i) {            if (i >= n) {return;}int max = i;int c1 = 2 * i + 1;int c2 = 2 * i + 2;if (c1 < n && tree[c1] > tree[max]) {max = c1;}if (c2 < n && tree[c2] > tree[max]) {max = c2;}if (max != i) {duiSwap(tree, max, i);heapify(tree, n, max);}}public static void bulidDui(int[] tree, int n) {int last = n - 1;int parent = (last - 1) / 2;for (int i = parent; i >= 0; i--) {heapify(tree, n, i);}}public static void duiSort(int[] tree, int n) {bulidDui(tree, n);for (int i = n - 1; i >= 0; i--) {duiSwap(tree, i, 0);heapify(tree, i, 0);}}public static void main(String[] args) {int[] tree = new int[] { 2, 5, 3, 1, 10 };int n = tree.length;duiSort(tree, n);for (int i = 0; i < n; i++) {System.out.println(tree[i]);}}