JAVA堆以及优先级队列详解 一、堆的模拟实现1.1堆的概念1.2 堆的性质1.3堆的存储结构1.4堆的创建1.4.1 只有根节点不满足堆的特性1.4.2 不只有根节点不满足堆的特性1.4.2
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
如下图就是大根堆和小根堆
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
注意：
要完成堆的创建，首先需要了解几个完全二叉树的性质。
如上图，发现只有根节点没有满足小根堆的特性，那么我们如何将这个堆调整至符合小根堆特性呢？
要知道这些数据实际都是用数组的形式进行存储的，我们可以通过下标去访问每个数据。
public void shutDown(int parent,int useSize){ int child = 2*parent+1;//找到左孩子 while(child<useSize){//child if(child+1<useSize && elem[child]>elem[child+1]) {//child+1 child++;//elem[child] } //注意：如果不满足child+1 // 这里千万不能把if(elem[parent]>elem[child])写到if(child+1elem[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 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 if(child+1<useSize && elem[child]>elem[child+1]) {//child+1 child++;//elem[child] } //注意：如果不满足child+1 // 这里千万不能把if(elem[parent]>elem[child])写到if(child+1elem[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]+" "); } }}测试结果
如下图是上面这个例子的建立小根堆的过程
我们用满二叉树来进行分析，多几个结点不影响结果，满二叉树也方便计算
所以
首先，堆的插入一定是从堆的末尾开始插入的，不能从中间开始插入
在对末尾插入之后该堆就不一定符合小根堆的特性了，需要向上调整。
如下图
首先需要知道的是，在完全二叉树里，如果子节点的下标是i,那么该子节点对应的父节点的下标就是(i-1)/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]+" "); } }}测试结果
下图就是上述代码的执行过程
首先堆删除的元素一定是堆首元素（也就是一定是数组首元素）
堆的删除的具体操作
经过前面的代码学习，其实删除已经很简单了
向下调整的代码我们已经写过了，只需要调用即可
//删除 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 if (child + 1 < useSize && elem[child] > elem[child + 1]) {//child+1 child++;//elem[child] } //注意：如果不满足child+1 // 这里千万不能把if(elem[parent]>elem[child])写到if(child+1elem[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中堆和优先级队列是一个概念，前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)（该段引用自比特讲义）。
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安的，PriorityBlockingQueue是线程安全的。这里我们重点介绍PriorityQueue。
关于PriorityQueue的使用要注意：
import java.util.PriorityQueue;ClassCastException异常NullPointerException异常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(); }}结果
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) 返回一个包含此队列中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。
以下是原生PriorityQueue的扩容原码
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//数组的最大长度是Integer所能表示的最大值减8private 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 codeif (newCapacity - MAX_ARRAY_SIZE > 0)//如果新的容量比数组的最大容量还要大newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow 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来进行扩容
集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：
Comparble和Comparator两种方式。
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);那么底层实际上是如下图这样运行的
而这里面调用的comparaTo实际上应该是在Integer类里面进行了覆写
假如说某市进行了一次统考，有很多学生（数据量很大），那么我们如何在众多学生中迅速找到这次考试中成绩最好的50人呢？
这就要用到堆这样的数据结构了。我们将问题简化，假如有7个学生，怎么去找前k名，或者怎么找k个分数最大值、怎么找第k大值。同理又怎么去找分数最低的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里面确实是成绩最高的三名学生
找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(); }}测试结果
其实，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(); }}测试结果
此外还可以简化以下传比较器时采用匿名内部类的形式
PriorityQueue<student> priorityQueue1 = new PriorityQueue<student>(3,new Comparator<student>() { @Override public int compare(student o1, student o2) { return (int) (o2.score - o1.score); } });有一组数据：
27,15,191,18,28,34,65,49,25,37，对这一组数据按照从小到大排序
我们想用堆排序去解决，那么首先要确定的就是用大根堆还是小根堆呢？
一定要注意堆排序要想从大到小输出一组数据，用的不是大根堆，而是小根堆。因为实际上堆这个数据结构本身只有堆顶元素有排序意义，因为左右子树是并不知道谁大谁小的。如果用小根堆，我们只能建立另外一个数组，然后每次用这个数组去接受堆顶元素，每出堆一个就再次调整堆，这样无论是时间复杂度还是空间复杂度都是比较高的。
那么如何用小根堆得到从大到小的排序呢
堆排序的定义
//堆排序 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堆的详解就暂告一段落啦！
来源地址：https://blog.csdn.net/baixian110/article/details/131389759
--结束END--
本文标题: java 堆（优先级队列）详解
本文链接: https://www.lsjlt.com/news/433445.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑，方便收藏和打印～
2024-04-03
2024-04-03
2024-04-01
2024-01-21
2024-01-21
2024-01-21
2024-01-21
2023-12-23
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0