树结构的实际应用

堆排序

堆排序的介绍

• 堆排序利用堆这中数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它是不稳定排序
• 堆是具有以下性质的完全二叉树:每个节点的值都大于或等于其它左右孩子节点的值,称为大顶堆,注意:没有要求节点的左孩子和右孩子的值的大小关系.
• 每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆
• 大顶堆举例说明
• 
  大顶堆特点:arr[i]>arr[2i+1]&&arr[i]>=arr[2i+2]
• 小顶对举例说明
• 
• 小顶堆特点:arr[i]<=arr[2i+1]&&arr[2i+2]
• 一般升序排序我们采用大顶堆,降序排序我们采用小顶堆

堆排序的思想

堆排序的基本思想

1. 将待排序的序列构造成一个大顶堆
2. 此时,整个序列的最大值就是堆顶的根节点
3. 将其与末尾元素进行交换,此时末尾就是最大值
4. 然后将剩余的n-1个元素重写构造成一个大顶堆,这样就会得到n个元素的次小值,如此反复的执行,便能得到一个有序序列了.
5. 可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列.

堆排序步骤图解说明

1. 构造初始堆,将给定一个无序序列构造成一个大顶堆(一般升序大顶堆,降序小顶堆)
2. 原始数组[4,6,8,5,9]

• 假设给定无序序列结构如下
  
• 此时我们从最后一个非叶子节点开始(叶节点自然不用调整,第一个非叶子节点arr.length/2-1=5/2-1=1,也就是下面的6节点,)从左至右,从上至下进行调整
  
• 再找到第二个非叶子节点,由于[4,9,8]中9元素最大,4和9交换
  
• 这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4,6

此时,我们就得到了一个大顶堆

3. 将堆顶元素与末尾元素进行交换,使末尾元素最大,然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素,得到第二大元素,如此反复进行交换,重建,交换.

• 将堆顶元素9和末尾元素4进行交换,
  
• 重新调整结构,使其满足堆定义
  
• 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8
  
• 后续过程中,继续进行调整,交换,如此反复进行,最终使得整个序列有序
  
  在简单总结一下堆排序思路
  1, 将无序序列构建成一个堆,根据升序降序的需求选择大顶堆或小顶堆
  2, 将堆顶元素与末尾元素进行交换,将最大元素"沉"大数组末端
  3,重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序
  结合代码分析
  
  代码实现

package com.atguigu.tree;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr={4,6,8,5,9};
        heapSort(arr);

        //插入排序的速度测试
        int[] arr2=new int[80000];
        for (int i=0;i<80000;i++){
            arr2[i]=(int)(Math.random()*40000);//生成一个[0,20000)的随机整数
        }
        long startTime=System.currentTimeMillis();
        heapSort(arr2);
        long endTime=System.currentTimeMillis();
        System.out.println("排序用的时间:"+(endTime-startTime));
    }


    //编写一个堆排序的方法
    public static void heapSort(int[] arr){
        int temp=0;
        System.out.println("堆排序");
        //分部完成
        adjustHeap(arr,1,arr.length);
        System.out.println("第一次调整后:"+ Arrays.toString(arr));

        adjustHeap(arr,0,arr.length);
        System.out.println("第二次调整后:"+Arrays.toString(arr));

        //完成我们的最终代码
        //将一个无序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        System.out.println("数组:"+Arrays.toString(arr));

        //将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端
        //重写调整结构,使其能满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复调整+交换步骤,直到整个序列有序
        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));

    }

    //将一个数组(二叉树),调整成一个大顶堆

    /**
     * 完成将以i对应的非叶子节点数调整为大顶堆
     * @param arr 待调整的数组
     * @param i 表示非叶子节点的在数组中索引
     * @param length 多少个元素进行调整,length是在逐渐减少
     */
    public  static void adjustHeap(int[] arr,int i,int length){
        int temp=arr[i];//先取出当前元素的值,保存在临时变量里面
        //开始调整
        /*
        说明,k=i*2+1是i节点的左子节点.
         */
        for(int k=i*2+1;k<length;k=k*2+1){
            if((k+1)<length&&arr[k]<arr[k+1]){//说明左子节点它的值小于右子节点的值
                k++;//k指向右子节点
            }
            if(arr[k]>temp){//如果子节点大于父节点
                arr[i]=arr[k];//把较大的值赋值给当前的父节点
                i=k;//让i执行k,继续循环比较
            }else {
                break;
            }

        }
        //当for循环结束后,我们已经将以i为父节点的树的最大值,调整到了最上面
        arr[i]=temp;//将temp放到调整之后的位置
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83