模拟实现优先级队列
目录
定义
在Java中，PriorityQueue 是一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时所提供的 Comparator 进行排序，具体取决于所使用的构造器。PriorityQueue 不允许 null 元素。
PriorityQueue默认是小根堆。
特点
1.无界：PriorityQueue 可以根据需要动态增长以容纳任意数量的元素。
2.基于优先级：队列中的元素按照优先级进行排序。元素的优先级可以是其自然顺序（对于实现了 Comparable 接口的元素），或者根据构造时提供的 Comparator 来确定。
3.不允许 null 元素：尝试添加 null 元素到 PriorityQueue 会抛出 NullPointerException。
4.非线程安全：如果多个线程同时访问一个 PriorityQueue 实例，并且至少有一个线程从结构上修改了队列，那么它必须保持外部同步。
为什么PriorityQueue不能够插入null对象？下面我们看一下源码：
构造函数
1.PriorityQueue()：创建一个默认初始容量的 PriorityQueue，其元素将按照其自然顺序进行排序。
2.PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的 PriorityQueue，其元素将按照其自然顺序进行排序。
3.PriorityQueue(Collection<? extends E> c)：创建一个包含指定集合元素的 PriorityQueue，其元素将按照其自然顺序进行排序。
4.PriorityQueue(int initialCapacity, Comparator<? super E> comparator)：创建一个具有指定初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。
5.PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator)：创建一个包含指定集合元素的 PriorityQueue，并根据指定的比较器对其元素进行排序。
常用方法
1.boolean add(E e)：将指定元素插入此优先级队列。
2.E poll()：检索并移除此队列的头，即在此队列中优先级最低/最高的元素。如果此队列为空，则返回 null。
3.E peek()：检索但不移除此队列的头；如果此队列为空，则返回 null。
4.int size()：返回队列中的元素数量。
5.boolean isEmpty()：如果此队列不包含任何元素，则返回 true。
6.void clear()：移除此队列中的所有元素。
关于扩容的问题
通过源码我们了解到，当容量小于64的时候，每次扩容只增加两个空间；当容量大于64的时候，每次扩容是1.5倍扩容。
并且，定义了一个常量值MAX_ARRAY_SIZE=MAX_VALUE-8，当计算后得到的新容量溢出时会抛异常OutOfMemoryError；当计算后得到的新容量大于MAX_ARRAY_SIZE时，新容量设置为MAX_VALUE。
关于建堆的问题
因为优先级队列是基于堆实现的，因此要想实现优先级队列，必须先实现建堆。
那么建立大根堆还是小根堆呢？需要根据实际需要来决定建立大根堆还是小根堆。
向上调整和向下调整的比较
那么建堆的时候使用“向上调整算法”还是“向下调整算法”呢？
下面我们分析一下二者的时间复杂度：
向下调整算法：时间复杂度为N
向上调整算法：时间复杂度为N*logN
显然，使用“向下调整”比“向上调整”更好。
（向上调整）代码
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if (elem[child] > elem[parent]) {
swap(child,parent);
child = parent;
parent = (child-1)/2;
} else {
break;
}
}
}
private void swap(int i,int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}（向下调整）代码
private void shiftDown(int parent, int usedSize) {
int child = (2*parent)+1;//左孩子下标
while (child < usedSize) {
if(child+1 < usedSize && elem[child] < elem[child+1]) {
child++;
}
//child一定是 左右孩子最大值的下标
if(elem[child] > elem[parent]) {
swap(child, parent);
parent = child;
child = 2*parent+1;
}else {
//已经是大根堆了
break;
}
}
}
private void swap(int i,int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}关于入队列和出队列问题
策略：
针对入队列：将要插入的元素放到堆尾，然后对该位置进行“向上调整”即可；
针对出队列：将要删除的元素（即堆顶元素）和堆尾元素进行交换，然后把队列的大小-1，然后从堆顶进行“向下调整”即可。
模拟实现优先级队列代码
public class TestHeap {
private int[] elem;
private int usedSize;
public TestHeap() {
this.elem = new int[10];
}
public void initHeap(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);
}
}
private void shiftDown(int parent, int usedSize) {
int child = (2*parent)+1;//左孩子下标
while (child < usedSize) {
if(child+1 < usedSize && elem[child] < elem[child+1]) {
child++;
}
//child一定是 左右孩子最大值的下标
if(elem[child] > elem[parent]) {
swap(child, parent);
parent = child;
child = 2*parent+1;
}else {
//已经是大根堆了
break;
}
}
}
private void swap(int i,int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
public void offer(int val) {
if(isFull()) {
this.elem = Arrays.copyOf(elem,2*elem.length);
}
this.elem[usedSize] = val;//usedSize=10
//向上调整
shiftUp(usedSize);
usedSize++;
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if (elem[child] > elem[parent]) {
swap(child,parent);
child = parent;
parent = (child-1)/2;
} else {
break;
}
}
}
public boolean isFull() {
return usedSize == elem.length;
}
public int poll() {
int tmp = elem[0];
swap(0,usedSize-1);
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public void heapSort() {
int end = usedSize-1;
while (end > 0) {
swap(0,end);
shiftDown(0,end);
end--;
}
}
}关于堆排序的问题
上面我们分析了“向上调整”和“向下调整”的时间复杂度，我们知道“向下调整”优于“向上调整”，下面将使用“向下调整”来实现堆排序。
实现堆排序的步骤：
1.首先建好堆
2.其次定义一个变量end标记最后一个元素的位置
3.然后交换堆顶和堆尾的元素
4.然后对堆顶位置进行向下调整，end--；
5.重复执行步骤3,4,5，直到end=0
堆排序代码
public void heapSort() {
int end = usedSize-1;
while (end > 0) {
swap(0,end);
shiftDown(0,end);
end--;
}
}
private void shiftDown(int parent, int usedSize) {
int child = (2*parent)+1;//左孩子下标
while (child < usedSize) {
if(child+1 < usedSize && elem[child] < elem[child+1]) {
child++;
}
//child一定是 左右孩子最大值的下标
if(elem[child] > elem[parent]) {
swap(child, parent);
parent = child;
child = 2*parent+1;
}else {
//已经是大根堆了
break;
}
}
}
private void swap(int i,int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}关于对象的比较
基于Comparable的比较
对于自定义类型，如果要对其进行比较，需要实现Comparable的compareTo方法。
代码示例
public class Person implements Comparable<Person> {
private String name;
private int age;
// 构造器、getter和setter省略
@Override
public int compareTo(Person o) {
return this.age - o.age; // 以年龄为基准进行比较
}
}
// 使用示例
Person p1 = new Person("Alice", 30);
Person p2 = new Person("Bob", 25);
System.out.println(p1.compareTo(p2)); // 输出正数，因为p1的年龄大于p2基于Comparator的比较
对于自定义类型，如果要对其进行比较，需要实现Comparator的compare方法。
代码示例
import java.util.Comparator;
public class Person {
private String name;
private int age;
// 构造器、getter和setter省略
// 使用Comparator进行比较
public static Comparator<Person> byName = new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
return p1.getName().compareTo(p2.getName());
}
};
// 或者使用Lambda表达式（Java 8+）
public static Comparator<Person> byAge = (Person p1, Person p2) -> Integer.compare(p1.getAge(), p2.getAge());
}
// 使用示例
Person p1 = new Person("Alice", 30);
Person p2 = new Person("Bob", 25);
System.out.println(Person.byName.compare(p1, p2)); // 按名字比较
System.out.println(Person.byAge.compare(p1, p2)); // 按年龄比较原文地址：https://blog.csdn.net/wmh_1234567/article/details/141270253
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！