java面经查缺补漏之第六天（不知不觉已经第六天了，加油！今天我们来学习堆排序和优先队列）

水深无声 2023-07-08 09:12 12阅读 0赞

不知不觉已经第六天了，不过，从今天开始任务也就加重了，老师那边让我们开始在家里学习和工作了，需要做一些科研上的东西了，但是，还是希望自己能继续坚持，不管多少都要写一点。

今天我们来学习堆排序和优先队列，主要还是参考了程序员小灰这个公众号，感谢作者，二叉堆在我的上一篇。上网找了很多关于堆，堆排序，优先队列的资料，这里讲的是最好的，最容易理解的。其中讲解部分是它的，代码是我自己写的，还是直接swap换位看着舒服。

**1.堆排序**

![format_png][]

![format_png 1][]

让我们回顾一下二叉堆和最大堆的特性：

**1.二叉堆本质上是一种完全二叉树**

**2.最大堆的堆顶是整个堆中的最大元素**

当我们删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。

![format_png 2][]

正如上图所示，当我们删除值为10的堆顶节点，经过调节，值为9的新节点就会顶替上来；当我们删除值为9的堆顶节点，经过调节，值为8的新节点就会顶替上来.......

由于二叉堆的这个特性，我们每一次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶，反复调节二叉堆，所得到的集合就成为了一个有序集合，过程如下：

删除节点9，节点8成为新堆顶：

![format_png 3][]

删除节点8，节点7成为新堆顶：

![format_png 4][]

删除节点7，节点6成为新堆顶：

![format_png 5][]

删除节点6，节点5成为新堆顶：

![format_png 6][]

删除节点5，节点4成为新堆顶：

![format_png 7][]

删除节点4，节点3成为新堆顶：

![format_png 8][]

删除节点3，节点2成为新堆顶：

![format_png 9][]

到此为止，我们原本的最大堆已经变成了一个从小到大的有序集合。之前说过二叉堆实际存储在数组当中，数组中的元素排列如下：

![format_png 10][]

由此，我们可以归纳出堆排序算法的步骤：

**1. 把无序数组构建成二叉堆。**

**2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。**

![format_png 11][]

![format_png 12][]

import java.util.Arrays;
    
    public class heapSort {
        public static void main(String[] strings) {
            int[] array = {1, 5, 3, 4, 2, 8, 6, 7, 10, 0, 11, 12, -1};
            heapSort(array);
            System.out.println(Arrays.toString(array));
        }
    
        public static void heapSort(int[] array) {
            buildHeap(array);
            for (int i = array.length - 1; i > 0; i--) {
                int temp = array[0];
                array[0] = array[i];
                array[i] = temp;
                down(array, 0, i);
            }
        }
    
        public static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
        public static void buildHeap(int[] array) {
            for (int i = (array.length - 2) / 2; i >= 0; i--) {
                down(array, i, array.length);
            }
        }
    
        public static void down(int[] array, int index, int length) {
            int childIndex = index * 2 + 1;
            while (childIndex < length) {
                if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                    childIndex++;
                }
                if (array[index] < array[childIndex]) {
                    break;
                }
                swap(array, index, childIndex);
                index = childIndex;
                childIndex = index * 2 + 1;
            }
        }
    }

--------------------

2.优先队列

这一次，我们来讲一讲二叉堆的另外一个应用：**优先队列**

![format_png 13][]

![format_png 14][]

队列的特点是什么？

聪明的小伙伴们都知道，是**先进先出（FIFO）**。

**入队列：**

![format_png 15][]

**出队列：**

![format_png 16][]

那么，优先队列又是什么样子呢？

优先队列不再遵循先入先出的原则，而是分为两种情况：

**最大优先队列，无论入队顺序，当前最大的元素优先出队。**

**最小优先队列，无论入队顺序，当前最小的元素优先出队。**

比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：

**![format_png 17][]**

要满足以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高，最坏时间复杂度O（n），并不是最理想的方式。

至于为什么最坏时间复杂度是O（n），大家可以思考下。

![format_png 18][]

![format_png 19][]

让我们回顾一下二叉堆的特性：

**1.最大堆的堆顶是整个堆中的最大元素**

