

用的是顺序存储二叉树,也就是数组实现的二叉树,遍历的时候按照的是二叉树的形式













代码实现
package tree;
import java.util.Arrays;
public class HeapSort {
public static void main(String []args){
int [] arr = { 4, 6, 8, 5, 9,-1,-1,2,4,5,6,88};
heapSort(arr);
}
//编写堆排序方法
public static void heapSort(int arr []){
System.out.println("堆排序");
int temp = 0;
//建堆(第一次整体是无序的,需要从下往上,从左往右开始建大顶堆)
for (int i = arr.length / 2 -1; i >= 0 ; i--) {
adjustHeap(arr,i,arr.length);
}
//不断交换重构大顶堆(因为第一次重构的时候已经有序,交换后只是root节点无序,只需要把root节点的值放到他该去的位置即可,所以从顶点往下开始重构,然后循环)
for (int j = arr.length -1; j > 0; j--) {
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr,0,j);
}
System.out.println("数组:"+ Arrays.toString(arr));
}
//将数组(二叉树),调整成大顶堆
/** * 功能:{4, 6, 8, 5, 9} => i = 1 以6为非叶子节点的 子树 调整成大顶堆{4, 9, 8, 5, 6}(让6与两个孩子比较,比 6 大就交换), * 然后继续调整传入i = 0,以4位节点的树调整成大顶堆(让4与两个孩子比较,比 4 大就交换) * @param arr 待调整的数组 * @param i 非叶子节点在数组中的索引 * @param length 对多少个元素进行调整(调整好的就不进行调整),length不断减少 */
public static void adjustHeap(int arr [], int i, int length){
int temp = arr[i]; //保存此非叶子节点
//开始调整
//说明k是i的左子节点
for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
if (j+1 < length && arr[j] < arr[j+1]){ //说明左子节点小于右子节点
j++; //j 指向右子节点
}
if (arr[j] > temp){ //如果子节点大于父节点
arr[i] = arr[j];//把较大的值附给当前节点
i = j; //!!! i指向j,继续循环比较
}else {
break;
}
}
arr[i] = temp;
}
}
还没有评论,来说两句吧...