Java教程

排序算法6 - 堆排序及其应用

本文主要是介绍排序算法6 - 堆排序及其应用,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

学习堆排序前,我们需要先对堆有一定的认识和了解,如果你还不了解堆的话,可以先看看我的另外一篇博客《堆的引入与实现》

算法思路

我们先使用堆的上浮使得数组中的数构成大根堆,再使用堆的下沉,就可以得到当前堆中的最大值,并放到下标为 heapSize 的位置,并把 heapSize - 1 , 继续使用堆的下沉,直到heapSize = 0

代码实现

public class heapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 2, 4, 5, 6, 2, 1, 7, 5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    } 
	public static void heapSort(int[] arr) {
        if(arr==null || arr.length < 2) {
            return;
        }
        for (int i =0;i<arr.length;i++){	// O(N)
            heapInsert(arr, i);		// O(logN)
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {	// O(N)
            heapify(arr,0, heapSize);	// O(logN)
            swap(arr, 0, --heapSize);	// O(1)
        }
    }

  // 这是关于堆的上浮与下沉的代码,我们在之前的文章已经介绍过
  public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = 2 * index + 1;
        while (left < heapSize) {// 表明此时有孩子节点
            // 找出左孩子和右孩子中更大的值,
            // 如果右孩子存在且右孩子的值大于左孩子,就返回右孩子的下标,否则返回左孩子的下标
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 将孩子中更大的那一个和父亲比较,如果比父亲大,则把下标给 largest
            largest = arr[largest] > arr[index] ? largest : index;
            // 如果孩子节点都没父亲大,则结束比较
            if (largest == index) {
                return;
            }
            swap(arr, index, largest);
            // 记录 largest ,用于下一次循环比较
            index = largest;
            left = 2 * index + 1;
        }
    }

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

运行结果如下:

运行结果

时间复杂度

由代码可知,堆排序的时间复杂度为 O(NlogN)

小小的优化

对于这段代码 for (int i =0;i<arr.length;i++){ heapInsert(arr, i); },我们可以做一个进一步的优化

 for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

原代码中,是进行循环,使得每一个数都进行堆的上浮,做法和之前在讲解堆的时候举的例子是一样的:用户每次给你一个值,你要保证该数存到数组后仍然对应的是一个大根堆;现在我们可以换个思路,因为用户不再是每次给我们一个值,而是我们最开始就得到了完整的数组,就已经组成了一棵二叉树,只是这树还没有构成大根堆而已,我们现在从最后一个元素往前处理

(1)对于一棵树,它的叶子结点是不需要进行堆的下沉(即 heapify)的,因为它们下面没有孩子结点

(1)

(2)而对于下面所标出来的子树而言,它们只需要 heapify 一次,就可以使子树成为大根堆

(2)

(3)当(2)中的子树也 heapify 过后,对于倒数第二层的元素而言,它也就只要 heapify 一次就可以变成大根堆

(3)

(4)同理,这样根节点也只要和它的孩子结点比较一次就可以变成大根堆

(4)

由上面步骤,我们可以得到时间复杂度为 O(N) (因为倒着来之后,对每个结点而言,它最多只需要与左右孩子比较,不需要再与孩子的孩子进行比较)

注意,这里是说数组变成堆的时间复杂度由 O(NlogN) 变为了 O(N),但是堆排序里根据大根堆进行排序的时间复杂度仍然为 O(NlogN),所以整体的时间复杂度还是 O(NlogN)

说明

稳定性

堆排序是不稳定的排序

举例如下:

稳定性示例图 1

对于这样的大根堆,如果我们使堆上浮,去掉里面最大的元素,那么最后一个元素 3 就会跑到根结点的位置,于是两个 3 的相对位置就发生了变化,所以堆排序是不稳定的排序

稳定性示例图 2

应用

题目

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

思路

假设 k = 6,那就意味着每一个元素的原始位置距离它排好后的位置不超过 6;

(1)我们现在准备一个小根堆,先遍历前七个数,即下标为 0 到 6 的数,那么排完序后,小根堆的最小值就在 0 位置,而这个最小值也是整个数组的最小值;因为每一个元素的原始位置距离它排好后的位置不超过 6,因此下标大于等于 7 的数排完序后都不可能是在 0 位置上,最终在 0 位置上的数的原始位置一定在下标为 0 - 6 的位置上

(1)

(2)我们将 0 位置的数弹出,然后将下标为 7 的数加入到小根堆,小根堆再弹出这个最小值,这个最小值就会在下标为 1 的位置

(2)

(3)继续将下标为 8 位置的数放入小根堆...周而复始,直到排完所有元素,即可得到有序的数组

(3)

代码

我们使用 Java 中的优先队列 PriorityQueue 来实现我们的算法,这个优先队列的本质其实就是堆

我们会用到它的两个方法:add() 添加元素,poll() 返回队首元素,并使队首元素出队列

(关于优先队列 PriorityQueue ,想了解更多的小伙伴可以自行百度一下唷)

public class heapSortApply {
    public static void main(String[] args) {
        int[] arr = new int[]{2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 11, 12, 14, 13, 12};
        sort(arr, 3);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int k) {
        // k = 0 表明已经排好序
        if (k == 0) {
            return;
        }
        // 优先队列,默认为小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // 先将前 k 个数放入堆中
        int index = 0;
        while (index < Math.min(arr.length, k)) {
            heap.add(arr[index++]);
        }
        int i = 0;
        for (; index < arr.length; i++, index++) {
            // 弹出对应的元素
            arr[i] = heap.poll();
            // 将 index 位置的元素放入堆中
            heap.add(arr[index]);
        }
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }


    }
}

时间复杂度

如果 k = 6,那么每个数字排好的代价为 log 6,所以时间复杂度为 O(Nlog6),那对于任意的 k ,该算法的时间复杂度为 O(Nlogk),因为 k 相对数组来说比较小,所以 logk 可忽略不计,算法的时间复杂度可等同于 O(N)

欢迎来逛逛我的博客 mmimo技术小栈

这篇关于排序算法6 - 堆排序及其应用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!