文章目录
1.优先级队列
1.1概念
队列是先进先出的数据结构，有些情况下数据是带有优先级的，一般出队列时，优先级高的元素先出队列
数据结构应该提供两个基本的数据结构，一个是返回最高优先级对象，一个是添加新的对象，这种数据结构就是优先级队列(Priority Queue)
2.Priority Queue模拟实现
PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调 整
2.1堆的概念
1.是一种特殊的二叉树（完全二叉树）
2.通过数组的方式顺序存储
3.对于这个数的任意节点来说，满足根节点大于左右子树的值（大堆），或者任意一节点满足根节点的值小于左右子树的值（小堆）
2.2堆的存储方式
堆是一个完全二叉树，因此层序的规则采用顺序的方式存储比较高效
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节 点，就会导致空间利用率比较低
将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
2.3创建堆
以大堆为例创建堆
数据为集合{ 27,15,19,18,28,34,65,49,25,37 }
元素存储到数组中：
还原成二叉树：
想要创建大堆，那么每颗子树都得是大根堆，现在需要在二叉树中进行调整
从最后一个子树开始调节，全都调整为大根堆
如何调整最后一个子树？
利用二叉树性质，最后一个节点和他的父亲节点下标关系为：（len - 1 - 1）/ 2，找到父亲节点然后自减后可以调整每个父亲节点
代码
test
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);
testHeap.createHeap();
System.out.println("++++++++++");
}
}
TestHeap
class TestHeap{
public int[] elem;
public int usedSize;//有效数据的个数
public static final int DEFAULT_SIZE = 10;
public TestHeap(){
this.elem = new int[DEFAULT_SIZE];
}
public void initElem(int[] array){
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
}
public void createHeap(){
for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
//调整方案
shiftDown(parent,usedSize);
}
}
/**
* @param parent：根节点
* @param len：子树调整的结束位置不能>len
*要注意怎么判断什么时候没有子树的条件
*/
private void shiftDown(int parent,int len){
int child = 2*parent+1;
while(child < len){
//防止越界
//child+1 < len &&保证有右孩子
if(child+1 < len && elem[child] < elem[child+1]){
child++;
}
//child一定最大值
if (elem[child] > elem[parent]) {
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
//更新，当前子树也有左右子树，不更新只是调整了当前子树
parent = child;
child = 2*parent+1;
}
//当都为大根堆时直接跳出
else{
break;
}
}
}
}
调试
可以看出已经创建了大根堆
最坏的情况即从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为log2(N)
2.4堆的插入与删除
2.4.1堆的插入
堆的插入总共需要两个步骤：
先将元素放入到底层空间中(注意：空间不够时需要扩容)
将最后新插入的节点向上调整，直到满足堆的性质
插入一个元素之后，仍然要保证这个堆是一个大根堆
插入后：
代码
//插入
private void offer(int val){
//判满
if(isFull()){
//扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
//插入
elem[usedSize] = val;
//有效数据加一
usedSize++;
//调整为大根堆
shiftUp(usedSize-1);
}
private void shiftUp(int child){
int parent = (child-1)/2;
//parent>=0也可作为条件，parent=0时也要进行调整
while(child>0){
if(elem[child]>elem[parent]){
//交换
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
//更新要调整的子树节点
child = parent;
parent = (child-1)/2;
}
//已经是大根堆直接跳出
else{
break;
}
}
}
private boolean isFull(){
//当有效数据=数组长度时就满了
return usedSize == elem.length;
}
调试
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);
testHeap.createHeap();
System.out.println("++++++++++");
testHeap.offer(80);
}
}
插入成功并且调整为大根堆
2.4.2堆的删除
注意：堆的删除一定删除的是堆顶元素
具体如下：
将堆顶元素对堆中最后一个元素交换
将堆中有效数据个数减少一个
对堆顶元素进行向下调整
代码
//删除
public int pop(){
//判断是否为空
if(isEmpty()){
return -1;
}
//将要删除的节点的值交换到最后一个位置并删除
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;
//向下调整保证仍然是大根堆
shiftDown(0,usedSize);
return tmp;
}
private boolean isEmpty(){
return usedSize == 0;
}
调试
删除前
删除后
2.4.3 peek方法
不为空直接返回elem[0]
//peek
public int peek(){
if(isEmpty()){
return -1;
}
return elem[0];
}
3.常见习题
已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是()A: 1B: 2C: 3D: 4
第一次比较：15和10 谁小
第二次比较：10和12谁小
第三次比较：12和16谁小
选c
4.PriorityQueue的特性
PriorityQueue的使用要注意：
使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
不能插入null对象，否则会抛出NullPointerException
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入和删除元素的时间复杂度为O(log2(N))
PriorityQueue底层使用了堆数据结构
PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
建一个优先级队列并测试
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(100);
priorityQueue.offer(2);
priorityQueue.offer(3);
System.out.println(priorityQueue.poll());
}
默认是小堆，则弹出最小的值2
当对象是引用类型时需要实现接口来比较
public class Test {
public static void main(String[] args) {
PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(new Student(10));
priorityQueue.offer(new Student(12));
System.out.println("+++++++++");
}
}
class Student implements Comparable<Student>{
public int age;
public Student(int age) {
this.age = age;
}
@Override
public int compareTo(Student o) {
return this.age-o.age;
}
}
还是默认的小根堆
compareTo()方法是在那里被调用？我们看一下源码
也可以传比较器
```hljs
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
原文链接: https://blog.csdn.net/chenchenchencl/article/details/127380833