07 加强堆

第7节.pptx
老师分享的一点code经验：代码指令10^8~10^9之间，java程序用时约2~4秒。因此可以根据题目时间限制和数据规模，逆向推断算法合格时间复杂度标准。（比如在2~4秒完成排序，数组组大长度不超过10^5，那么排序算法时间复杂度必须低于O(N^2），由此可以判断算法是否合格）；此经验可以用于网站刷题（牛客网）。

1 加强堆

public class HeapGreater<T> {
    /**
     * 用户传入的比较器
     */
    private final Comparator<? super T> comparator;
    /**
     * 底层用ArrayList动态数组
     */
    private ArrayList<T> heap;
    /**
     * 反向序列表
     */
    private HashMap<T, Integer> indexMap;
    /**
     * 堆大小
     */
    private int heapSize;
    /**
     * 构造器
     *
     * @param comparator 用户实现的比较器
     */
    public HeapGreater(Comparator<? super T> comparator) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        this.comparator = comparator;
    }
    /**
     * 堆是否为空
     *
     * @return 为空返回true,不为空返回false
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }
    /**
     * 堆大小
     * @return heapSize
     */
    public int size() {
        return heapSize;
    }
    /**
     * 堆是否包含某个元素
     * @param obj 元素
     * @return 包含返回true,不包含返回false
     */
    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }
    /**
     * 查看堆顶元素
     * @return 堆顶元素
     */
    public T peek() {
        return heap.get(0);
    }
    /**
     * 添加元素
     * @param obj 元素
     */
    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }
    /**
     * 向上调整堆结构
     * @param index 当前元素下标
     */
    private void heapInsert(int index) {
        while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    /**
     * 取出堆顶元素
     * @return 堆顶元素
     */
    public T pop() {
        T ans = heap.get(0);
        heap.set(0, heap.get(heapSize - 1));
        indexMap.remove(ans);
        indexMap.put(heap.get(0), 0);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }
    /**
     * 删除某个元素
     * @param obj 元素
     */
    public void remove(T obj) {
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if (replace != obj) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(replace);
        }
    }
    /**
     * 从某个元素开始调整堆结构
     * @param obj 元素
     */
    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }
    /**
     * 返回所有堆元素
     * @return 封装堆元素的List集合
     */
    public List<T> getAllElements() {
        return new ArrayList<>(heap);
    }
    /**
     * 向下调整堆结构
     * @param index 当前元素下标
     */
    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int right = left + 1;
            int best = right < heapSize && (comparator.compare(heap.get(right), heap.get(left)) < 0) ? right : left;
            best = (comparator.compare(heap.get(best), heap.get(index)) < 0) ? best : index;
            if (best == index) {
                break;
            }
            swap(best, index);
            index = best;
            left = index * 2 + 1;
        }
    }
    /**
     * 交换堆元素
     * @param i 下标i
     * @param j 下标j
     */
    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);    
        heap.set(j, o1);
        indexMap.put(o1, j);
        indexMap.put(o2, i);
    }
}

2 加强堆应用题目

给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op；两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作。arr = [ 3 , 3 , 1 , 2, 1, 2, 5…]、op= [ T , T, T, T, F, T, F…]
依次表示：3用户购买了一件商品，3用户购买了一件商品，1用户购买了一件商品，2用户购买了一件商品，1用户退货了一件商品，2用户购买了一件商品，5用户退货了一件商品…
一对arr[i]和op[i]就代表一个事件：用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品、op[i] == F就代表这个用户退货了一件商品；现在你作为电商平台负责人，你想在每一个事件到来的时候，都给购买次数最多的前K名用户颁奖。所以每个事件发生后，你都需要一个得奖名单（得奖区）。得奖系统的规则：
1，如果某个用户购买商品数为0，但是又发生了退货事件，则认为该事件无效，得奖名单和上一个事件发生后一致，例中的5用户
2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
3，每次都是最多K个用户得奖，K也为传入的参数，如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
4，得奖系统分为得奖区和候选区，任何用户只要购买数>0，一定在这两个区域中的一个
5，购买数最大的前K名用户进入得奖区，在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区
6，如果购买数不足以进入得奖区的用户，进入候选区

public static class Customer {
        public int id;
        public int buy;
        public int enterTime;

        public Customer(int v, int b, int o) {
            id = v;
            buy = b;
            enterTime = 0;
        }
    }

    public static class CandidateComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
        }

    }

    public static class DaddyComparator implements Comparator<Customer> {

        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
        }

    }

    public static class WhosYourDaddy {
        private HashMap<Integer, Customer> customers;
        private HeapGreater<Customer> candHeap;
        private HeapGreater<Customer> daddyHeap;
        private final int daddyLimit;

        public WhosYourDaddy(int limit) {
            customers = new HashMap<Integer, Customer>();
            candHeap = new HeapGreater<>(new CandidateComparator());
            daddyHeap = new HeapGreater<>(new DaddyComparator());
            daddyLimit = limit;
        }

        // 当前处理i号事件，arr[i] -> id,  buyOrRefund
        public void operate(int time, int id, boolean buyOrRefund) {
            if (!buyOrRefund && !customers.containsKey(id)) {
                return;
            }
            if (!customers.containsKey(id)) {
                customers.put(id, new Customer(id, 0, 0));
            }
            Customer c = customers.get(id);
            if (buyOrRefund) {
                c.buy++;
            } else {
                c.buy--;
            }
            if (c.buy == 0) {
                customers.remove(id);
            }
            if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
                if (daddyHeap.size() < daddyLimit) {
                    c.enterTime = time;
                    daddyHeap.push(c);
                } else {
                    c.enterTime = time;
                    candHeap.push(c);
                }
            } else if (candHeap.contains(c)) {
                if (c.buy == 0) {
                    candHeap.remove(c);
                } else {
                    candHeap.resign(c);
                }
            } else {
                if (c.buy == 0) {
                    daddyHeap.remove(c);
                } else {
                    daddyHeap.resign(c);
                }
            }
            daddyMove(time);
        }

        public List<Integer> getDaddies() {
            List<Customer> customers = daddyHeap.getAllElements();
            List<Integer> ans = new ArrayList<>();
            for (Customer c : customers) {
                ans.add(c.id);
            }
            return ans;
        }

        private void daddyMove(int time) {
            if (candHeap.isEmpty()) {
                return;
            }
            if (daddyHeap.size() < daddyLimit) {
                Customer p = candHeap.pop();
                p.enterTime = time;
                daddyHeap.push(p);
            } else {
                if (candHeap.peek().buy > daddyHeap.peek().buy) {
                    Customer oldDaddy = daddyHeap.pop();
                    Customer newDaddy = candHeap.pop();
                    oldDaddy.enterTime = time;
                    newDaddy.enterTime = time;
                    daddyHeap.push(newDaddy);
                    candHeap.push(oldDaddy);
                }
            }
        }

    }

    public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        WhosYourDaddy whoDaddies = new WhosYourDaddy(k);
        for (int i = 0; i < arr.length; i++) {
            whoDaddies.operate(i, arr[i], op[i]);
            ans.add(whoDaddies.getDaddies());
        }
        return ans;
    }