java 堆（优先级队列）详解

傷城~ 2024-03-16 23:17 127阅读 0赞

#### JAVA堆以及优先级队列详解 ####

*  一、堆的模拟实现
 *   *  1.1堆的概念
     *  1.2 堆的性质
     *  1.3堆的存储结构
     *  1.4堆的创建
     *   *  1.4.1 只有根节点不满足堆的特性
         *  1.4.2 不只有根节点不满足堆的特性
         *   *  1.4.2.1 建堆代码
             *  1.4.2.2 建堆过程图示
         *  1.4.3 建堆的时间复杂度
     *  1.5堆的插入
     *   *  1.5.1堆的插入的基本思想
         *  1.5.2堆的插入的完整代码
         *  1.5.3堆的插入的过程图示
     *  1.6堆的删除
     *   *  1.6.1堆的删除的基本操作
         *  1.6.2堆的删除的代码
         *  1.6.3堆的删除的过程图示
 *  二、优先级队列
 *   *  2.1优先级队列的概念
     *  2.2优先级队列的常用接口
     *  2.3PriorityQueue的特性
     *  2.4PriorityQueue的构造方法
     *  2.5PriorityQueue的基本方法
     *  2.6PriorityQueue的扩容机制
     *  2.7集合框架中PriorityQueue的比较方式
     *  2.8使用PriorityQueue创建大小堆，解决TOPK问题
     *   *  2.8.1问题背景
         *  2.8.2解决办法
         *  2.8.1找k个最大值
         *  2.8.2找k个最小值
         *  2.8.3利用比较器构建大根堆
 *  三、堆排序
 *   *  3.1问题背景
     *  3.2误区
     *  3.3解决办法
     *  3.4具体代码实现
     *  3.5执行过程图示

## 一、堆的模拟实现 ##

### 1.1堆的概念 ###

