每日算法 — 使用java实现优先队列：急诊分诊与任务调度系统

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都关联一个优先级，出队时总是返回优先级最高的元素。在 Java 中，PriorityQueue 类基于二叉堆实现，提供了 (O(\log n)) 的入队和出队效率。本文将手写一个优先队列，并构建一个完整的”医院急诊分诊系统”来展示其实际应用。

二叉堆原理

优先队列的底层通常使用最小堆（或最大堆）：

• 堆性质：父节点的值总是小于（或大于）其子节点。
• 完全二叉树：除了最后一层，其他层都是满的，且最后一层的节点靠左排列。
• 数组存储：对于索引 i 处的节点，左子节点在 2i+1，右子节点在 2i+2，父节点在 (i-1)/2。

核心操作：
– 上浮（Sift Up）：新元素插入末尾，与父节点比较，若更小则交换，直到恢复堆序。
– 下沉（Sift Down）：堆顶元素移除后，将末尾元素放到堆顶，与子节点比较交换，直到恢复堆序。

手写优先队列

import java.util.Arrays;
import java.util.Comparator;

/**
 * 基于二叉堆的泛型优先队列实现
 * @param <T> 元素类型
 */
public class CustomPriorityQueue<T> {
    private static final int DEFAULT_CAPACITY = 16;
    private Object[] heap;
    private int size;
    private final Comparator<? super T> comparator;

    public CustomPriorityQueue() {
        this(null);
    }

    public CustomPriorityQueue(Comparator<? super T> comparator) {
        this.heap = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.comparator = comparator;
    }

    /**
     * 入队操作：将元素加入堆尾，然后上浮
     */
    public void offer(T element) {
        ensureCapacity();
        heap[size] = element;
        siftUp(size);
        size++;
    }

