Skip to main content
 首页 » 编程设计

java算法之自定义最小优先队列

2022年07月18日28webabcd
 
 
**
* @desc: 最小优先队列,值越小,优先级越高,其实就是构造小顶堆
* @author: 毛会懂
* @create: 2021-01-06 16:34:00
**/
public class MyMinPriorityQueue<T extends Comparable<T>> {
private T[] arr;
private Integer size;

public MyMinPriorityQueue(Integer size){
arr = (T[])new Comparable[size];
this.size = 0;
}

//队列是否为空
public Boolean isEmpty(){
return size == 0;
}

//队列的大小
public Integer getSize(){
return size;
}

//插入元素
public void add(T t){
//插入到数组的末尾(数组的第0个元素不存储,方便元素的上浮和下沉)
arr[++size] = t;
//上浮
swim(size);
}

//删除最小元素
public T delMin(){
if(size == 0){
return null;
}
T t = arr[1];
//最大的元素(第1个位置)和最后一个元素做交换
exec(1,size);
size--;
//下沉第一个位置的元素
sink(1);
return t;
}

//上浮
public void swim(Integer k){
while (k > 1){
if(less(k,k/2)){
exec(k,k/2);
}
k = k /2;
}
}


//下沉
public void sink(Integer k){
while (2 * k <= size){
int max;
if(2 * k + 1 <= size) {
if (less(2 * k, 2 * k + 1)) {
max = 2 * k;
} else {
max = 2 * k + 1;
}
}else{
max = 2 * k;
}
if(less(max,k)){
exec(max,k);
}
k = max;
}
}

//比较两个元素的大小(arr[i]小,返回True)
private Boolean less(int i,int j){
return arr[i].compareTo(arr[j]) < 0;
}

//交换两个元素位置
private void exec(int i,int j){
T t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
 

测试代码:

//最小优先队列
public static void main(String[] args) {
char[] chars = {'A','H','D','O','E','W','G','T'};
MyMinPriorityQueue<Character> myHeap = new MyMinPriorityQueue<>(20);
for(int i = 0;i < chars.length;i++){
myHeap.add(chars[i]);
}

System.out.println("---------");

for(int i = 0;i < chars.length;i++){
System.out.print(myHeap.delMin() + ", ");
}
System.out.println("over");
}

本文参考链接:https://www.cnblogs.com/maohuidong/p/14245962.html