如果有一个关键码的集合K = \{k0，k1， k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

### 1.2 堆的性质 ###

堆中某个节点的值总是不大于或不小于其父节点的值；  
堆总是一棵完全二叉树。  
如下图就是大根堆和小根堆  
![在这里插入图片描述][80025aefef0b4fe48419271a7fd16fb2.png]

### 1.3堆的存储结构 ###

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储  
![在这里插入图片描述][652eb4cf305d4938804802644bdc1dce.png]注意：

*  对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
 *  将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：  
    如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2  
    如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子  
    如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子

### 1.4堆的创建 ###

要完成堆的创建，首先需要了解几个完全二叉树的性质。

*  如果一致完全二叉树有n个结点，那么最后一个叶子结点的坐标是n-1(根节点是从0开始的),最后一个父节点的坐标是(n-1-1)/2
 *  如果父节点的下标是i,那么其左孩子（如果有）的下标是2i+1;右孩子（如果有）的下标是2i+1。

#### 1.4.1 只有根节点不满足堆的特性 ####

![在这里插入图片描述][50f4ed4504414216afef00f2d982d8d9.png]如上图，发现只有根节点没有满足小根堆的特性，那么我们如何将这个堆调整至符合小根堆特性呢？  
要知道这些数据实际都是用数组的形式进行存储的，我们可以通过下标去访问每个数据。

1.  我们先用一个parent指向根节点，那么其左孩子child的下标是(2parent+1)，右孩子的下标是child+1；
2.  我们无非是比较三者谁大谁小，选取最小的哪一个（其下标重新赋值为child），将其与父节点（也就是parent）的值进行交换。
3.  但是这样就会有新的问题，这回导致根节点的子树不再满足小根堆的性质，所以还要继续对子树进行调整，所以我们此时将parent的值赋值为child,指向更改后的子树的根节点，在重复上述步骤即可  
    代码如下

public void shutDown(int parent,int useSize){
        
            int child = 2*parent+1;//找到左孩子
            while(child<useSize){
        //child<useSize可以作为循环的终止条件，也可以作为判断父节点是否有左孩子的条件
                if(child+1<useSize && elem[child]>elem[child+1]) {
        //child+1<useSize判断是否有右孩子，
                    child++;//elem[child]<elem[child+1]结合child++用于取得左右孩子的最小值。
                }
                //注意：如果不满足child+1<useSize，也就是所只有左孩子没有右孩子，那么此时去判断左孩子值与根节点谁大谁小，
                // 这里千万不能把if(elem[parent]>elem[child])写到if(child+1<useSize && elem[child]>elem[child+1])里面去，这样的话就会有最后一个只有左孩子的父节点没有调整的情况
                if(elem[parent]>elem[child]){
        //如果父节点的值比子节点最小值要大，那么就要交换
                    int tmp = elem[parent];
                    elem[parent] = elem[child];
                    elem[child] = tmp;
                    //调整好这个父节点之后有可能会导致子树不再满足小根堆的特性，所以要继续往下调整
                    parent = child;
                    child = 2*parent+1;
                }
                else{
        
                    break;//如果父节点的值比子节点最小值要小，那么就不交换，直接break，注意此时是不需要再往下去看子树是否满足小根堆的，一定是
                    //满足的，因为前面的if里面是从最后的父节点一路往前调整的，所以后面的一定满足小根堆的特性
                    }
            }
        }

#### 1.4.2 不只有根节点不满足堆的特性 ####

其实这种情况是非常好处理的，只需要遍历一遍父节点即可，把每个父节点都当做当前子树的根节点去处理即可

##### 1.4.2.1 建堆代码 #####

所以完整的建立小根堆的代码如下

public class TestHeap {
        
        public int[] elem;
        public int useSize;
    
        public TestHeap(){
        
            this.elem = new int[10];
            this.useSize = 0;
        }
        //初始化一个数组，将输入的数组全部用elem数组存起来
        public void  initElem(int[] array) {
        
            for (int i = 0; i < array.length; i++) {
        
                elem[i] = array[i];
                useSize++;
            }
        }
        //创建一个大根堆
        public void createShortHeap(){
        
            //从最后一个父节点开始向下去调整
            for (int i = (elem.length-1-1)/2; i >=0 ; i--) {
        
                //elem.length-1表示最后一个结点的下标，最后一个结点下标减一再除以二就是最后一个父节点的坐标
                shutDown(i,useSize);
    
            }
        }
    
        //向下调整
        public void shutDown(int parent,int useSize){
        
            int child = 2*parent+1;//找到左孩子
            while(child<useSize){
        //child<useSize可以作为循环的终止条件，也可以作为判断父节点是否有左孩子的条件
                if(child+1<useSize && elem[child]>elem[child+1]) {
        //child+1<useSize判断是否有右孩子，
                    child++;//elem[child]<elem[child+1]结合child++用于取得左右孩子的最小值。
                }
                //注意：如果不满足child+1<useSize，也就是所只有左孩子没有右孩子，那么此时去判断左孩子值与根节点谁大谁小，
                // 这里千万不能把if(elem[parent]>elem[child])写到if(child+1<useSize && elem[child]>elem[child+1])里面去，这样的话就会有最后一个只有左孩子的父节点没有调整的情况
                if(elem[parent]>elem[child]){
        //如果父节点的值比子节点最小值要大，那么就要交换
                    int tmp = elem[parent];
                    elem[parent] = elem[child];
                    elem[child] = tmp;
                    //调整好这个父节点之后有可能会导致子树不再满足小根堆的特性，所以要继续往下调整
                    parent = child;
                    child = 2*parent+1;
                }
                else{
        
                    break;//如果父节点的值比子节点最小值要小，那么就不交换，直接break，注意此时是不需要再往下去看子树是否满足小根堆的，一定是
                    //满足的，因为前面的if里面是从最后的父节点一路往前调整的，所以后面的一定满足小根堆的特性
                    }
            }
        }
    }

测试代码

测试结果  
![在这里插入图片描述][00c9a83ab9ff4ed595ba76e8eab5c6af.png]

##### 1.4.2.2 建堆过程图示 #####

如下图是上面这个例子的建立小根堆的过程  
![在这里插入图片描述][5d84674153af4ed295310de4907af117.png]

#### 1.4.3 建堆的时间复杂度 ####

我们用满二叉树来进行分析，多几个结点不影响结果，满二叉树也方便计算  
![在这里插入图片描述][abed0b86b5e64ecea40728ed70873543.png]  
所以  
![第一层][e5f8fafd5f794414b45a2c2e8411f0f9.png]  
![在这里插入图片描述][bb11789533e946e685a547951a625fa2.png]

### 1.5堆的插入 ###

#### 1.5.1堆的插入的基本思想 ####

首先，堆的插入一定是从堆的末尾开始插入的，不能从中间开始插入  
在对末尾插入之后该堆就不一定符合小根堆的特性了，需要向上调整。  
如下图  
![在这里插入图片描述][00edac0074d04029bc9cb6c4992d803d.png]  
首先需要知道的是，在完全二叉树里，如果子节点的下标是i,那么该子节点对应的父节点的下标就是(i-1)/2。

1.  我们将插入结点的下标赋值为child,那么其父节点的下标为parent = (child-1)/2。
2.  比较child的值与parent的值谁大谁小，如果child的值比较小，就需要调换child的值与parent的值，反之则不需要调整。
3.  在一次调整之后，还需要往上继续调整，所以将child = parent;parent = (child-1)/2。

#### 1.5.2堆的插入的完整代码 ####

//插入
        public void offer(int val) {
        
            if (isFull()) {
        //判断堆是不是满了，满了就调用copyof进行扩容；
                elem = Arrays.copyOf(elem, (elem.length) * 2);
            }
            //在堆的末尾插入
            this.elem[useSize] = val;
            //重新调整堆为小根堆
            shiftUp(useSize);
            //一定要注意这三句的顺序，最后useSize++
            useSize++;
    
    
        }
    
        //向上调整
        public void shiftUp(int child) {
        //child 就是插入的位置下标
            int parent = (child - 1) / 2;
            while (parent >= 0) {
        //注意这里是parent>=0,因为parent = 0时正好是根节点的情况，这是也是有可能需要调整的。
                if (elem[parent] > elem[child]) {
        //如果子节点的值比父节点的值要小，那么就是需要调整的。
                    int tmp = elem[parent];
                    elem[parent] = elem[child];
                    elem[child] = tmp;
                    child = parent;
                    parent = (child - 1) / 2;
                } else {
        
                    break;//如果插入的数（孩子结点）的值比其父节点的值本来就要大，那么是满足小根堆特性的，不需要调整。
                }
            }
    
        }
        //判满
        public boolean isFull() {
        
            if (useSize == elem.length) {
        
                return true;
            }
            return false;
        }

测试代码

public class Test {
        
        public static void main(String[] args) {
        
            TestHeap testHeap = new TestHeap();
            int[] array = {
        27,15,19,18,28,34,65,49,25,37};
            testHeap.initElem(array);
            for (int i = 0; i < testHeap.useSize; i++) {
        
                System.out.print(testHeap.elem[i]+" ");
            }
            System.out.println();
            testHeap.createShortHeap();
            for (int i = 0; i < testHeap.useSize; i++) {
        
                System.out.print(testHeap.elem[i]+" ");
            }
            System.out.println();
            testHeap.offer(10);
            for (int i = 0; i < testHeap.useSize; i++) {
        
                System.out.print(testHeap.elem[i]+" ");
            }
        }
    }

测试结果  
![在这里插入图片描述][154fd89aebe84b348441e9e19a0a5826.png]

#### 1.5.3堆的插入的过程图示 ####

下图就是上述代码的执行过程  
![在这里插入图片描述][2002bb7cd7d14e0490650d829b2630ec.png]

### 1.6堆的删除 ###

#### 1.6.1堆的删除的基本操作 ####

首先堆删除的元素一定是堆首元素（也就是一定是数组首元素）  
堆的删除的具体操作

1.  将堆顶元素与堆尾元素互换，将堆尾元素删除（useSize-1）
2.  从堆顶开始向下调整，重新调整至符合大根堆（小根堆）。

#### 1.6.2堆的删除的代码 ####

经过前面的代码学习，其实删除已经很简单了  
向下调整的代码我们已经写过了，只需要调用即可

//删除
        public void poll(){
        
            if(!isEmpty()){
        
                elem[0] = elem[useSize-1];//堆尾元素赋值为堆首元素
                useSize--;//useSize-1表示删除最后一个元素
                shiftDown(0, useSize);
            }
            else{
        
                return;
            }
        }
        //判空
        public boolean isEmpty(){
        
            if(useSize == 0){
        
                return true;
            }
            return false;
        }
        //向下调整
        public void shiftDown(int parent, int useSize) {
        
            int child = 2 * parent + 1;//找到左孩子
            while (child < useSize) {
        //child<useSize可以作为循环的终止条件，也可以作为判断父节点是否有左孩子的条件
                if (child + 1 < useSize && elem[child] > elem[child + 1]) {
        //child+1<useSize判断是否有右孩子，
                    child++;//elem[child]<elem[child+1]结合child++用于取得左右孩子的最小值。
                }
                //注意：如果不满足child+1<useSize，也就是所只有左孩子没有右孩子，那么此时去判断左孩子值与根节点谁大谁小，
                // 这里千万不能把if(elem[parent]>elem[child])写到if(child+1<useSize && elem[child]>elem[child+1])里面去，这样的话就会有最后一个只有左孩子的父节点没有调整的情况
                if (elem[parent] > elem[child]) {
        //如果父节点的值比子节点最小值要大，那么就要交换
                    int tmp = elem[parent];
                    elem[parent] = elem[child];
                    elem[child] = tmp;
                    //调整好这个父节点之后有可能会导致子树不再满足小根堆的特性，所以要继续往下调整
                    parent = child;
                    child = 2 * parent + 1;
                } else {
        
                    break;//如果父节点的值比子节点最小值要小，那么就不交换，直接break，注意此时是不需要再往下去看子树是否满足小根堆的，一定是
                    //满足的，因为前面的if里面是从最后的父节点一路往前调整的，所以后面的一定满足小根堆的特性
                }
            }
        }

测试代码

结果  
![在这里插入图片描述][13bc5a0f35b54ed6809eedd84abc4c66.png]

#### 1.6.3堆的删除的过程图示 ####

![在这里插入图片描述][d06b02a68bd147948893b2ed6f368962.png]

## 二、优先级队列 ##

### 2.1优先级队列的概念 ###

在java中堆和优先级队列是一个概念，前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)（该段引用自比特讲义）。

