【排序】堆排序

发表于

这是我参与8月更文挑战的第5天，活动详情查看：8月更文挑战

介绍

堆结构就是用数组实现的完全二叉树结构，也叫做优先级队列结构,堆排序是利用堆这种数据结构而设计的一种排序算法， 堆排序是一种选择排序， 它的最坏， 最好平均时间复杂度均为 O(nlogn)， 它也是不稳定排序。

堆是具有以下性质的完全二叉树： 每个结点的值都大于或等于其左右孩子结点的值， 称为大顶堆（注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系,）每个结点的值都小于或等于其左右孩子结点的值， 称为小顶堆。

image.png

思路

1.首先我们来看构建大顶堆的两个主要方法:

heapInsert: 向堆中加入元素,先加在末尾，然后通过比较其与父节点之间的大小关系不断向上交换。直到子节点的值小于父节点。
heapify: 将以index位置为根节点的树调整为大根堆的形式
注意: 以上方法也可以构建小根堆，只是条件稍微改变一下

2.通过heapInsert首先将数组构成一个大根堆

3.整个序列的最大值就是堆顶的根节点。

4.将其与末尾元素进行交换， 此时末尾就为最大值

5.然后将剩余 n-1 个元素通过heapify重新构造成一个堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了

代码

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
java复制代码   public void heapSort(int[] arr) {
        //首先我们假设依次把数组中的数加入堆中，以此方法来构建堆结构
        for (int i = 1; i < arr.length; i++) {
            heapInsert(arr, i);
        }
//        for (int i = arr.length - 1; i >= 0; i++) {  //这种调整成堆的时间复杂度O(N)
//            heapify(arr, i, arr.length);
//        }
        for (int i = arr.length - 1; i >= 0; i--) { //这个是O(N * logN)级别的
            swap(arr, i, 0);
            heapify(arr, 0, i);
        }
    }

    public void heapInsert(int[] arr, int index) {
        //在数组尾部插入
        //和父节点比较，一步一步向上走
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    //size表示当前堆的大小
    public void heapify(int[] arr, int index, int size) { //这个是调整成大根堆结构的过程
        //index表示从哪个下标开始调整
        int left = index * 2 + 1;
        while (left < size) { //表示存在左子节点
            int largestIndex = index * 2 + 2 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            largestIndex = arr[largestIndex] > arr[index] ? largestIndex : index;
            if (largestIndex == index) break;
            swap(arr, largestIndex, index);
            index = largestIndex;  //需要调整的节点移动到被交换值的子节点的位置
            left = index * 2 + 1;//这个时候left就是子节点的left了
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

堆排序扩展题目

已知一个几乎有序的数组， 几乎有序是指， 如果把数组排好顺序的话， 每个元素移动的距离可以不超过k， 并且k相对于数组来说比较小。 请选择一个合适的排序算法针对这个数据进行排序。

思路

1.可以使用一个容量为k+1个小根堆进行操作，

2.将数组中索引位置为i到i+k上面的k+1个元素加入到小根堆中，将堆顶的最小值放到i位置上

3.此时<=i位置的元素已经排序好了然后把k+2上面的元素加入到小根堆中,继续重复操作

4.添加到arr.length-1位置元素的时候把直接把堆中元素弹出放到对应位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码public void sortArrayDistanceLessK(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int i = 0;
        for (; i < k; i++) {  //先向小根堆中添加k个数
            heap.add(arr[i]);
        }
        for (; i < arr.length; i++) {
            heap.add(arr[i]);
            arr[i - k] = heap.poll();

        }
        while (!heap.isEmpty()) {
            arr[i - k] = heap.poll();
            i++;
        }

    }

时间复杂度

O(N * logN)
headInsert和heapify的时间复杂度都是logN

1
2
3
4
java复制代码        for (int i = arr.length - 1; i >= 0; i--) { //这个是O(N * logN)级别的
            swap(arr, i, 0);
            heapify(arr, 0, i);
        }

for循环遍历一遍元素然后heapify的时间复杂度为logN所以堆排序的时间复杂度为O(N * logN)

额外空间复杂度

O(1)
只用到有限几个变量

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%