算法 - 堆排序(大顶堆、小顶堆)

忘是亡心i 2023-07-03 06:15 44阅读 0赞

在这里插入图片描述

在这里插入图片描述

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

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码实现

  1. package tree;
  2. import java.util.Arrays;
  3. public class HeapSort {
  4. public static void main(String []args){
  5. int [] arr = { 4, 6, 8, 5, 9,-1,-1,2,4,5,6,88};
  6. heapSort(arr);
  7. }
  8. //编写堆排序方法
  9. public static void heapSort(int arr []){
  10. System.out.println("堆排序");
  11. int temp = 0;
  12. //建堆(第一次整体是无序的,需要从下往上,从左往右开始建大顶堆)
  13. for (int i = arr.length / 2 -1; i >= 0 ; i--) {
  14. adjustHeap(arr,i,arr.length);
  15. }
  16. //不断交换重构大顶堆(因为第一次重构的时候已经有序,交换后只是root节点无序,只需要把root节点的值放到他该去的位置即可,所以从顶点往下开始重构,然后循环)
  17. for (int j = arr.length -1; j > 0; j--) {
  18. //交换
  19. temp = arr[j];
  20. arr[j] = arr[0];
  21. arr[0] = temp;
  22. adjustHeap(arr,0,j);
  23. }
  24. System.out.println("数组:"+ Arrays.toString(arr));
  25. }
  26. //将数组(二叉树),调整成大顶堆
  27. /** * 功能:{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不断减少 */
  28. public static void adjustHeap(int arr [], int i, int length){
  29. int temp = arr[i]; //保存此非叶子节点
  30. //开始调整
  31. //说明k是i的左子节点
  32. for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
  33. if (j+1 < length && arr[j] < arr[j+1]){ //说明左子节点小于右子节点
  34. j++; //j 指向右子节点
  35. }
  36. if (arr[j] > temp){ //如果子节点大于父节点
  37. arr[i] = arr[j];//把较大的值附给当前节点
  38. i = j; //!!! i指向j,继续循环比较
  39. }else {
  40. break;
  41. }
  42. }
  43. arr[i] = temp;
  44. }
  45. }

发表评论

表情:
评论列表 (有 0 条评论,44人围观)

还没有评论,来说两句吧...

相关阅读