### 2.2优先级队列的常用接口 ###

Java集合框架中提供了**PriorityQueue**和**PriorityBlockingQueue**两种类型的优先级队列，PriorityQueue是线程不安的，PriorityBlockingQueue是线程安全的。这里我们重点介绍PriorityQueue。  
![在这里插入图片描述][59eafbc44a9e4bd095422fbcd0650170.png]

### 2.3PriorityQueue的特性 ###

关于PriorityQueue的使用要注意：

1.  使用时必须导入PriorityQueue，即`import java.util.PriorityQueue;`
2.  PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出`ClassCastException`异常
3.  不能插入null对象，否则会抛出`NullPointerException`异常
4.  没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5.  插入和删除元素的时间复杂度为O（logN）
6.  PriorityQueue底层使用了堆数据结构
7.  PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

### 2.4PriorityQueue的构造方法 ###

PriorityQueue()

创建一个PriorityQueue ，具有默认的初始容量（11），根据它们的natural ordering对其元素进行排序 。

PriorityQueue(Collection<? extends E> c)

创建一个 包含了集合C中的所有元素的PriorityQueue。

PriorityQueue(int initialCapacity)

创建PriorityQueue并指定的初始容量initialCapacity

示例

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Queue<Integer> priorityQueue1 = new PriorityQueue<>();
            priorityQueue1.offer(27);
            priorityQueue1.offer(15);
            priorityQueue1.offer(19);
            priorityQueue1.offer(18);
            priorityQueue1.offer(28);
            priorityQueue1.offer(34);
            priorityQueue1.offer(65);
            priorityQueue1.offer(49);
            priorityQueue1.offer(25);
            priorityQueue1.offer(37);
            //使用迭代去打印堆（数组）
            Iterator<Integer> iterator1 = priorityQueue1.iterator();
            while(iterator1.hasNext()){
        
                System.out.print(iterator1.next()+" ");
            }
            System.out.println();
    //
            List<Integer> arraylist = new ArrayList<>();
            arraylist.add(27);
            arraylist.add(15);
            arraylist.add(19);
            arraylist.add(18);
            arraylist.add(28);
            arraylist.add(34);
            arraylist.add(65);
            arraylist.add(49);
            arraylist.add(25);
            arraylist.add(37);
            Queue<Integer> priorityQueue2 = new PriorityQueue<>(arraylist);
            Iterator<Integer> iterator2 = priorityQueue1.iterator();
            while(iterator2.hasNext()){
        
                System.out.print(iterator2.next()+" ");
            }
            System.out.println();
            
        }
    }

