二叉堆与优先队列（三）-- HDU-6000-Wash-java

前言

前两节已经分析过题解，也梳理了二叉堆与优先队列的实现方式，今天完成洗衣机烘干机的问题。

题目

后来我查，这是一道ACM的题，原题链接

• 1、有m个洗衣机，每台洗衣机只能一件一件洗，没台洗衣机的时间不同。
• 2、有n个烘干机，每台烘干机只能一件一件烘干，没台烘干机的时间不同。
• 3、一共有x件衣服，每件衣服要先洗干净，然后再烘干。
• 求：处理完所有衣服最少的时间是多少？

实现

public class WashTest {

    // m个洗衣机
    private static final int COUNT_M = 0;
    // n个烘干机
    private static final int COUNT_N = 0;
    // x件衣服
    private static final int COUNT_L = 0;

    // m个洗衣机,数组记录每个洗衣机耗时时间
    int[] m = new int[COUNT_M];
    // m个洗衣机,数组记录每个洗衣机耗时时间
    int[] n = new int[COUNT_N];

    int getTotalCostTime(int[] m, int[] n, int l) {
        // 构建洗衣机最小堆
        PriorityQueue washPQ = new PriorityQueue<WashModel>(m.length);
        for (int i = 0; i < m.length; i++) {
            WashModel washModel = new WashModel(i, m[i]);
            washPQ.push(washModel);
        }
        // 构建烘干机最小堆
        PriorityQueue hongPQ = new PriorityQueue<WashModel>(n.length);
        for (int i = 0; i < n.length; i++) {
            WashModel washModel = new WashModel(i, n[i]);
            hongPQ.push(washModel);
        }

        // 存储每件衣服洗涤的时间
        int[] costL = new int[l];
        for (int i = 0; i < l; i++) {
            // 取出当前洗完最快就绪的洗衣机
            WashModel washModel = (WashModel) washPQ.pop();
            // 记录
            costL[i] = washModel.getTime();
            // 将当前衣服重新加入最小堆
            washModel.setTime(washModel.getTime() + m[washModel.getIndex()]);
            washPQ.push(washModel);
        }
        // 记录耗时最长的一件衣服
        int res = 0;
        // 倒着从洗衣机完成的衣服中取出,让最后意见洗完的衣服找到最快的烘干机
        for (int i = l - 1; i >= 0; i--) {
            // 取出当前洗完最快就绪的洗衣机
            WashModel washModel = (WashModel) hongPQ.pop();
            // 比较每一件衣服烘干完的时间
            res = Math.max(res,washModel.getTime()+costL[i]);
            // 加上烘干时间
            washModel.setTime(washModel.getTime()+n[washModel.getIndex()]);
            // 重新插入优先队列
            hongPQ.push(washModel);
        }
        return res;
    }


    class WashModel implements Comparable<WashModel> {

        private int index;
        private int time;

        public WashModel(int index, int time) {
            this.index = index;
            this.time = time;
        }


        @Override
        public int compareTo(WashModel o) {
            return this.time - o.time;
        }

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public int getTime() {
            return time;
        }

        public void setTime(int time) {
            this.time = time;
        }
    }

}

class BinaryHeap<T extends Comparable> {
    // 用数组作为二叉堆的底层存储结构
    private T[] values;

    // 当前二叉堆实际存储的元素数量
    private int count;

    // 构造函数,初始化是决定堆大小
    public BinaryHeap(int capacity) {
        this.values = (T[]) new Comparable[capacity + 1];
    }

    /**
     * 取出堆顶元素
     *
     * @return
     */
    public T pop() {
        // 先取出堆顶元素
        T result = values[1];
        // 和堆底元素进行交换
        exchange(1, count);
        // 清除堆顶元素(此时堆顶元素在堆底)
        values[count--] = null;
        // 将新插入的元素进行下沉
        down(1);
        return result;
    }


    /**
     * 插入元素
     *
     * @param target
     */
    public void insert(T target) {
        // 将新元素添加在最后
        values[++count] = target;
        // 上浮新插入的元素
        up(count);
    }


    /**
     * 获取target的父节点下标
     *
     * @param target
     * @return
     */
    private int parent(int target) {
        return target / 2;
    }

    /**
     * 获取target的左节点下标
     *
     * @param target
     * @return
     */
    private int left(int target) {
        return target * 2;
    }

    /**
     * 获取target的右节点下标
     *
     * @param target
     * @return
     */
    private int right(int target) {
        return target * 2 + 1;
    }

    /**
     * 上浮
     *
     * @param target
     */
    private void up(int target) {
        // target = 1 时代表到了堆顶,不再交换
        // 与父节点比较,直到一个比自己小的父节点
        while (target > 1 && large(parent(target), target)) {
            exchange(parent(target), target);
        }
    }

    /**
     * 下沉
     *
     * @param target
     */
    private void down(int target) {
        // 判断是否已经到了堆底
        while (left(target) <= count) {
            // 找到左右节点的较小节点
            int smaller = left(target);
            if (right(target) <= count && large(smaller, right(target))) {
                smaller = right(target);
            }
            // 和左右子节点中较小的比较,如果比较小的小,就不需要下沉了
            if (large(smaller, target)) {
                return;
            }
            // 与较小的子节点交换位置
            exchange(smaller, target);
            // 更新要比较的目标节点坐标
            target = smaller;
        }
    }

    /**
     * 交换两节点位置
     *
     * @param index1
     * @param index2
     */
    private void exchange(int index1, int index2) {
        T tmp = values[index1];
        values[index1] = values[index2];
        values[index2] = values[1];
    }

    /**
     * 比较两节点大小
     *
     * @param index1
     * @param index2
     * @return
     */
    private boolean less(int index1, int index2) {
        // 返回index1的值是否比index2的值小
        return values[index1].compareTo(index2) < 0;
    }

    /**
     * 比较两节点大小
     *
     * @param index1
     * @param index2
     * @return
     */
    private boolean large(int index1, int index2) {
        // 返回index1的值是否比index2的值小
        return values[index1].compareTo(index2) > 0;
    }

}

class PriorityQueue<T extends Comparable> {
    private BinaryHeap<T> binaryHeap;

    public PriorityQueue(int capacity) {
        this.binaryHeap = new BinaryHeap(capacity);
    }

    public void push(T t) {
        this.binaryHeap.insert(t);
    }

    public T pop() {
        return this.binaryHeap.pop();
    }

}