数据结构与算法 ---- 详解堆排序、桶排序、基数排序及比较器内容（一）

前言

在讲解堆排序之前让我们来回顾一下完全二叉树的概念，因为堆的结构和完全二叉树息息相关。

一、完全二叉树

概念：

若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层若干结点靠左对齐，就说它是完全二叉树。如下图所示：

这里简单回顾完全二叉树的定义，接下来开始讲解重点！

二、堆

1.堆的结构

堆是一颗被完全填满的二叉树，底层上的元素从左到右填入，这样的树称为完全二叉树。

堆结构就是用数组实现完全二叉树结构

• 完全二叉树中如果每颗子树的最大值都在顶部就是大根堆
• 完全二叉树中如果每颗子树的最小值都在顶部就是小根堆
• 优先级队列结构，就是堆结构

例如，存在如下数组：

它的堆结构如下

每一个节点之间存在如下关系（后面会用到，记住！！）

1、左孩子：2 * i + 1

2、右孩子：2 * i + 2

3、父亲：( i - 1 ) / 2

i是当前节点，我们可以通过这三个关系知i求三

容易证明，一棵高为h的完全二叉树有2^h 到 2^(h+1) - 1个结点。这意味着完全二叉树的高是[logN]，显然它是O(logN)的。

本章将堆分为两种，分别为大根堆和小根堆

2.大根堆

每一个为头结点的子树，子树上整体的最大值，都是这棵树的头结点。这样的一个结构就称为大根堆，如下图所示就是大根堆：

在[7,5,1]形成的树上，头结点7为最大值

在[5,1,0]形成的树上，头结点5为最大值

在[9,7,5,5,1,1,0]形成的树上，头结点9为最大值

所以这个堆结构符合大根堆的定义，即是大根堆

如果我有这样一个需求：用户依次给我一个数，我要如何把它放进数组中且让这个数组满足大根堆呢？

答：heapInsert

2.1 heapInsert

heapInsert主要用于添加元素过程中，把新元素放进堆里，但依旧保持内部结构为大根堆的一种算法。【是一个向上的过程】

思想：放进一个数

1、首先，比较这个数和它父位置的数。

2、其次，若当前数大于父位置的数，那么交换位置。

3、最后，位置交换完后将当前位置的下标，来到父位置的下标处

图解如下

假设当前数组[4,2]，接下来我要插入元素5，经过heapInsert让其变为大根堆结构

当前值与父位置值比较后，大则交换

同时，index来到当前位置（原父位置）

代码实现

//某个数现在处在index位置，往上继续移动
    public static void heapInsert(int[] arr,int index){
        //如果当前的数大于父位置的数
        while (arr[index] > arr[(index - 1) /2]){
            //当前的数和父位交换
            swap(arr,index,(index-1)/2);
            //来到父位置，继续while判断
            index = (index-1)/2;
        }
    }
       
    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

这样就形成了大根堆

如果用户需要一个最大的数，我们将0位置上的数拿出来就行。然后把最后一位数放到0位置上，堆大小减一，请问，如何将剩下的数形成大根堆？

答：heapfiy

2.2 heapfiy

heapfiy主要用于树头部，往下操作使数组成为大根堆的一种算法。【是一个向下的过程】

思想：对一个组数（若从头节点出发）

1、首先，先判断当前节点是否有左孩子（只判断左孩子，因为是完全二叉树，所以没有左孩子那一定就没有右孩子）

2、其次，在左右孩子中选出值最大的，将其标记largest（较大孩子）

3、然后，较大孩子与父亲值进行比较，谁大谁把下标标记largest（胜出者）

4、如果最大值largest是父亲，不用改变。如果largest是某个孩子，将其与父亲位置交换

5、最后，当前位置下标来到最大值处

图解如下：

假设有数组[4,2,5]

在当前位置4看，它有左右孩子，且右孩子（5）更大，那么将右孩子标记为较大孩子

较大孩子与父亲进行比较，大于则交换位置，将下标往下走，继续进行heapfiy

代码实现

    //某个数在index位置，能否往下移动
    public static void heapify(int[] arr,int index,int heapSize){
        int left = index *2+1;   //左孩子下标
        //判断下面还有没有孩子
        while (left < heapSize){
            //两个孩子中，谁的值大，把下标给largest
            int largest = left +1 <heapSize && arr[left +1] > arr[left]
                    ? left +1 : left;

            //父和较大孩子之间，谁的值大，下标给largest
            largest = arr[largest] > arr[index] ? largest : index;

            if (largest == index){
                break;
            }
            swap(arr,largest,index);
            index = largest;   //新当前位置
            left = index*2+1;  //新左孩子下标
        }
    }

index是当前位置，可以在任意位置往下形成大根堆。

heapSize控制左右孩子不会发生越界，越界代表下面没有孩子了

2.3 heapsort堆排序