结果  
![在这里插入图片描述][70de866a4a354dc287f519ac9afe4f77.png]

### 2.5PriorityQueue的基本方法 ###

boolean add(E e)

将指定的元素插入到此优先级队列中。

void clear()

从此优先级队列中清空所有元素。

Comparator<? super E> comparator()

返回用于为了在这个队列中的元素，或比较null如果此队列根据所述排序natural ordering的元素。

boolean contains(Object o)

如果此队列包含指定的元素，则返回 true 。

Iterator<E> iterator()

返回此队列中的元素的迭代器。

boolean offer(E e)

将指定的元素插入到此优先级队列中。  
与addq区别在于add堆满时直接抛出异常，而offer会自动扩容并且返回false;

E peek()

检索但不删除此队列的头，如果此队列为空，则返回 null 。

E poll()

检索并删除此队列的头，如果此队列为空，则返回 null 。

boolean remove(Object o)

从该队列中删除指定元素的单个实例（如果存在）。

int size()

返回此集合中的元素数。

Spliterator<E> spliterator()

在此队列中的元素上创建late-binding和失败快速 Spliterator 。

Object[] toArray()

返回一个包含此队列中所有元素的数组。

<T> T[] toArray(T[] a)

返回一个包含此队列中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。

### 2.6PriorityQueue的扩容机制 ###

