o2o网站建设咨询,小程序制作软件,网站职业培训学校,广州app开发服务用的是顺序存储二叉树#xff0c;也就是数组实现的二叉树#xff0c;遍历的时候按照的是二叉树的形式 代码实现
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};heapS… 用的是顺序存储二叉树也就是数组实现的二叉树遍历的时候按照的是二叉树的形式 代码实现
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 (j1 length arr[j] arr[j1]){//说明左子节点小于右子节点j; //j 指向右子节点}if (arr[j] temp){//如果子节点大于父节点arr[i] arr[j];//把较大的值附给当前节点i j; // i指向j继续循环比较}else {break;}}arr[i] temp;}
}