知道了怎么形成大根堆后，然后来进行堆排序。这两者之间有什么关联呢？

先说下堆排序的思想：

1、给出一组随机排序的数[9,4,8,6,1,2,4,7]，此时heapSize=8。经过heapInsert或heapify让其形成大根堆

heapSize是此时要进行操作的堆的大小，如arr[heapSize]为该堆的最后一个元素

形成大根堆前

形成大根堆后

此时数组：[9,7,8,6,1,2,4,4]

2、将最后一个数与头部（第一个数）交换，交换后是[4,7,8,6,1,2,4,9]，并将heapSize-1（断开最后一个数的连接）。

这样确保了最后一位数为最大值，并不再做改变。

此时最后一位9已经断开连接了，相当于固定了不再进行操作。然后剩下的7位数再进行大根堆操作

此时数组[8, 7, 4, 6, 1, 2,4, 9]

同理，将最后一位数，即下标为heapSize ==（不是9，9已经断连了，heapSize减一了，此时是8）==与头节点交换位置，交换后[4, 7, 4, 6, 1, 2,8, 9]，heapSize-1，断开最后一位的连接。

数组从[4,7,8,6,1,2,4,9]变为了[4, 7, 4, 6, 1, 2, 8, 9]，后两位已断开链接，并且不再进行操作。

以此类推，最终整体有序。

[1, 2, 4, 4, 6, 7, 8, 9]

总而言之，结合大根堆方式，堆排序看做是一个从后往前，从大到小依次使数组整体有序的过程。

代码实现

    //堆排序
    public static int[] headSort(int[] arr){
        if (arr == null || arr.length <2){
            return arr;
        }
        for (int i = 0;i<arr.length;i++){   //O(N)
            heapInsert(arr,i);  //调用heapInsert方法，使数组变成大根堆 O(logN)
        }

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

        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)
        }
        return arr;
    }

让剩下的数成为大根堆用heapInsert或heapfiy方法都可以

2.4 堆排序时间复杂度

1、初始化堆过程（O(N)）

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

    那么总的时间计算为：s = 2^( i - 1 )  *  ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

    S = 2^(k-2) * 1 + 2^(k-3)*2.....+2*(k-2)+2^(0)*(k-1)  ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；

    这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：

    S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

    除最后一项外，就是一个等比数列了，直接用求和公式：S = {  a1[ 1-  (q^n) ] }  / (1-q)；

    S = 2^k -k -1；又因为k为完全二叉树的深度，所以 (2^k) <=  n < (2^k  -1 )，总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;

    综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)
    原文参考：https://www.cdsy.xyz/computer/programme/algorithm/230513/cd43560.html

2、调整堆的时间复杂度（O(NlogN)）

因为每次要将最大值往后放，这个过程一个经历N次，那就是O(N)

剩下的数进行heapfiy操作，因为每次都是从跟节点往下找，所以最差情况就是这棵树的高度，即时间复杂度为O(logN)，所以需要O(NlogN)的时间复杂度

综上所述时间是O(NlogN)

2.5 堆排序空间复杂度

O(1)

因为heapInsert里没有申请额外变量。heapfiy里面就额外几个变量。

3.小根堆

定义：完全二叉树中如果每颗子树的最小值都在顶部就是小根堆

小根堆与大根堆相反，操作就不额外讲了，了解大根堆的话推导小根堆也不会很困难的，原理类似。

3.1 PriorityQueue

PriorityQueue是基于优先级堆的无界优先级队列，小根堆在java里就是优先级队列

PriorityQueue<Integer> heap = new PriorityQueue<>();

其底层实现就是堆结构，不传参的时候默认就是小根堆

如

    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Acomp());

        heap.add(6);
        heap.add(9);
        heap.add(3);
        heap.add(2);
        heap.add(10);

        while (!heap.isEmpty()){
            System.out.println(heap.poll()); //每次弹出队列头部
        }
    }

运行结果为：

2 3 6 9 10

三、堆排序扩展题

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

思路：这里要用到小根堆。因为每次移动的距离不能超过k。所以我先在数组[0，k]范围内形成小根堆，然后弹出第一个数（最小值）。再把k后面的数依次放到最小堆里去，每次结果弹出一个最小值。

代码实现

    public void sortedArrDistanceLessK(int[] arr,int k){
        //默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        //先把前k个数放到小根堆里去
        for (;index <= Math.min(arr.length,k);index++){
            heap.add(arr[index]);
        }
        int i = 0;
        for (;index<arr.length;i++,index++){
            heap.add(arr[index]);  //新加一个数放到小根堆里去
            arr[i] = heap.poll(); //每次弹一个数放到i位置
        }
        while (!heap.isEmpty()){
            arr[i++] = heap.poll();
        }
    }

本章内容主要讲解堆排序，桶排序、基数排序、比较器内容以后会进行更新~