以下是原生PriorityQueue的扩容原码

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //数组的最大长度是Integer所能表示的最大值减8
    private void grow(int minCapacity) {
        
    	int oldCapacity = queue.length;
    	// Double size if small; else grow by 50%
    	int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :
    	(oldCapacity >> 1));
    	//从这个三目运算符就可以看出扩容的机制。
    // overflow-conscious code
    	if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新的容量比数组的最大容量还要大
    		newCapacity = hugeCapacity(minCapacity);
    	queue = Arrays.copyOf(queue, newCapacity);
    }
    private static int hugeCapacity(int minCapacity) {
        
    if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
    }

优先级队列的扩容说明：  
如果容量小于64时，是按照oldCapacity的2倍方式扩容的  
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的  
如果容量超过MAX\_ARRAY\_SIZE，按照MAX\_ARRAY\_SIZE来进行扩容

### 2.7集合框架中PriorityQueue的比较方式 ###

集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：  
Comparble和Comparator两种方式。

1.  Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
2.  用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。

**java JDK中关于comparable和comparator的一些原生代码**

// JDK中PriorityQueue的实现：
    public class PriorityQueue<E> extends AbstractQueue<E> 
       implements java.io.Serializable {
        
       // ...
       // 默认容量
       private static ﬁnal int DEFAULT_INITIAL_CAPACITY = 11;
       // 内部定义的比较器对象，用来接收用户实例化PriorityQueue对象时提供的比较器对象 
       private ﬁnal Comparator<? super E> comparator;
       // 用户如果没有提供比较器对象，使用默认的内部比较，将comparator置为null 
       public PriorityQueue() {
        
           this(DEFAULT_INITIAL_CAPACITY, null); 
     }
       // 如果用户提供了比较器，采用用户提供的比较器进行比较
       public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
         
           // Note: This restriction of at least one is not actually needed,
           // but continues for 1.5 compatibility 
           if (initialCapacity < 1)
               throw new IllegalArgumentException(); 
           this.queue = new Object[initialCapacity]; 
           this.comparator = comparator;
     }
       // ...
       // 向上调整：
       // 如果用户没有提供比较器对象，采用Comparable进行比较 
       // 否则使用用户提供的比较器对象进行比较
       private void siftUp(int k, E x) {
         
           if (comparator != null)
               siftUpUsingComparator(k, x); 
           else
               siftUpComparable(k, x); 
     }
      // 使用Comparable
       @SuppressWarnings("unchecked")
       private void siftUpComparable(int k, E x) {
        
           Comparable<? super E> key = (Comparable<? super E>) x; 
           while (k > 0) {
        
               int parent = (k - 1) >>> 1; 
               Object e = queue[parent]; 
               if (key.compareTo((E) e) >= 0) 
                   break;
               queue[k] = e; 
               k = parent; 
         }
           queue[k] = key; 
     }
       // 使用用户提供的比较器对象进行比较 
       @SuppressWarnings("unchecked")
       private void siftUpUsingComparator(int k, E x) {
        
         while (k > 0) {
        
               int parent = (k - 1) >>> 1; 
               Object e = queue[parent];
               if (comparator.compare(x, (E) e) >= 0) 
                   break;
               queue[k] = e; 
               k = parent; 
         }
           queue[k] = x; 
     }
    }

