1. Toy模板网首页
  2. > Toy博客

java 堆（优先级队列）详解

9月前 作者：baixian110 分类：Toy博客 阅读(43) 违法举报

这篇具有很好参考价值的文章主要介绍了java 堆（优先级队列）详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、堆的模拟实现

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 堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
如下图就是大根堆和小根堆
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

1.3堆的存储结构

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序注意：

  • 对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
  • 将元素存储到数组中后，可以根据二叉树章节的性质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 只有根节点不满足堆的特性

java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序如上图，发现只有根节点没有满足小根堆的特性，那么我们如何将这个堆调整至符合小根堆特性呢？
要知道这些数据实际都是用数组的形式进行存储的，我们可以通过下标去访问每个数据。

  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里面是从最后的父节点一路往前调整的，所以后面的一定满足小根堆的特性
                }
        }
    }
}

测试代码

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.elem.length; i++) {
            System.out.print(testHeap.elem[i]+" ");
        }
        System.out.println();
        testHeap.createShortHeap();
        for (int i = 0; i < testHeap.elem.length; i++) {
            System.out.print(testHeap.elem[i]+" ");
        }
    }
}

测试结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

1.4.2.2 建堆过程图示

如下图是上面这个例子的建立小根堆的过程
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

1.4.3 建堆的时间复杂度

我们用满二叉树来进行分析，多几个结点不影响结果，满二叉树也方便计算
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序
所以
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

1.5堆的插入

1.5.1堆的插入的基本思想

首先，堆的插入一定是从堆的末尾开始插入的，不能从中间开始插入
在对末尾插入之后该堆就不一定符合小根堆的特性了，需要向上调整。
如下图
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序
首先需要知道的是，在完全二叉树里，如果子节点的下标是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]+" ");
        }
    }
}

测试结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

1.5.3堆的插入的过程图示

下图就是上述代码的执行过程
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

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里面是从最后的父节点一路往前调整的，所以后面的一定满足小根堆的特性
            }
        }
    }

测试代码

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]+" ");
        }
        System.out.println();
        testHeap.poll();
        for (int i = 0; i < testHeap.useSize; i++) {
            System.out.print(testHeap.elem[i]+" ");
        }
    }
}

结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

1.6.3堆的删除的过程图示

java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

二、优先级队列

2.1优先级队列的概念

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

2.2优先级队列的常用接口

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安的，PriorityBlockingQueue是线程安全的。这里我们重点介绍PriorityQueue。
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

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();
        
    }
}

结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

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 final int DEFAULT_INITIAL_CAPACITY = 11;
   // 内部定义的比较器对象，用来接收用户实例化PriorityQueue对象时提供的比较器对象 
   private final 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);

那么底层实际上是如下图这样运行的
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序而这里面调用的comparaTo实际上应该是在Integer类里面进行了覆写
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

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里面确实是成绩最高的三名学生
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

2.8.2找k个最小值

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

student类的定义：

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)(o.score-this.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();
    }
}

测试结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

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();
    }
}

测试结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序
此外还可以简化以下传比较器时采用匿名内部类的形式

 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();
    }
}

结果
java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序

3.5执行过程图示

java 堆,数据结构,java,数据结构,堆,优先级对列,heap,PriorityQueue,堆排序
至此，java堆的详解就暂告一段落啦！文章来源地址https://www.toymoban.com/news/detail-719595.html

到了这里，关于java 堆（优先级队列）详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构：优先级队列（堆）

    数据结构：优先级队列（堆）

    队列是一种先进先出 (FIFO) 的数据结构 ，但有些情况下， 操作的数据可能带有优先级，一般出队 列时，可能需要优先级高的元素先出队列。 在这种情况下， 数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象 。这种数据结构就是 优先级

    2024年02月08日
    浏览(41)

  • 数据结构与算法-优先级队列

    Gitee上开源的数据结构与算法代码库：数据结构与算法Gitee代码库 优先级队列，按照优先级别依次输出 计算机科学中，堆是一种基于树的数据结构，通常用 完全二叉树 实现。堆的特性如下 在大顶堆中，任意节点 C 与它的父节点 P 符合 P . v a l u e ≥ C . v a l u e P.value geq C.val

    2024年02月13日
    浏览(43)
  • 数据结构之优先级队列【堆】（Heap）

    数据结构之优先级队列【堆】（Heap）

    目录 1. 优先级队列（Priority Queue） 2.堆的概念 3.堆的存储方式 4.堆的创建 5.用堆模拟实现优先级队列  6.PriorityQueue常用接口介绍 6.1 PriorityQueue的特点 6.2 PriorityQueue几种常见的构造方式 7.top-k问题 8.堆排序 本篇主要内容总结 （1）优先级队列底层是堆来实现的 （2）堆的本质是

    2024年02月01日
    浏览(53)
  • 数据结构 之 优先级队列(堆) (PriorityQueue)

    数据结构 之 优先级队列(堆) (PriorityQueue)

    🎉欢迎大家观看AUGENSTERN_dc的文章(o゜▽゜)o☆✨✨ 🎉感谢各位读者在百忙之中抽出时间来垂阅我的文章，我会尽我所能向的大家分享我的知识和经验📖 🎉希望我们在一篇篇的文章中能够共同进步！！！ 🌈个人主页：AUGENSTERN_dc 🔥个人专栏：C语言 | Java | 数据结构 ⭐个人

    2024年03月20日
    浏览(48)
  • 【数据结构与算法】03 队列（顺序队列--循环队列--优先级队列--链队列）

    【数据结构与算法】03 队列（顺序队列--循环队列--优先级队列--链队列）

    队列（ queue ）是一种常见的数据结构，它遵循先进先出（FIFO）的原则。队列可以理解为一个具有两个端点的线性数据结构，其中一个端点称为\\\"队尾\\\"（rear），用于插入新元素，另一个端点称为\\\"队首\\\"（front），用于移除元素。新元素被插入到队尾，而最早插入的元素总是在队

    2024年02月08日
    浏览(52)
  • java 堆（优先级队列）详解

    java 堆（优先级队列）详解

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

    2024年02月08日
    浏览(43)
  • 【一起学习数据结构与算法】优先级队列(堆)

    【一起学习数据结构与算法】优先级队列(堆)

    如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了 优先级队列 这种数据结构。 优先级队列（priority queue） 是0个或多个元素的集

    2024年01月19日
    浏览(41)
  • 【数据结构】 优先级队列(堆)与堆的建立

    【数据结构】 优先级队列(堆)与堆的建立

    前面介绍过队列， 队列是一种先进先出(FIFO)的数据结构 ，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适。 比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话

    2024年02月10日
    浏览(39)
  • 【数据结构初阶】——第八节.优先级队列（小根堆的模拟实现）

    【数据结构初阶】——第八节.优先级队列（小根堆的模拟实现）

     作者简介：大家好，我是未央； 博客首页： 未央.303 系列专栏：Java初阶数据结构 每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！ 目录 文章目录 前言 引言 一、堆的概念 二、堆的性质  三、堆的操作 3.1 向下调整算法 3.2 小根堆的创建 3.3 向上调整

    2024年02月07日
    浏览(48)
  • 经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

    经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

    前言： 本篇文章以 TopK 问题为引，具体阐述了 PriorityQueue 实现的基本逻辑——堆 数据结构，以及PriorityQueue 的常用方法。如有问题欢迎看官朋友指正，如果觉得文章还不错的话，求点赞、收藏、评论 三连。 重点： 堆的基本实现逻辑 PriorityQueue 运用和源码分析 TopK 问题的解法

    2023年04月22日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包