**2.最小堆的堆顶是整个堆中的最小元素**

因此，我们可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

**入队操作：**

1.插入新节点5

![format_png 20][]

2.新节点5上浮到合适位置。

![format_png 21][]

**出队操作：**

1.把原堆顶节点10“出队”

![format_png 22][]

2.最后一个节点1替换到堆顶位置

![format_png 23][]

3.节点1下沉，节点9成为新堆顶

![format_png 24][]

![format_png 25][]

![format_png 26][]

![format_png 27][]

import java.util.Arrays;
    
    public class priorityQueue {
        public static void main(String[] strings)
        {
            priorityQueue queue=new priorityQueue();
            queue.add(5);
            queue.add(4);
            queue.add(1);
            queue.add(11);
            queue.add(6);
            queue.add(9);
            queue.add(0);
            queue.add(-1);
            System.out.println(queue.remove());
            System.out.println(queue.remove());
        }
        private static int[] array;
        private static int size=0;
        //构造函数
        public priorityQueue()
        {
            array=new int[32];
        }
        //入队
        private static void add(int k)
        {
            if(size>array.length)
            {
                resize();
            }
            array[size++]=k;
            up(array);
        }
        //上浮
        public static void up(int[] array)
        {
            int childIndex=size-1;
            while(childIndex>0&&array[childIndex]<array[(childIndex-1)/2])
            {
                swap(array,childIndex,(childIndex-1)/2);
                childIndex=(childIndex-1)/2;
            }
        }
        //换位
        public static void swap(int[] array,int i,int j)
        {
            int temp=array[i];
            array[i]=array[j];
            array[j]=temp;
        }
        //如果超过大小则扩容
        private static void resize()
        {
            array=Arrays.copyOf(array,array.length*2);
        }
        //出队并返回队顶元素
        private static int remove()
        {
            int head=array[0];
            array[0]=array[--size];
            down();
            return head;
        }
        //下沉
        public static void down()
        {
            int index=0;
            int childIndex=1;
            while(childIndex<size)
            {
                if(childIndex+1<size&&array[childIndex+1]<array[childIndex])
                {
                    childIndex++;
                }
                if(array[index]<array[childIndex])
                {
                    break;
                }
                swap(array,index,childIndex);
                index=childIndex;
                childIndex=index*2+1;
            }
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JCQnJUUnduTmc4dlUyVDZDS1JQdzI1M1RPaWFJamUwaER5TDFyRDNQMERVSTd5UG5TVTV5aWFwUkhqWHJpY3c5THViOHhmVVpVekgzRHcvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JCQnJUUnduTmc4dlUyVDZDS1JQdzJON3g5b2F6Vm5xNFBrd09EVEltUEdrWmh1OXAwU1J2ZDZaMllEMWppY25HSndVQTlVd3d2OWVRLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWEyWlpUa1ppYkcxTmdMSlhUcXRmNkZkY3VLOUZraWJMcjZsR0dCRmhpYkVwRmxlNm5wOUR2bmg0VUEvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFlQmV1V2U1QnBUeTZiT3FleWliZEVYVVZHb2liZTgzRllkdDlUMFJxMWZUSXFQYlY5TmV4bVhkZy82NDA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFYb1dTd0xrdmRZUDNBcG9CNmM4d0pKaWNtUUpEazJOeEZDejROSFVoNmlhdDlwSUdKU28wbWpyZy82NDA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFwaDVJb2psV0lXUHFicWdwOGNEZVBHNWt6VHNpYkNpY0FuaWJnS1EyYkVSajROaWE2d0UzVHNrQkh3LzY0MA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFYQno5UUk4ZXBRbWRmRzlKb0NkbkF0WFFxWXpPbHdrOU8xbmNLT2dFTFRlV1FySjZMQTJJeVEvNjQw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFPeTZmWTAzZzRCb3pNeGtrQ3Vqakc2RzB6aWJiaGs4ajM3RGI0eW96M1JrT3d2bTExWVBjTkZBLzY0MA?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFzejJhOXpBUWhBTlVRU1h1SFJSOFlCaWJWQkJ3TnlLQk04TEY3SzFFT2NJa1dubmF2M0FHWTdBLzY0MA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWE3OVIyelN0VXlaTU1ZN1NhNGVtdWxyUWxHWm5jNWpDSWwzWUM4c0pyYWljTkVpYmswdmI1UUtDdy82NDA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFhVzJ1ZEl4SWljRGxKVmdzT2ZvSHJmczVpYlhXaHd5Q0hOYWQ5ZTRpYjBJcUZjMlpjSmt0VkFuWlEvNjQw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFpYTFqWExRbldqS0JPeG0zd0s5MzdpY0g1YVRhS09ESkRUbGJWeEV5aDYwMjM3RFlLRWlhcWFUTlEvNjQw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BJN3VYcWZqWEx6TTdNdUoyMjgxTWFoalZKa3BuOXBvSUxKSEtta28yMDF1MVY3bkd4cVpGam1GNkNENlZKcWhsVDRPV3dwOTlzUncvNjQw?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZWTJTNXpjd0tRdm1oWTFwNVdUV1JMR3VMNlZPR0pqQVdrZWlhblliRmtYOUo2aGZ1YXZpYkdyZFEvNjQw?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZT1pJTUZENlZ4T3NtaGdyeksyQ29udlpoUVhGTVJtOGlia3UzSmFWbTRzWHh6RjJHaWE2Y2RBQlEvNjQw?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZTXppY2p0WmliSGxpY0d5YWZXSG5LNzNONU44YUgxc2liNmh5OXVNNkcydldFbUY2aWNybFExSFVpYTNRLzY0MA?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZQWtZbnducVl1UVNlOXBGaWI1b0Zkb25rRUdjblE4MldsZGxpYWFnOFl3eU5hQm5FOUlrUGZSQlEvNjQw?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZbFRDd2hZd3pRMWljdjlNaWJJTk5pYXJtTGxmbGlhYnBxdk5seW1pYkpuOXhPNmdyRktRNm42TzRxdXcvNjQw?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZUHlqQnpGTDdhVkVtaWJLeE1TRGVwbGcwRXBGYmNQM2MzZmYzWmttdTdCSzFlMlpOTmJ6cmdpYlEvNjQw?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZaWNnZzc5cGlhNEZtZG1TdjFpYnBoSFhMcXB6MG1lOFpEeEIyRUNLQkpEQklIdlRub1ZuMm1XY0hBLzY0MA?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZaWNrb2FYb3dsTUR1VllxQTNPRFRXbHRhN2g4M2c2MTA2MjVpY0dEa3BQZGFNejJ3S05jeXRLbUEvNjQw?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZSTlZcjRPaWFxNEQ5Y2JRMTcyNlhIa3Fkb1p6MU0zaWNwRE42UHhwWW93ajdpYjczWkdEaWFackZudy82NDA?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZbXlFcGRLa2ZpYVRzRzdCVWhwOWNyREx5b0t3REJaSmliaWNQQk1JdmdWaWNMenR2Y0tJZ3YwQ0laZy82NDA?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZV1JKM0ZvVkJwdFRPZnd5b250dWZqb0k0NGlhVlZhaWJ1djVhV1NXMWlhSkdDSk5rVlNVVEtQYTZ3LzY0MA?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZaGE5V0V6bllxVUFqTW5RbEdFdVBLcEw5OGNPT3g3aWNLRmxCV0drczVNT1JGSVJVN0c4VVd4QS82NDA?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTc4TEpuR3BrZGtuR1pxUGcxV1NXYkZQaEk0YldvTlpYU3p6a3ZBbFhYUFJFV0hRTE9MaWJmUmtnLzY0MA?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTdwbGxpY2ljdWljS1Z1aEJpY2FEazNDYVNsZ2hRMm5tUDUwVzF1VnFyRmx1OTZ3MlM2bHlOeGNvT2ZnLzY0MA?x-oss-process=image/format,png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTdxaWFDT1ZoaHBWTWZpY1E0V1Y0RVV2Z25XOE5qTnBPZEV4NTZXaWJOZ2V3WWFxUHhpY2tDdjJSa2RRLzY0MA?x-oss-process=image/format,png