快捷導(dǎo)航

Java堆&優(yōu)先級隊列示例講解(下)

更新時間：2022年03月18日 11:23:49 作者：愛干飯的猿

這篇文章主要通過示例詳細(xì)為大家介紹Java中的堆以及優(yōu)先級隊列，文中的示例代碼講解詳細(xì)，對我們了解java有一定幫助，需要的可以參考一下

1.優(yōu)先級隊列

1.1 概念

在很多應(yīng)用中，我們通常需要按照優(yōu)先級情況對待處理對象進(jìn)行處理，比如首先處理優(yōu)先級最高的對象，然后處理次高的對象。最簡單的一個例子就是，在手機(jī)上玩游戲的時候，如果有來電，那么系統(tǒng)應(yīng)該優(yōu)先處理打進(jìn)來的電話。在這種情況下，我們的數(shù)據(jù)結(jié)構(gòu)應(yīng)該提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這種數(shù)據(jù)結(jié)構(gòu)就是優(yōu)先級隊列(Priority Queue)。

1.2 內(nèi)部原理

優(yōu)先級隊列的實現(xiàn)方式有很多，但最常見的是使用堆來構(gòu)建。

1.3 操作-入隊列

過程（以大堆為例）：

1. 首先按尾插方式放入數(shù)組

2. 比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質(zhì)，插入結(jié)束

3. 否則，交換其和雙親位置的值，重新進(jìn)行 2 、 3 步驟

4. 直到根結(jié)點(diǎn)

圖示：

1.4 操作-出隊列（優(yōu)先級最高）

為了防止破壞堆的結(jié)構(gòu)，刪除時并不是直接將堆頂元素刪除，而是用數(shù)組的最后一個元素替換堆頂元素，然后通過向下調(diào)整方式重新調(diào)整成堆

1.5 借用堆實現(xiàn)優(yōu)先級隊列

1.實現(xiàn)一個接口

public interface IQueue<E> {
    // 入隊
    void offer(E val);
    //出隊
    E poll();
    //返回隊首元素
    E peek();
    //判斷隊列是否為空
    boolean isEmpty();
}

2.堆完整代碼見Java堆&優(yōu)先級隊列示例講解(上)

3.優(yōu)先級隊列

/**
 * 基于最大堆的優(yōu)先級隊列,值越大優(yōu)先級越高
 * 隊首元素就是優(yōu)先級最大的元素(值最大)
 */
 
import stack_queue.queue.IQueue;
 
public class PriorityQueue implements IQueue<Integer> {
    MaxHeap heap = new MaxHeap();
    public PriorityQueue(){
        heap = new MaxHeap();
    }
 
    @Override
    public void offer(Integer val) {
        heap.add(val);
    }
 
    @Override
    public Integer poll() {
        return heap.extractMax();
    }
 
    @Override
    public Integer peek() {
        return heap.peekMax();
    }
 
    @Override
    public boolean isEmpty() {
        return heap.isEmpty();
    }
}

1.6 測試

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueTest {
    public static void main(String[] args) {
        // 通過構(gòu)造方法傳入比較器
        // 默認(rèn)是最小堆，"值"(比較器compare的返回值)越小，優(yōu)先級就越高
        // 當(dāng)傳入一個降序的比較器時,值(比較器compare的返回值，值越大，返回負(fù)數(shù))
//        Queue<Student> queue = new PriorityQueue<>(new StudentComDesc());
//        Queue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {
//            @Override
//            public int compare(Student o1, Student o2) {
//                return o2.getAge() - o1.getAge();
//            }
//        });
        Queue<Student> queue = new PriorityQueue<>(new StudentCom());
        Student stu1 = new Student(18,"雷昊");
        Student stu2 = new Student(20,"張超");
        Student stu3 = new Student(16,"鉞浦");
        queue.offer(stu1);
        queue.offer(stu2);
        queue.offer(stu3);
        while (!queue.isEmpty()){
            System.out.println(queue.poll());
        }
    }
}
 
//升序（最小堆）
class StudentCom implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getAge() - o2.getAge();
    }
}
 
//降序（最大堆）
class StudentComDesc implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o2.getAge() - o1.getAge();
    }
}
 
class Student{
    private int age;
    private String name;
 
    public int getAge() {
        return age;
    }
 
    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

結(jié)果如下：Java堆&優(yōu)先級隊列示例講解(上)