- 1.优先级队列
- 2.堆
- 2.1堆的概念
- 2.2向下调整
- 2.3将数组元素—建堆
- 2.4向上调整
- 2.5堆的简单实现
==============================================================================
1.优先级队列- 优先级队列：进入队列的数据存在各种各样的优先级，比如大小，规定出队列的时候必须按照优先级大小出；这样的队列称为优先级队列；
- Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的；
- 没有容量限制，可以自动扩容；
- 插入删除的时间复杂度为O(log_2N)；
- 其底层实现使用的数据结构为——堆；
// 由于优先级队列与队列与链表类的关系如下：
//由于创建一般队列实例化类为linkedList<>();创建优先级队列实例化为PriorityQueue<>();因为都是实现了接口Queue而来的类，故在方法和实现上一般通用，插入删除可以用add()/offer()-remove()/poll();
例1：
- 不能插入null对象，否则抛出NullPointerException异常；
例2：
- 可以看出对于Java内置类型，Java内部类PriorityQueue中定义了相关Complare()方法进行比较；
例3：
class Student{
public String name;
public int id;
public int age;
public int score;
public Student(String name, int id, int age, int score) {
this.name = name;
this.id = id;
this.age = age;
this.score = score;
}
}
- 如上例所示 ，优先级队列必须插入的数据类型是可比较大小的，否则抛出 ClassCastException异常；
- 对于自定义对象常见优先级队列时，需要自定义优先级规则：
- 方法1：让自定义类型实现接口Complarable->再重写比较方法compareTo();
class Student implements Comparable{ public String name; public int id; public int age; public int score; public Student(String name, int id, int age, int score) { this.name = name; this.id = id; this.age = age; this.score = score; } @Override public String toString() { return "{" + name + ''' + id +''' + age +''' + score +'}'; } @Override public int compareTo(Student o) { //通过学生学号出队列 return this.id-o.id; // //通过学生年龄排序 // return this.age-o.age; // //通过学生成绩排序 // return this.score-o.score; // //通过学生名字排序 // return this.name.compareTo(o.name); } } public class Main { public static void main(String[] args) { Queue qq=new java.util.PriorityQueue<>(); qq.offer(new Student("C",1,19,90)); qq.offer(new Student("X",0,19,60)); qq.offer(new Student("Z",3,18,99)); qq.offer(new Student("A",2,17,59)); while (!qq.isEmpty()) { System.out.println(qq.poll()); } } }
* 方法2：创建一个类用于实现Comparator接口，在其类内重写实现compare()方法；
class Student {
public String name;
public int id;
public int age;
public int score;
public Student(String name, int id, int age, int score) {
this.name = name;
this.id = id;
this.age = age;
this.score = score;
}
@Override
public String toString() {
return "{" + name + ''' + id +''' + age +''' + score +'}';
}
}
class StudentComparator implements Comparator{
@Override
public int compare(Student o1, Student o2) {
//根据学生数据的年龄排序：
return o1.age-o2.age;
}
}
public class Main {
public static void main(String[] args) {
Queue qq=new java.util.PriorityQueue<>(new StudentComparator());
qq.offer(new Student("C",1,19,90));
qq.offer(new Student("X",0,19,60));
qq.offer(new Student("Z",3,18,99));
qq.offer(new Student("A",2,17,59));
while (!qq.isEmpty()) {
System.out.println(qq.poll());
}
}
}
// 在创建优先队列时，将自定义的排序类对象传给优先队列对象；
// 更为方便的方法——仍然使用Comparator接口实现重写比较函数compare()，但是在可以在创建优先队列时同时定义：
// 也可以直接省略方法重新重写的步骤：
- 如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树，可以高效的利用层序遍历的方法存储元素；
- 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
- 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
- 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
- 举例：大堆(前提是，调整位置的两个子树已满足大堆)；
// 大堆：每一个节点的值均大于左右子节点的值；
// 故进行向下调整时，需要判断当前调整的起始节点位置index，作为当前根节点与左右子节点(2*index)+1/+2;如果左右子节点其中有比当前值大的，则交换；每一次都想下更新当前节点；
// 不许要调整，仍满足大堆要求，则调整结束，break跳出；
// 同理：
//向下调整，为大堆(前提是，调整位置的两个子树已满足大堆)
public static void shiftDown(int[] arr,int size,int index){
int parent=index;
int child = (2 * index) + 1;
while (index < size) {
//为了找到左右子树中最大的节点=child，进而与parent(调整位置）进行比较大小；
if(child+1arr[child+1]){
child=child+1;
}
//交换三连：
if(arr[parent]
2.3将数组元素—建堆
- 递归思想：将整个数组建堆（二叉树），向下调整的前提是当前节点左右子树已经满足大堆的要求，故建堆时，需要找到第一个非叶子节点，进行向下调整->在进行递归调整每一个非叶子节点；
//堆的创建（向下调整）
public static void createHeap(int[] arr){
//从第一个非叶子节点比较判断，向下调整
for(int i=(arr.length-1-1)/2;i>=0;i--){
shiftDown(arr,arr.length-1,i);
}
}
2.4向上调整
- 向上调整：在当前堆末尾插入一个新元素时，向上调整使其满足大堆要求；
- 当前index位置的值与其父节点比较判断大小；(只与父结点比较是因为没插入之前已经为大堆，父节点元素值是其左右子树节点中最大的);
//向上调整（将当前节点和其父节点比较，比父节点大，则交换）
public static void shiftUp(int[] arr,int size,int index){
int child=index;
int parent=(index-1)/2;
while(parent>0){
if(arr[parent]
2.5堆的简单实现
import java.util.Arrays;
//优先级队列：实际上是一个数组表示的二叉树，这样的完全二叉树数组表示称为堆，堆有大小堆之分；
public class MyPriorityQueue {
private int[] arr;
private int size;
private int capacity=3;
public MyPriorityQueue() {
arr=new int[capacity];
}
//向下调整，为大堆(前提是，调整位置的两个子树已满足大堆)
public static void shiftDown(int[] arr,int size,int index){
int parent=index;
int child = (2 * index) + 1;
while (index < size) {
if(child+1arr[child+1]){
child=child+1;
}
if(arr[parent]=0;i--){
shiftDown(arr,arr.length-1,i);
}
}
//向上调整（将当前节点和其父节点比较，比父节点大，则交换）
public static void shiftUp(int[] arr,int size,int index){
int child=index;
int parent=(index-1)/2;
while(parent>0){
if(arr[parent]=arr.length){
//扩容；
arr=reallocate(arr);
}
arr[size++]=e;
size++;
//向上调整
shiftUp(arr,size,size-1);
}
//使用向上调整创建堆：
public void createHeap2(int[] arr){
for(int x:arr){
offer(x);
}
}
//获取队首元素
public Integer getPeek(){
if (size==0){
return null;
}
return arr[0];
}
//删除队首（堆头）元素（将堆头元素与末尾元素交换，在进行向下调整）
public Integer poll(){
if (size == 0) {
return null;
}
int tmp=arr[0];
arr[0]=arr[size-1];
arr[size-1]=tmp;
size--;
shiftDown(arr,size,0);
return tmp;
}
}
