- 默认将arr数组按照广度优先遍历的方式形成一个二叉树,该树满足以下特性:
- 如果含有子节点leftChildIndex的父节点的序号为parentIndex,arr总长度为len,则
- 对于任意parentIndex,均满足 parentIndex <= (len-1)/2,即叶子节点最多有 len - (len-1)/2
- leftChildIndex = 2*parentIndex + 1, 这是由每一层x的结点数都是 Math.pow(2, x)决定的
- 从父节点最大的序号开始依次遍历各个子树,使得每个子树都是大根堆结构,需要先从子节点中找到最大的值,然后和父节点比对,如果交换了数据,还需要向下调整大根堆结构
- 每次将大根堆的头结点的数据和最后一个叶子结点交换,交换后剪掉该叶子结点,并从头结点调整大根堆结构,循环直到大根堆只有一个结点为止。
package com.example.demo;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {10,2,3,6,7,4,5,7,8,9};
heapSort(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
private static void heapSort(int[] arr) {
int len = arr.length;
//(arr.length-1)/2的index是第一个有子结点的父结点
for(int i=(len-1)/2; i>=0;i--) {
adjustHeap(arr, i, len);
}
for(int i = len-1;i>0;i--) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
}
/**
*
* @param arr 将arr调成成为 adjustLength 内的、子树的头结点序号是parentIndex的大根堆,
* @param parentIndex 需要调整arr的范围,超过这个范围说明已经排序好了
* @param adjustLength 子树的头结点序号是parentIndex,调整后该子树为大根堆
*/
private static void adjustHeap(int[] arr, int parentIndex, int adjustLength) {
int selectedIndex = parentIndex*2+1;
int needAdjustNum = arr[parentIndex];
while(selectedIndex < adjustLength) {
int rightChildIndex = selectedIndex+1;
if(rightChildIndex<adjustLength && arr[rightChildIndex] > arr[selectedIndex]) {
selectedIndex = rightChildIndex;
}
if(needAdjustNum >= arr[selectedIndex]) {
break;
} else {
arr[parentIndex] = arr[selectedIndex];
parentIndex = selectedIndex;
selectedIndex = parentIndex*2+1;
}
}
arr[parentIndex] = needAdjustNum;
}
}