我们可以实际操作来看一下底层的运行逻辑

Queue<Integer> priorityQueue1 = new PriorityQueue<>();
    priorityQueue1.offer(27);
    priorityQueue1.offer(15);

那么底层实际上是如下图这样运行的  
![在这里插入图片描述][c68a78e5a5d44ed1946a5762276f6195.png]而这里面调用的comparaTo实际上应该是在Integer类里面进行了覆写  
![在这里插入图片描述][a3bcd7067ccf4199b56dc5152404177e.png]

### 2.8使用PriorityQueue创建大小堆，解决TOPK问题 ###

#### 2.8.1问题背景 ####

假如说某市进行了一次统考，有很多学生（数据量很大），那么我们如何在众多学生中迅速找到这次考试中成绩最好的50人呢？  
这就要用到堆这样的数据结构了。我们将问题简化，假如有7个学生，怎么去找前k名，或者怎么找k个分数最大值、怎么找第k大值。同理又怎么去找分数最低的k名学生。

#### 2.8.2解决办法 ####

#### 2.8.1找k个最大值 ####

先来说找k个分数最大值  
我们可以定义一个只有k个元素的PriorityQueue,将7和元素顺序插入，在插入k后（比如说k = 3）那么我们得到结果3的元素的小根堆，并且此时堆顶元素是当前三个元素中最小的，那么我们再入堆时，就将该元素与堆顶元素进行比较，如果比堆顶大，那么就证明他在当前最大的数值这个集合中，我们就入堆，否则不如堆，继续往后。  
此时这个思路里面的比较就需要我们重写comparable方法或者自己定义一个comparator比较器了。

**具体代码如下**

**先定义一个学生类实现Comparable接口并且重写comparaTo方法**

public class student implements Comparable<student>{
        
        String name;
        int age;
        double score;
    
        public student(String name, int age, double score) {
        
            this.name = name;
            this.age = age;
            this.score = score;
        }
    
        @Override
        //重写comparableTo方法
        public int compareTo(student o) {
        
            return (int)(this.score-o.score);
        }
    }

