Java实现小根堆和大根堆(PriorityQueue)

小根堆和大根堆(PriorityQueue)"/>

Java实现小根堆和大根堆(PriorityQueue)

Java里面的PriorityQueue底层默认使用的堆，所以我们使用PriorityQueue就能实现堆的功能。

1、小根堆实现

package test;import java.util.Comparator;
import java.util.PriorityQueue;/*add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常offer 添加一个元素并返回true 如果队列已满，则返回falsepoll 移除并返问队列头部的元素 如果队列为空，则返回nullpeek 返回队列头部的元素 如果队列为空，则返回null*/
public class Test {public static void main(String[] args) {PriorityQueue<Integer>priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2pareTo(o1);}});for(int i = 10; i >= 0; i--){if(priorityQueue.size() < 5){priorityQueue.add(i);}else {priorityQueue.remove();priorityQueue.add(i);}}while (!priorityQueue.isEmpty()) {System.out.println(priorityQueue.remove());}}
}

2、大根堆

package test;import java.util.Comparator;
import java.util.PriorityQueue;/*add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常offer 添加一个元素并返回true 如果队列已满，则返回falsepoll 移除并返问队列头部的元素 如果队列为空，则返回nullpeek 返回队列头部的元素 如果队列为空，则返回null*/
public class Test {public static void main(String[] args) {PriorityQueue<Integer>priorityQueue = new PriorityQueue<>();for(int i = 0; i < 10; i++){if(priorityQueue.size() < 5){priorityQueue.add(i);}else {priorityQueue.remove();priorityQueue.add(i);}}while (!priorityQueue.isEmpty()) {System.out.println(priorityQueue.remove());}}
}