【算法&数据结构体系篇class07】：加强堆

桃扇骨 2024-03-26 10:55 29阅读 0赞

### 一、手动改写堆（非常重要）！ ###

> 系统提供的堆无法做到的事情：  
> 1）已经入堆的元素，如果参与排序的指标方法变化，  
> 系统提供的堆无法做到时间复杂度O(logN)调整！都是O(N)的调整！  
> 2）系统提供的堆只能弹出堆顶，做不到自由删除任何一个堆中的元素，  
> 或者说，无法在时间复杂度O(logN)内完成！一定会高于O(logN)  
> 根本原因：**无反向索引表**

### 二、加强堆的核心点 ###

1）建立反向索引表indexMap

2）建立比较器

3）核心在于各种结构相互配合，非常容易出错

### 三、构建加强堆演示 ###

package class07;
    
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    
    /**
     * 手写一个加强堆，比系统自带的优先队列多了更多高效的获取元素查询动作
     * 注意泛型：T一定要是非基础类型，有基础类型需求包一层
     */
    public class HeapGreaterTrain<T> {
        //保存堆元素的集合
        public ArrayList<T> heap;
        //保存堆元素对应的索引位置 元素：索引
        public HashMap<T, Integer> indexMap;
        //堆大小
        public int heapSize;
        //比较器，自定义的比较器 ?匹配类型是T的父类 包括T本身
        public Comparator<? super T> comp;
    
        public HeapGreaterTrain(Comparator<? super T> c) {
            heap = new ArrayList<>();
            indexMap = new HashMap<T, Integer>();
            heapSize = 0;
            comp = c;
        }
    
        //判断堆是否为空
        public boolean isEmpty() {
            return heapSize == 0;
        }
    
        //判断堆大小
        public int size() {
            return heapSize;
        }
    
        //判断堆中是否包含某个元素
        public boolean contains(T obj) {
            return indexMap.containsKey(obj);
        }
    
        //查询堆顶元素
        public T peek() {
            return heap.get(0);
        }
    
        //入堆操作
        public void push(T obj) {
            //直接进集合最后，反向索引表创建关系，后面再接着insert向上排序
            heap.add(obj);
            indexMap.put(obj, heapSize);
            heapInsert(heapSize++);
        }
    
        //堆向上交换操作，默认是小根堆的排序
        private void heapInsert(int i) {
            //通过业务创建加强堆自定义的比较器来定义排序，假设返回小于0，执行交换操作
            while (comp.compare(heap.get(i), heap.get((i - 1) / 2)) < 0) {
                swap(i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }
    
        //出堆操作
        public T pop(){
            //出堆顶，然后与最后一个元素交换，再将最后一个元素从集合与反向索引表删除
            T ans = heap.get(0);
            swap(0,--heapSize);
            heap.remove(heapSize);
            indexMap.remove(ans);
            heapify(0);
            return ans;
        }
    
        //堆向下沉操作 默认小根堆
        public void heapify(int i) {
            int left = i *2 +1;
            while(left < heapSize){
                int smallest = left+1 < heapSize && comp.compare(heap.get(left+1),heap.get(left))<0?left+1:left;
                smallest = comp.compare(heap.get(smallest),heap.get(i))<0?smallest:i;
                if(smallest == i) break;
                swap(smallest,i);
                i = smallest;
                left = i *2+1;
            }
        }
    
        //移除任意一个元素  将最后一个元素交换到该元素位置，然后再从该位置进行堆的上下调整排序操作
        public void remove(T obj){
            //获取集合中最后一个元素
            T end = heap.get(heapSize-1);
            //获取要删除元素的索引
            int index = indexMap.get(obj);
            //分别删除索引表该元素记录，与集合中最后一个元素，该元素前面已经保存下来
            indexMap.remove(obj);
            heap.remove(--heapSize);
            //注意：如果删除元素不是最后一个元素，再将该元素添加到index位置，并增加反向索引表记录
            if(obj != end){
                heap.set(index,end);
                indexMap.put(end,index);
                //调整完，就需要判断该元素是否需要上移或下移,其中只会执行一句
                resign(end);
            }
    
        }
    
        public void resign(T end) {
            heapInsert(indexMap.get(end));
            heapify(indexMap.get(end));
        }
    
        //返回堆上所有元素
        public List<T> getAllElements(){
            return heap;
        }
        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);
        }
    }

### 四、加强堆应用：用户颁奖问题 ###

> 给定一个整型数组，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，如果购买数不足以进入得奖区的用户，进入候选区  
> 7，如果候选区购买数最多的用户，已经足以进入得奖区，  
> 该用户就会替换得奖区中购买数最少的用户（大于才能替换），  
> 如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户  
> 如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户  
> 8，候选区和得奖区是两套时间，  
> 因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有  
> 从得奖区出来进入候选区的用户，得奖区时间删除，  
> 进入候选区的时间就是当前事件的时间（可以理解为arr\[i\]和op\[i\]中的i）  
> 从候选区出来进入得奖区的用户，候选区时间删除，  
> 进入得奖区的时间就是当前事件的时间（可以理解为arr\[i\]和op\[i\]中的i）  
> 9，如果某用户购买数==0，不管在哪个区域都离开，区域时间删除，  
> 离开是指彻底离开，哪个区域也不会找到该用户  
> 如果下次该用户又发生购买行为，产生>0的购买数，  
> 会再次根据之前规则回到某个区域中，进入区域的时间重记  
> 请遍历arr数组和op数组，遍历每一步输出一个得奖名单  
> publicList<List<Integer>> topK(int\[\] arr, boolean\[\] op, int k)