import java.util.*;
    
    public class Main {
        
     public static void main(String[] args) {
        
            student student1 = new student("a", 27, 27.0);
            student student2 = new student("b", 15, 15.0);
            student student3 = new student("c", 19, 19.0);
            student student4 = new student("d", 18, 18.0);
            student student5 = new student("e", 28, 28.0);
            student student6 = new student("f", 34, 34.0);
            student student7 = new student("g", 65, 65.0);
    
            ArrayList<student> arrayList = new ArrayList<>();
            arrayList.add(student1);
            arrayList.add(student2);
            arrayList.add(student3);
            arrayList.add(student4);
            arrayList.add(student5);
            arrayList.add(student6);
            arrayList.add(student7);
    
            PriorityQueue<student> priorityQueue1  = new PriorityQueue<>(3);
            int i = 0;
            while(i<3){
        
                priorityQueue1.offer(arrayList.get(i));
                i++;
            }
            while(i<arrayList.size()){
        
                if(arrayList.get(i).score>priorityQueue1.peek().score){
        
                    priorityQueue1.poll();
                    priorityQueue1.offer(arrayList.get(i));
                    i++;
                }
                else{
        
                    i++;
                }
            }
            System.out.println();
    }

**测试结果**  
我们发现preorityqueue里面确实是成绩最高的三名学生  
![在这里插入图片描述][38c1e952fb0941a7a4d88495703fb12b.png]

#### 2.8.2找k个最小值 ####

找k个最小值与找k个最大值的区别无非就在于要建立的是大根堆，每次都是比堆顶元素小才会入堆。  
非常简单，只需要将comparaTo方法调转一下就可以。

student类的定义：

主函数

import java.util.*;
    
    public class Main {
        
    	public static void main(String[] args) {
        
            student student1 = new student("a", 27, 27.0);
            student student2 = new student("b", 15, 15.0);
            student student3 = new student("c", 19, 19.0);
            student student4 = new student("d", 18, 18.0);
            student student5 = new student("e", 28, 28.0);
            student student6 = new student("f", 34, 34.0);
            student student7 = new student("g", 65, 65.0);
    
            ArrayList<student> arrayList = new ArrayList<>();
            arrayList.add(student1);
            arrayList.add(student2);
            arrayList.add(student3);
            arrayList.add(student4);
            arrayList.add(student5);
            arrayList.add(student6);
            arrayList.add(student7);
    
            PriorityQueue<student> priorityQueue1  = new PriorityQueue<>(3);
            int i = 0;
            while(i<3){
        
                priorityQueue1.offer(arrayList.get(i));
                i++;
            }
            while(i<arrayList.size()){
        
                if(arrayList.get(i).score<priorityQueue1.peek().score){
        
                    priorityQueue1.poll();
                    priorityQueue1.offer(arrayList.get(i));
                    i++;
                }
                else{
        
                    i++;
                }
            }
            System.out.println();
        }
    }

测试结果  
![在这里插入图片描述][31b10776a05c4fd98eeec5456c782af1.png]

#### 2.8.3利用比较器构建大根堆 ####

其实，PriorityQueue除了支持前面介绍过的三种构造方法外，其实还支持比较器作为参数参与构造，有以下两种

PriorityQueue(Comparator<? super E> comparator)

创建具有默认初始容量（11）的 PriorityQueue ，并根据指定的比较器对其元素进行排序。

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

创建具有 PriorityQueue初始容量的PriorityQueue，根据指定的比较器对其元素进行排序。

所以，除了student类实现comparable接口，重写compareTo方法，还可以自己创建一个比较器类，实现comparator接口，重写compare方法。然后实例化这个对象，将带实例化对象作为实参传入priorityqueue的构造函数。  
比如下面就是采用重新构造比较器的形式去建立大根堆，去结果上述topK问题。  
示例：  
student类的定义

public class student {
        
        String name;
        int age;
        double score;
    
        public student(String name, int age, double score) {
        
            this.name = name;
            this.age = age;
            this.score = score;
        }
     }

Main类

//构建一个用于大根创建的比较器
    class maxScoreComprator implements Comparator<student>{
        
        @Override
        public int compare(student o1, student o2) {
        
            return (int)(o2.score- o1.score);
        }
    }
    public class Main {
        
    public static void main(String[] args) {
        
            student student1 = new student("a", 27, 27.0);
            student student2 = new student("b", 15, 15.0);
            student student3 = new student("c", 19, 19.0);
            student student4 = new student("d", 18, 18.0);
            student student5 = new student("e", 28, 28.0);
            student student6 = new student("f", 34, 34.0);
            student student7 = new student("g", 65, 65.0);
    
            ArrayList<student> arrayList = new ArrayList<>();
            arrayList.add(student1);
            arrayList.add(student2);
            arrayList.add(student3);
            arrayList.add(student4);
            arrayList.add(student5);
            arrayList.add(student6);
            arrayList.add(student7);
    
    
    
            maxScoreComprator com1 = new maxScoreComprator();
            PriorityQueue<student> priorityQueue1  = new PriorityQueue<student>(3,com1);//将比较器作为实参传入
    
            int i = 0;
            while(i<3){
        
                priorityQueue1.offer(arrayList.get(i));
                i++;
            }
            while(i<arrayList.size()){
        
                if(arrayList.get(i).score<priorityQueue1.peek().score){
        
                    priorityQueue1.poll();
                    priorityQueue1.offer(arrayList.get(i));
                    i++;
                }
                else{
        
                    i++;
                }
            }
            System.out.println();
        }
    }

测试结果  
![在这里插入图片描述][c70a0f2629354bcdb448273489895ea0.png]  
此外还可以简化以下传比较器时采用匿名内部类的形式

PriorityQueue<student> priorityQueue1  = new PriorityQueue<student>(3,new Comparator<student>() {
        
                @Override
                public int compare(student o1, student o2) {
        
                    return (int) (o2.score - o1.score);
                }
            });

## 三、堆排序 ##

### 3.1问题背景 ###

有一组数据：  
27,15,191,18,28,34,65,49,25,37，对这一组数据按照从小到大排序

### 3.2误区 ###

我们想用堆排序去解决，那么首先要确定的就是用大根堆还是小根堆呢？  
一定要注意堆排序要想从大到小输出一组数据，用的不是大根堆，而是小根堆。因为实际上堆这个数据结构本身只有堆顶元素有排序意义，因为左右子树是并不知道谁大谁小的。如果用小根堆，我们只能建立另外一个数组，然后每次用这个数组去接受堆顶元素，每出堆一个就再次调整堆，这样无论是时间复杂度还是空间复杂度都是比较高的。  
那么如何用小根堆得到从大到小的排序呢

### 3.3解决办法 ###

1.  我们得到一个数组，先将其调整为小根堆，这样堆顶元素就是这里面最小的元素了；
2.  将堆顶元素与堆尾元素值互换，这样最小的元素就调整到了数组末尾；
3.  然后再次调整至小根堆（排除掉最后一个元素进行调整），这样堆顶元素就是第二小元素以此重复。

### 3.4具体代码实现 ###

堆排序的定义

//堆排序
        public void heapSort(){
        
            int end = useSize-1;
            while(end>0){
        
                swap(elem,0,end);
                shiftDown(0,end);//向下调整，具体代码看前面堆的模拟实现
                end--;
            }
        }
        //交换
        private void swap(int[] elem,int x,int y){
        
            int tmp = elem[x];
            elem[x] = elem[y];
            elem[y] = tmp;
        }

测试代码

public class HeapSort {
        
        public static void main(String[] args) {
        
            int[] arr = {
        27,15,191,18,28,34,65,49,25,37};
            TestHeap heap = new TestHeap();
            heap.initElem(arr);//初始化，具体细节可以看前面堆的模拟实现
            heap.createShortHeap();//构建小根堆，具体细节可以看前面堆的模拟实现
            heap.heapSort();
            System.out.println();
        }
    }

结果  
![在这里插入图片描述][6fc318eefb4c465796bbc8b04dba2fbb.png]

### 3.5执行过程图示 ###

![在这里插入图片描述][9977cacb28f9428b9a52601b4db24c32.png]  
至此，java堆的详解就暂告一段落啦！

[80025aefef0b4fe48419271a7fd16fb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f64bffe7c83c4433b9334c47591d0f63.png
[652eb4cf305d4938804802644bdc1dce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/78213ea398654ba6ab775b4a230efc1f.png
[50f4ed4504414216afef00f2d982d8d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ba7284e897464173802b381649ad6e27.png
[00c9a83ab9ff4ed595ba76e8eab5c6af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/dadd948a12da472bab8d7eae3b34e97d.png
[5d84674153af4ed295310de4907af117.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/23fd54834bcb496bb7f69899cafe3df4.png
[abed0b86b5e64ecea40728ed70873543.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6deded38f7c5404ab5ab98143583ef25.png
[e5f8fafd5f794414b45a2c2e8411f0f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/88f5869e606b44609b21af2557338160.png
[bb11789533e946e685a547951a625fa2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d720131ab3c4480a83bbefb8fa9c1a29.png
[00edac0074d04029bc9cb6c4992d803d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/fecf80b6fe564047b586ddcf30144e88.png
[154fd89aebe84b348441e9e19a0a5826.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5322b51e5f184a8c9594e8241d3e87cf.png
[2002bb7cd7d14e0490650d829b2630ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/797374246911493fa425a80aff77426c.png
[13bc5a0f35b54ed6809eedd84abc4c66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/003906a3b1ce473a958d14d7f3498708.png
[d06b02a68bd147948893b2ed6f368962.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8af6a9d67590443bb1583a377eb8778d.png
[59eafbc44a9e4bd095422fbcd0650170.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/20efa477b776495992af1ba1044cfcc1.png
[70de866a4a354dc287f519ac9afe4f77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2d31ee98b715438aa28fcc3a4a1f061b.png
[c68a78e5a5d44ed1946a5762276f6195.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b0270a4702384a7dad7d9ca1f10f8969.png
[a3bcd7067ccf4199b56dc5152404177e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d1824962d34b417f836f2240644333c4.png
[38c1e952fb0941a7a4d88495703fb12b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f011d8300c7b4f7ea790431f91bc7540.png
[31b10776a05c4fd98eeec5456c782af1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4350d4a3fd2b4ab8b8682ab7ce303211.png
[c70a0f2629354bcdb448273489895ea0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e758bbf7e51a4452b323599b5418de0c.png
[6fc318eefb4c465796bbc8b04dba2fbb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/18f3e8057bc04de8ae2a2b6e35753ed8.png
[9977cacb28f9428b9a52601b4db24c32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/4be8c4aa26d44fab8c03e3c514a2e91c.png