堆排序的关键是构建大(小)顶堆,堆顶元素就是最大(小)的元素,然后堆顶元素和末尾元素交换位置,再次堆化除最后一个元素外的其它元素,循环次过程即可完成排序。
翻译成代码如下:
public void sort(int a) {
for(int i = a.length - 1; i > 0; i--) {
buildHeap(a, i);
// 堆顶元素和最后一个元素交换,除过最后一个元素外其它元素再次构建大顶堆
swap(a, 0, i);
}
}
堆化过程
1、从序列最后一个非叶子节点开始
2、堆化规则:替换节点为当前节点和叶子节点中值最大的节点
3、倒序依次处理其它非叶子节点
4、须保证叶子节点也满足堆化规则
前置知识
1、堆是完全二叉树
2、满二叉树使用数组存储最省空间
3、若节点在数组中的下标为 n
,其左叶子节点在数组中的下标为 2 * n + 1
,右子节点下标为 2 * n + 2
,父节点下标为 (n - 2)/2
堆化过程图解
翻译成代码如下:
/**
* 构建大顶堆
*
* @param a 数组
* @param n 最后一个元素下标
*/
public static void buildHeap(int[] a, int n) {
// 从最后一个非叶子节点开始,倒序依次处理其它非叶子节点
for(int i = (n -1) / 2; i >=0; i--) {
heapify(a, n, i);
}
}
/**
* 堆化
*
* @param a 数组
* @param n 最后一个元素下标
* @param i 需要调整的父节点下标
*/
public static void heapify(int[] a,int n, int i) {
while (true) {
// 大顶堆规则:替换节点为当前节点和叶子节点中值最大的节点
int maxPos = i;
int l = 2 * i + 1;
if (a[l] > a[maxPos]) {
maxPos = l;
}
int r = 2 * i + 2;
if (a[r] > a[maxPos]) {
maxPos = r;
}
// 当前节点最大时退出
if (maxPos == i) {
return;
}
swap(a, maxPos, i);
// 保证叶子节点也满足堆化规则
i = maxPos;
}
}
public static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}