堆排序的过程
堆父节点和子节点
- parent(3) = (i - 1) / 2;
- c1(5) = 2 * i + 1;
- 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进行heapify()，2与7进行交换，然后对结点4进行heapify，6与4进行交换，最后1与7交换，我们看看最后的结果
我们考虑下，关于堆的定义：是一个完全二叉树、父节点全部大于等于或者全部小于等于子节点
我们看下图，可以看出明明5和3是4的子节点，为什么4还小于6呢？
同理，5和2也是1的子节点，为什么1还小于5呢？
这说明了我们对于堆的建立出现了错误，难道是我们的heapify出现了错误，我们从头开始分析一下：
首先，当我们将3和6进行交换时，这时候我们仅仅改变的是3-5-6之间的关系，也就是合理的，继而我们以2为父节点，改变2-5-7之间的关系，也是合理的，
当我们对以节点4进行heapify时，我们会将6和4的位置进行调换
这时候，聪明的你有没有看出什么错误导致的我们的建堆错误？
答案是：当我们对结点4进行heapify时，将4转变至子节点，破坏了下面这个小堆
也就是，对于交换后，我们原来排序好的堆，就失去了稳定性，有什么办法能让我们原来排序的堆也是顺序的嘛？
聪明的你可能想到了，我们再一次进行heapify不就可以了，对，我们只需要对交换完之后的节点再一次使用heapify，也就是对于上图中进行heapify，得到如下
按照上面的想法，我们对节点1再一次进行heapify
这时候聪明的你，能不能想到我们的heapify少了点什么？
对，我们一开始的heapify少了对改变的子节点进行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); heapify(tree, n, max); } }
这时候我们的堆就建好了，我们可以进行下一步操作，堆排序
进行堆排序
对于堆排序，我们使用方法是：
每次将root与末尾的进行交换，然后对root进行heapify
我们看一下图示：
依次进行这种操作，我们最后得到的数组就是从小到大排序好的
注意：我们进行堆排序的时候，我们每次重新对节点使用heapify时，我们已经排序好了一个7，所以下一次进行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]); } }