    /**
     * 出队操作：移除堆顶元素，将末尾元素移到堆顶后下沉
     */
    @SuppressWarnings("unchecked")
    public T poll() {
        if (size == 0) return null;
        T result = (T) heap[0];
        heap[0] = heap[size - 1];
        heap[size - 1] = null;
        size--;
        siftDown(0);
        return result;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        return size == 0 ? null : (T) heap[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    /**
     * 上浮：将索引 k 处的元素向上调整到正确位置
     */
    @SuppressWarnings("unchecked")
    private void siftUp(int k) {
        while (k > 0) {
            int parent = (k - 1) / 2;
            if (compare((T) heap[k], (T) heap[parent]) >= 0) {
                break; // 已满足堆序
            }
            swap(k, parent);
            k = parent;
        }
    }

    /**
     * 下沉：将索引 k 处的元素向下调整到正确位置
     */
    @SuppressWarnings("unchecked")
    private void siftDown(int k) {
        while (true) {
            int left = 2 * k + 1;
            int right = 2 * k + 2;
            int smallest = k;

            if (left < size && compare((T) heap[left], (T) heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < size && compare((T) heap[right], (T) heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest == k) break;

            swap(k, smallest);
            k = smallest;
        }
    }

    @SuppressWarnings("unchecked")
    private int compare(T a, T b) {
        if (comparator != null) {
            return comparator.compare(a, b);
        }
        return ((Comparable<? super T>) a).compareTo(b);
    }

    private void swap(int i, int j) {
        Object temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    private void ensureCapacity() {
        if (size >= heap.length) {
            heap = Arrays.copyOf(heap, heap.length * 2);
        }
    }
}

急诊分诊系统实战

在急诊室中，病人根据病情严重程度被赋予优先级：
– 危重（Critical）：心跳骤停、大出血，优先级 1
– 紧急（Urgent）：骨折、剧烈疼痛，优先级 2
– 普通（Normal）：感冒、轻微擦伤，优先级 3

/**
 * 病人实体类
 */
public class Patient implements Comparable<Patient> {
    public enum Level { CRITICAL, URGENT, NORMAL }

    private final String name;
    private final Level level;
    private final long arrivalTime; // 到达时间戳，用于同优先级时先到先服务
    private final int priorityValue;

    public Patient(String name, Level level) {
        this.name = name;
        this.level = level;
        this.arrivalTime = System.currentTimeMillis();
        this.priorityValue = switch (level) {
            case CRITICAL -> 1;
            case URGENT -> 2;
            case NORMAL -> 3;
        };
    }

    @Override
    public int compareTo(Patient other) {
        if (this.priorityValue != other.priorityValue) {
            return Integer.compare(this.priorityValue, other.priorityValue);
        }
        return Long.compare(this.arrivalTime, other.arrivalTime);
    }

    @Override
    public String toString() {
        return String.format("Patient[%s, %s]", name, level);
    }

    public String getName() { return name; }
    public Level getLevel() { return level; }
}

/**
 * 急诊分诊系统：管理病人队列，按优先级安排就诊
 */
public class EmergencyTriageSystem {
    private final CustomPriorityQueue<Patient> waitingQueue;
    private int treatedCount = 0;

    public EmergencyTriageSystem() {
        // 使用默认自然排序（Patient已实现Comparable）
        this.waitingQueue = new CustomPriorityQueue<>();
    }

    /**
     * 病人到达，加入等待队列
     */
    public void patientArrives(String name, Patient.Level level) {
        Patient patient = new Patient(name, level);
        waitingQueue.offer(patient);
        System.out.println("[到达] " + patient + " 已登记，当前等待人数: " + waitingQueue.size());
    }

    /**
     * 医生叫号：处理优先级最高的病人
     */
    public void treatNextPatient() {
        if (waitingQueue.isEmpty()) {
            System.out.println("[叫号] 当前无等待病人，医生可休息");
            return;
        }
        Patient patient = waitingQueue.poll();
        treatedCount++;
        int waitTime = (int) ((System.currentTimeMillis() - System.currentTimeMillis()) / 1000);
        System.out.println("[就诊] " + patient + " 进入诊室（累计就诊: " + treatedCount + "人）");

        // 模拟治疗时间
        int treatmentTime = switch (patient.getLevel()) {
            case CRITICAL -> 2000;
            case URGENT -> 1500;
            case NORMAL -> 1000;
        };
        try {
            Thread.sleep(treatmentTime);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        System.out.println("[完成] " + patient.getName() + " 治疗完毕，耗时 " + treatmentTime + "ms");
    }

    public void printQueueStatus() {
        System.out.println("===== 当前等待队列状态 =====");
        System.out.println("等待人数: " + waitingQueue.size());
        System.out.println("下一位优先病人: " + waitingQueue.peek());
        System.out.println("===========================");
    }

    public static void main(String[] args) {
        EmergencyTriageSystem triage = new EmergencyTriageSystem();

        // 模拟病人陆续到达
        triage.patientArrives("张三", Patient.Level.NORMAL);
        triage.patientArrives("李四", Patient.Level.CRITICAL);
        triage.patientArrives("王五", Patient.Level.NORMAL);
        triage.patientArrives("赵六", Patient.Level.URGENT);
        triage.patientArrives("孙七", Patient.Level.CRITICAL);

        System.out.println();

        // 医生依次叫号
        while (!triage.waitingQueue.isEmpty()) {
            triage.treatNextPatient();
            System.out.println();
        }
    }
}

任务调度系统扩展

优先队列同样是操作系统任务调度的核心数据结构。以下是一个简化的任务调度器，支持动态优先级调整：

/**
 * 可调度任务
 */
public class Task implements Comparable<Task> {
    private final String taskId;
    private int priority; // 数值越小优先级越高
    private int remainingTime; // 剩余执行时间（毫秒）
    private final int totalTime;

    public Task(String taskId, int priority, int totalTime) {
        this.taskId = taskId;
        this.priority = priority;
        this.totalTime = totalTime;
        this.remainingTime = totalTime;
    }

    /**
     * 执行一个时间片
     * @param timeSlice 时间片长度
     * @return 是否已完成
     */
    public boolean execute(int timeSlice) {
        int actualRun = Math.min(timeSlice, remainingTime);
        remainingTime -= actualRun;
        System.out.println("  任务 " + taskId + " 执行 " + actualRun + "ms，剩余 " + remainingTime + "ms");
        return remainingTime <= 0;
    }

    /**
     * 优先级动态提升（防止饥饿）
     */
    public void boostPriority() {
        priority = Math.max(1, priority - 1);
    }

    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }

    public String getTaskId() { return taskId; }
    public int getPriority() { return priority; }
    public int getRemainingTime() { return remainingTime; }
}

/**
 * 优先级任务调度器：模拟操作系统进程调度
 */
public class TaskScheduler {
    private final CustomPriorityQueue<Task> readyQueue;
    private int timeSlice = 500; // 默认时间片 500ms

    public TaskScheduler() {
        this.readyQueue = new CustomPriorityQueue<>();
    }

    public void submitTask(Task task) {
        readyQueue.offer(task);
        System.out.println("[提交] 任务 " + task.getTaskId() + " 进入就绪队列，优先级: " + task.getPriority());
    }

    public void run() {
        System.out.println("===== 任务调度开始 =====");
        int round = 0;
        while (!readyQueue.isEmpty()) {
            round++;
            Task current = readyQueue.poll();
            System.out.println("[调度第" + round + "轮] 执行任务: " + current.getTaskId() + "（优先级: " + current.getPriority() + "）");

            boolean finished = current.execute(timeSlice);

            if (!finished) {
                // 未完成的低优先级任务可能饥饿，适当提升优先级
                if (round % 3 == 0) {
                    current.boostPriority();
                    System.out.println("  → 优先级提升至 " + current.getPriority() + "（防饥饿机制）");
                }
                readyQueue.offer(current);
                System.out.println("  → 任务放回就绪队列");
            } else {
                System.out.println("  → 任务 " + current.getTaskId() + " 完成！");
            }
            System.out.println();
        }
        System.out.println("===== 所有任务执行完毕 =====");
    }

    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();
        scheduler.submitTask(new Task("T1-打印文档", 3, 800));
        scheduler.submitTask(new Task("T2-视频渲染", 1, 1500));
        scheduler.submitTask(new Task("T3-后台同步", 5, 600));
        scheduler.submitTask(new Task("T4-用户输入", 2, 400));
        scheduler.run();
    }
}

复杂度分析

与 Java PriorityQueue 的对比

总结

优先队列是连接抽象数据结构与真实系统的桥梁。从急诊分诊到操作系统调度，其核心逻辑始终是”按优先级高效取出元素”。理解二叉堆的上浮与下沉机制，不仅能帮助你手写优先队列，更能让你在使用 PriorityQueue、TreeSet 等容器时知其然更知其所以然。