package class07;
    
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    
    public class Code02_EveryStepShowBoss {
    
        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 HeapGreaterTrain<Customer> candHeap;
            private HeapGreaterTrain<Customer> daddyHeap;
            private final int daddyLimit;
    
            public WhosYourDaddy(int limit) {
                customers = new HashMap<Integer, Customer>();
                candHeap = new HeapGreaterTrain<>(new CandidateComparator());
                daddyHeap = new HeapGreaterTrain<>(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;
        }
    
        // 干完所有的事，模拟，不优化
        public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
            HashMap<Integer, Customer> map = new HashMap<>();
            ArrayList<Customer> cands = new ArrayList<>();
            ArrayList<Customer> daddy = new ArrayList<>();
            List<List<Integer>> ans = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                int id = arr[i];
                boolean buyOrRefund = op[i];
                if (!buyOrRefund && !map.containsKey(id)) {
                    ans.add(getCurAns(daddy));
                    continue;
                }
                // 没有发生：用户购买数为0并且又退货了
                // 用户之前购买数是0，此时买货事件
                // 用户之前购买数>0， 此时买货
                // 用户之前购买数>0, 此时退货
                if (!map.containsKey(id)) {
                    map.put(id, new Customer(id, 0, 0));
                }
                // 买、卖
                Customer c = map.get(id);
                if (buyOrRefund) {
                    c.buy++;
                } else {
                    c.buy--;
                }
                if (c.buy == 0) {
                    map.remove(id);
                }
                // c
                // 下面做
                if (!cands.contains(c) && !daddy.contains(c)) {
                    if (daddy.size() < k) {
                        c.enterTime = i;
                        daddy.add(c);
                    } else {
                        c.enterTime = i;
                        cands.add(c);
                    }
                }
                cleanZeroBuy(cands);
                cleanZeroBuy(daddy);
                cands.sort(new CandidateComparator());
                daddy.sort(new DaddyComparator());
                move(cands, daddy, k, i);
                ans.add(getCurAns(daddy));
            }
            return ans;
        }
    
        public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
            if (cands.isEmpty()) {
                return;
            }
            // 候选区不为空
            if (daddy.size() < k) {
                Customer c = cands.get(0);
                c.enterTime = time;
                daddy.add(c);
                cands.remove(0);
            } else { // 等奖区满了，候选区有东西
                if (cands.get(0).buy > daddy.get(0).buy) {
                    Customer oldDaddy = daddy.get(0);
                    daddy.remove(0);
                    Customer newDaddy = cands.get(0);
                    cands.remove(0);
                    newDaddy.enterTime = time;
                    oldDaddy.enterTime = time;
                    daddy.add(newDaddy);
                    cands.add(oldDaddy);
                }
            }
        }
    
        public static void cleanZeroBuy(ArrayList<Customer> arr) {
            List<Customer> noZero = new ArrayList<Customer>();
            for (Customer c : arr) {
                if (c.buy != 0) {
                    noZero.add(c);
                }
            }
            arr.clear();
            for (Customer c : noZero) {
                arr.add(c);
            }
        }
    
        public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
            List<Integer> ans = new ArrayList<>();
            for (Customer c : daddy) {
                ans.add(c.id);
            }
            return ans;
        }
    
        // 为了测试
        public static class Data {
            public int[] arr;
            public boolean[] op;
    
            public Data(int[] a, boolean[] o) {
                arr = a;
                op = o;
            }
        }
    
        // 为了测试
        public static Data randomData(int maxValue, int maxLen) {
            int len = (int) (Math.random() * maxLen) + 1;
            int[] arr = new int[len];
            boolean[] op = new boolean[len];
            for (int i = 0; i < len; i++) {
                arr[i] = (int) (Math.random() * maxValue);
                op[i] = Math.random() < 0.5 ? true : false;
            }
            return new Data(arr, op);
        }
    
        // 为了测试
        public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
            if (ans1.size() != ans2.size()) {
                return false;
            }
            for (int i = 0; i < ans1.size(); i++) {
                List<Integer> cur1 = ans1.get(i);
                List<Integer> cur2 = ans2.get(i);
                if (cur1.size() != cur2.size()) {
                    return false;
                }
                cur1.sort((a, b) -> a - b);
                cur2.sort((a, b) -> a - b);
                for (int j = 0; j < cur1.size(); j++) {
                    if (!cur1.get(j).equals(cur2.get(j))) {
                        return false;
                    }
                }
            }
            return true;
        }
    
        public static void main(String[] args) {
            int maxValue = 10;
            int maxLen = 100;
            int maxK = 6;
            int testTimes = 100000;
            System.out.println("测试开始");
            for (int i = 0; i < testTimes; i++) {
                Data testData = randomData(maxValue, maxLen);
                int k = (int) (Math.random() * maxK) + 1;
                int[] arr = testData.arr;
                boolean[] op = testData.op;
                List<List<Integer>> ans1 = topK(arr, op, k);
                List<List<Integer>> ans2 = compare(arr, op, k);
                if (!sameAnswer(ans1, ans2)) {
                    for (int j = 0; j < arr.length; j++) {
                        System.out.println(arr[j] + " , " + op[j]);
                    }
                    System.out.println(k);
                    System.out.println(ans1);
                    System.out.println(ans2);
                    System.out.println("出错了！");
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    }