文章链接：日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
day48 堆排序 48.1 基本思路（1）大/小顶堆：每一个结点值都大于（小于）或等于孩子结点（实际上堆可以看成一颗完全二叉树）
（2）堆排序：利用这种堆的结构进行排序。如：对一个待排序列进行堆排序，需要先建堆（大顶堆），这时我们可以结合大顶堆的性质，取堆顶元素，取完堆顶元素后我们要重新调整大顶堆，再取堆顶数据再调整。在这个过程会涉及建堆，调整堆。所以要清楚这个堆有什么特点。
（3）堆：堆通常是一个可以被看做一棵完全二叉树的数组对象，因为堆可以看做是完全二叉树。则完全二叉树的特点：
a. 假设完全二叉树总节点数为n,则会有n/2个父节点
b. 对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) ，若2i>n,则结点i无左孩子，否则左孩子的结点为2i;如果2i+1>n,则结点i无右孩子，否则右孩子结点为2i+1
c. 完全二叉树的叶子结点也只能出现最后两层上
对于上面完全二叉树中（1）（2）中这个关系对我们进行堆排序进行构建堆，调整堆很关键。
(4)手动模拟构造堆：（这里i从1开始）
step1：对待排序数组按完全二叉树方式排列出来，自下往上逐步调整。先找到最后一个父节点n/2=4,判断i=4结点的孩子结点较大是否大于父节点，若大于则交换数据
step2-5：继续向上调整，但是在调整的过程中，可能回破坏下一级的大顶堆结构，所以还需要向下检查，如图中step4中i=1中53和87交换后，破坏了i=3处大顶堆的结构，则需要调整。
48.2 代码思路（1）结合文章的代码，需要注意的是这里i不是从1开始的，是从0开始的，则i其左孩子结点为2i+1，右孩子结点为2i
（2）先看adjustHeap(int paraStart, int paraLength)这个方法中，for循环是根据i处父节点向下去筛选最大的结点，第一个if是判断父节点的孩子结点中的最大结点 第二个if则是与父节点进行比较，是否大于父节点，若大于则需要交换位置，在这里，交换了父节点并不能确定父节点的最终位置，因为可能交换了位置会破坏下面的堆结构，还需要向下级继续调整。
（3）堆排序方法heapSort()，第一个for循环是构建初始堆，第二个循环则是在循环输出堆排序，我们从代码也可以看到，每取一个堆顶元素则要进行一次堆调整、
public void heapSort() {
//构建堆
DataNode tempNode;
for (int i = length/2 -1; i >= 0; i--) {
adjustHeap(i, length);
}
System.out.println("The initial heap: " + this + "rn");
// Step 2. Swap and reconstruct.
for (int i = length-1; i > 0; i--) {
tempNode = data[0];
data[0] = data[i];
data[i] = tempNode; //把最大的数放在堆底
adjustHeap(0, i); //调整剩余的堆
System.out.println("Round " + (length - i) + ": " + this);
}
}
public void adjustHeap(int paraStart, int paraLength) {
DataNode tempNode = data[paraStart];
int tempParent = paraStart;
int tempKey = data[paraStart].key;
//这里i是从0开始的 注意
for (int tempChild = paraStart*2 + 1; tempChild < paraLength; tempChild = tempChild*2 + 1) {
if (tempChild + 1 < paraLength) {
//右孩子大于左孩子
if (data[tempChild].key < data[tempChild+1].key) {
tempChild++; //找到孩子结点中最大的结点与双亲比较
}
}
System.out.println("The parent position is " + tempParent + " and the child is " + tempChild);
if (tempKey < data[tempChild].key) {
//将孩子结点中较大的与父节点交换位置
data[tempParent] = data[tempChild];
System.out.println("Move " + data[tempChild].key + " to position " + tempParent);
tempParent = tempChild; //修改父节点位置，可能交换位置会破坏结构 继续向下筛选
}else {
break; //筛选结束
}
}
data[tempParent] = tempNode; //将这个父节点放在这一趟堆排序的最终位置
}
代码运行结果：
-------heapSortTest------- I am a data array with 7 items. (5, if) (3, then) (6, else) (10, switch) (7, case) (1, for) (9, while) The parent position is 2 and the child is 6 Move 9 to position 2 The parent position is 1 and the child is 3 Move 10 to position 1 The parent position is 0 and the child is 1 Move 10 to position 0 The parent position is 1 and the child is 4 Move 7 to position 1 The initial heap: I am a data array with 7 items. (10, switch) (7, case) (9, while) (3, then) (5, if) (1, for) (6, else) The parent position is 0 and the child is 2 Move 9 to position 0 The parent position is 2 and the child is 5 Round 1: I am a data array with 7 items. (9, while) (7, case) (6, else) (3, then) (5, if) (1, for) (10, switch) The parent position is 0 and the child is 1 Move 7 to position 0 The parent position is 1 and the child is 4 Move 5 to position 1 Round 2: I am a data array with 7 items. (7, case) (5, if) (6, else) (3, then) (1, for) (9, while) (10, switch) The parent position is 0 and the child is 2 Move 6 to position 0 Round 3: I am a data array with 7 items. (6, else) (5, if) (1, for) (3, then) (7, case) (9, while) (10, switch) The parent position is 0 and the child is 1 Move 5 to position 0 Round 4: I am a data array with 7 items. (5, if) (3, then) (1, for) (6, else) (7, case) (9, while) (10, switch) The parent position is 0 and the child is 1 Move 3 to position 0 Round 5: I am a data array with 7 items. (3, then) (1, for) (5, if) (6, else) (7, case) (9, while) (10, switch) Round 6: I am a data array with 7 items. (1, for) (3, then) (5, if) (6, else) (7, case) (9, while) (10, switch) Result I am a data array with 7 items. (1, for) (3, then) (5, if) (6, else) (7, case) (9, while) (10, switch)总结：
今天学习了堆排序，我认为学习堆排序最重要的是建堆，自己能够去手动模拟出建堆的过程，堆排序近似完全二叉树，在实现堆排序的过程中也用到了完全二叉树的特点。对比昨天学习的选择排序，其实堆排序也是选择排序的一种，但是堆排序的选择相比昨天的直接选择排序改进了许多。
