时间：2020-10-08 13:28:22 | 栏目：JAVA代码 | 点击：次
学习堆排序，首先需要明白堆的概念，堆是一个数组。可以近似当做完全二叉树的数组存储方式。但是跟他还有其他的性质，就是类似于二叉排序树。有最大堆跟最小堆之分，最大堆是指根节点的值都大于子节点的值，而最小堆的是根节点的值小于其子节点的值。堆排序一般用的是最大堆，而最小堆可以构造优先队列。堆里面有一个方法是用来维护堆的性质，也就是我们下面代码中的maxheap方法，这是维护最大堆性质的方法，第一个参数就是堆也就是数组，第二个参数是调整堆的具体节点位置，可能这个节点的值不符合最大堆的性质，那么这个值得位置就作为参数，而size其实是堆内实际存储的有效元素个数。可能数组的长度就是堆内实际存储的元素个数，但是不一定所有的数据我们都需要进行构建最大堆。算法导论中说的得到左子结点是2xi但是我们数组是从0开始计数的，所以左子结点就成了2xi+1，buildheap就是构建一个最大堆，我们去2分之长度的原因是，这些点的子节点都是叶子节点，所以我们通过从下向上进行排序来构建一个最大堆。保证了我们堆内所有节点都满足最大堆性质。最后堆排序就是把第一个节点取出来，将剩下的节点再进行堆排序，再取出根节点。这样保证我们每次取出都是最大值。
public static void main(String[] args) {
int[] heap=new int[]{4,1,5,3,7,12,65,7};
HeapSort hs=new HeapSort();
hs.sort(heap);
for (int i = 0; i < heap.length; i++) {
System.out.println(heap[i]);
}
}
}