排序-01-堆排序

前言

• 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

1. 堆

• 堆是具有如下性质的完全二叉树
  • 每个节点的值都大于或者等于其左右孩子节点的值，成为大顶堆
  • 每个节点的值都小于或者等于其左右孩子节点的值，成为小顶堆

同时，将堆中节点按照层级进行编号，将这种逻辑结构映射到数组中就是如下的例子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

2. 堆排序介绍

• 堆排序(Heap Sort) 是指利用堆这种数据结构所涉及的一种排序算法。
• 将n个无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
• 将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
• 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

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

3. 大顶堆实现堆排

 
import java.util.Arrays;
/**
 * 
 * @author Administrator
 *
 */
public class HeapSort {
    public static void main(String []args){
        int []arr = {7,6,7,11,5,12,3,0,1};
        System.out.println("排序前："+Arrays.toString(arr));
        sort(arr);
        System.out.println("排序前："+Arrays.toString(arr));
    }
 
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
 
    }
 
    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
 
    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

4. 小顶堆实现堆排以及TopK

小顶堆实现 (堆排序 以及 topk)

public class HeapSort{
    public static void heapSort(int[] tree,int n) {
        buildHeap(tree, n);//第一步是将得到的数组构建成小顶堆
        for(int i = n-1;i>=0;i--) {
            swap(tree, i, 0);//第一次构建完小顶堆之后，要进行第一个数和最后一个树的交换
            //交换完之后，最上面的数就不是最小数了，因此只需要对最上面的数，进行一个树的调整即可
            //所以，我们使用的时adjustTree而不是buildHeap
            adjustTree(tree, i, 0);//这里解释一下，这参数的含义：之所以将i当做数组的长度，
            //是因为我们将第一个数和最后一个数交换之后，就已经把最小的数放在了数组最后，进行
            //树调整的时候，就不需要管最后一个数字了。而0就是因为交换之后需要进行节点调节的那个节点
            //换到了第一个位置
        }
    }        
    /*
     * 这个函数写完之后，就可以将任意一个数组，构建成小顶堆了，构建完小顶堆之后，就要进行堆排序了
     */
    public static void buildHeap(int[] tree,int n) {
        for(int i = (n-1)/2;i>=0;i--) {//i从最后一个子节点的父节点开始，所以i = (n-1)/2
            adjustTree(tree, n, i);
        }
    }
    //利用adjustTree和swap两个函数，可以针对某一个父节点，进行调节。接下来，解决当整个树是
    //乱序的，将一个树构建成一个小顶堆。思路是这样的：从最后一个子节点的父节点开始调节，往上走。
    //不断重复，每往上一个父节点，父节点的下标就减一，可以将adjustTree和swap函数放进一个for循环
    //就是上面的for循环
    /*
     * 表示从某一个节点开始，调整一次树，使之成为堆，其中i表示某一个节点的下标
     */
    public static void adjustTree(int[] tree,int n,int i) {
        if(i>=n) {//这是递归头。
            return;
        }
        //首先确定i节点的左右两个孩子的下标
        int c1 = 2*i+1;
        int c2 = 2*i+2;
        //接下来，在这三个值中，找出最小值
        int max = i;//先假设最小值为这个父节点
        if(c1<n && tree[c1]>tree[max]) {//要保证c1不会出界
            max = c1;
        }
        if(c2<n && tree[c2]>tree[max]) {//保证c2不会出界  c2<n
            max = c2;
        }
        //经过上面的条件判断，就可以将最小值的下标保存到max中了，如果最小值max就是i，也就是
        //父节点最小，就不用调整，但是如果父节点不是最小，就要进行交换了
        if(max!=i) {
            swap(tree,max,i);
            adjustTree(tree,n,max);//交换之后，将父节点下放一级，就有可能会破坏下一层结构，
            //所以，递归调用adjustTree.使用递归之后，就要添加递归头了
        }              
    }
    private static void swap(int[] tree, int i, int j) {
        int temp = tree[i];
        tree[i] = tree[j];
        tree[j] = temp;
    }
}

public class TopK {
    public static void main(String[] args) {

        int[] data = new int[]{1, 3, 4, 2, 8, 9, 5, 6, 7, 32, 56, 23, 87, 32};//原始数据

        int[] topk = topK(data, 5);//调用topK方法，返回前k大的数组，返回的数组并不是有序的，而是一个小顶堆，如果想返回一个有序的，可以调用上面HeapSort类中的heapSort方法

        for (int i = 0; i < topk.length; i++) {//循环输出小顶堆
            System.out.println(topk[i]);
        }
    }

    public static int[] topK(int[] data, int k) {
        int[] topk = new int[k];//根据传进来的K创建长度为k的数组

        for (int i = 0; i < k; i++) {
            topk[i] = data[i];//先将源数据的前k个的数赋值给topK数组
        }

        HeapSort.buildHeap(topk, k);//对这个topK数组进行一次最小堆的构建。

        for (int i = k; i < data.length; i++) {//从源数据的第K个数开始循环，如果循环的数比堆顶元素还小，直接pass，
            // 如果比堆顶元素要大，就将此数放在堆顶，同时进行一次以它为起始点的树的调整。
            int temp = data[i];
            if (topk[0] < temp) {
                topk[0] = temp;
                HeapSort.adjustTree(topk, k, 0);
            }
        }
        return topk;
    }
}

再简单总结下堆排序的基本思路：

　　a.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

　　b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

　　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

打赏