8.3：加强堆的应用

题目要求：

做一个加强堆的题目，给定一个整型数组，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数组，遍历每一步输出一个得奖名单
public List<List> topK (int[] arr, boolean[] op, int k)

// 暴力解法思路：
// 1：根据题目要求我们可以得出，用户对象Customer有属性buy（购买数量），enterTime（进入时间），id（独自的ID）这三个属       性，与此同时我们还分析出有得奖区和等候区两个区域，即两个容器。返回的结果是List<List<Integer>>类型，即一个链表，       链表中存储的一个存储类型是Integer类型的一个链表，记录每一次的TOPK的顾客的ID。
// 2：根据题意我们知到：当没有这个人时，这个人还退货，那么直接跳过，进行下一次的操作。这里出现了一个问题，我们如何知到       有没有这个人，因为传进来的参数只有(ID, buyOrReund, k),难道我们要遍历那两个容器吗，时间复杂度太高，所以我们需要	   根据ID查找有没有这个人。所以我们可以写一个hashmap<Integer , Customer>,这样可以快速的查找又没有这个人，并且可       以快速的拿到这个人，需要注意是，hashmap中村的顾客是两个容器中所有buy！= 0的人。
// 3：2已经分析了一种情况：当没有这个人时，这个人还退货，还剩三种情况，(1)：当没有这个人时，这个人还买货。(2)：有这个       人时,这个人还买货。(3)：有这个人时，这个人还退货。
// 4：(1): 创建这个顾客，Customer c = new Customer(id, i, 1);其进入的时间是现在的时间。因为一次只能买一个，所以buy       == 1,Hashmap中存一下，之后这个顾客放到那个容器中呢？如果终中奖区没满，就将其进中奖区。如果中奖区满了就将其放进       等待区，放完之后我们再调整两个区域，调正的准则是：中奖区最差的放在头，等候区最好的放在头。之后必将两个头，如果等	  候区的头的buy大于中奖区头的buy就交换。
//    (2)：如果有这个人这个人还买货，或者是有这个人时，这个人还退货。我们可以通过hashmap根据这个人的ID迅速的得到这个       Customer，对其buy进行调整，c.buy++ or c.buy--,如果调整完以后他的buy == 0,那么就将这个对象删除。hashmap中删除       与此同时容器中的这个对象也要删除。由于不知到这个对象在那个容器中，所以两个容器都要删除一遍cleanZeroBuy(cands);       cleanZeroBuy(daddy);删完之后，或者是说buy调整完之后，两个容器需要调整。中奖区最差的放在头，等候区最好的放在         头。之后必将两个头，如果等候区的头的buy大于中奖区头的buy就交换。
//    最后生成TOPOK。// 大根堆解法思路：
// 1：暴力解法中，使用的容器是Arraylist类型，其进行排序调整的时间复杂度是:NlogN，删除的时间复杂度是N,由于一共有N个数       据所以总的时间复杂度是: N^2logN.
// 2: 容器我们可以使用加强堆，这样调整的时间复杂度是logN,删除的时间复杂度也是logN,而且堆的调整我们可以自己写比较器，按       照自己的要求调整堆。总的时间复杂度降到NlogN
// 3：注意java中一般的堆，你只能存与取，非常的单一。不可以对堆中的元素进行修改，一修改就废了。因为他没法自己调整成正确       的堆。但是加强堆不同，她可以对堆中的元素进行修改，它可以自己调整成正确的堆。

// 大根堆的好处：可以对堆中的元素进行修改，它可以自己调整成正确的堆，并且调整的时间复杂度是logN级别的非常的高效，与此同    时能传入比较器，按照自己想要的规则进行tiao'zheng。

暴力解法

package algorithmbasic.class8;import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;public class EveryStepShowBoss2 {// 顾客内部类public static class Customer {public int id;public int enterTime;public int buy;public Customer(int id, int enterTime, int buy) {this.id = id;this.enterTime = enterTime;this.buy = buy;}}// 属性// 存储返回值List<List<Integer>> ans = new ArrayList<>();// 得奖区ArrayList<Customer> daddy = new ArrayList<>();// 等候区ArrayList<Customer> cands = new ArrayList<>();// 查找是否有这个顾客 --> (根据id找customer)HashMap<Integer, Customer> map = new HashMap<>();// 方法public List<List<Integer>> topK2(int[] arr, boolean[] op, int k) {for (int i = 0; i < arr.length; i++) {int id = arr[i];boolean buyOrRefund = op[i];// 没有这个顾客并且退货if (!map.containsKey(id) && !buyOrRefund) {ans.add(this.getCurAns());continue;}// 没有这个顾客 -> 买// 有这个顾客 -> 退// 有这个顾客 -> 买// 这个是：没有这个顾客 -> 买if (!map.containsKey(id)) {Customer c = new Customer(id, i, 1);map.put(id, c);// cands / daddy 中加if (daddy.size() < k) {daddy.add(c);} else {cands.add(c);}// 后面会涉及一个调整} else { // 有这个顾客 -> 退  有这个顾客 -> 买Customer c = map.get(id);if (buyOrRefund) {c.buy++;} else {c.buy--;}if (c.buy == 0) {map.remove(id);// 只会执行其中一个// NcleanZeroBuy(cands);cleanZeroBuy(daddy);}}// 调整// NlogNcands.sort(new CandsComparator());daddy.sort(new DaddyComparator());// 是否要交换位置move(k, i);// 生成topK// Kans.add(getCurAns());}return ans;}// 将中奖区的topK放到 List<Integer> 中public List<Integer> getCurAns() {List<Integer> list = new ArrayList<>();for (Customer c : this.daddy) {list.add(c.id);}return list;}// 删除daddy/cands中购买数为0的顾客public 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 void move(int k, int time) {if (cands.isEmpty()) {return;}if (daddy.size() < k) {Customer c = cands.get(0);c.enterTime = time;cands.remove(0);daddy.add(c);} else if (cands.get(0).buy > daddy.get(0).buy) {Customer c1 = cands.get(0);c1.enterTime = time;Customer c2 = daddy.get(0);c2.enterTime = time;cands.remove(0);daddy.remove(0);daddy.add(c1);cands.add(c2);}}// 比较器// 中奖区的比较器  ->  最烂的在前面public class DaddyComparator implements Comparator<Customer> {@Overridepublic int compare(Customer o1, Customer o2) {return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);}}// 等待区的比较器  ->  最好的在前面public class CandsComparator implements Comparator<Customer> {@Overridepublic int compare(Customer o1, Customer o2) {return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);}}
}

大根堆解法：

package algorithmbasic.class8;import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;// 用加强堆实现
public class EveryStepShowBoss3 {// 顾客内部类public static class Customer {public int id;public int enterTime;public int buy;public Customer(int id, int enterTime, int buy) {this.id = id;this.enterTime = enterTime;this.buy = buy;}}// 比较器// 中奖区的比较器  ->  最烂的在前面public class DaddyComparator implements Comparator<Customer> {@Overridepublic int compare(Customer o1, Customer o2) {return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);}}// 等待区的比较器  ->  最好的在前面public class CandsComparator implements Comparator<Customer> {@Overridepublic int compare(Customer o1, Customer o2) {return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);}}// 属性// 查找是否有这个顾客 --> (根据id找customer)HashMap<Integer, Customer> map;// 得奖区HeapGreater<Customer> daddy;// 等候区HeapGreater<Customer> cands;// 中奖区最多容纳人数final int daddyLimit;// 构造器public EveryStepShowBoss3(int daddyLimit) {this.daddyLimit = daddyLimit;map = new HashMap<>();daddy = new HeapGreater<>(new DaddyComparator());cands = new HeapGreater<>(new CandsComparator());}// 方法public List<List<Integer>> topK(int[] arr, boolean[] op, int k) {// 返回的结果存放区List<List<Integer>> ans = new ArrayList<>();EveryStepShowBoss3 everyStepShowBoss3 = new EveryStepShowBoss3(k);for (int i = 0; i < arr.length; i++) {operate(i, arr[i] , op[i] , ans);}return ans;}public void operate(int time, int id, boolean buyOrRefund , List<List<Integer>> ans) {// 没有这个顾客并且退货if(!map.containsKey(id) && !buyOrRefund) {ans.add(this.getCurAns());return;}// 没有这个顾客 -> 买// 有这个顾客 -> 退// 有这个顾客 -> 买if(!map.containsKey(id)) {Customer c = new Customer(id, time, 1);map.put(id, c);if(daddy.size() < daddyLimit) {// 会自动调整daddy.push(c);}else {cands.push(c);}}else {Customer c = map.get(id);if(buyOrRefund) {c.buy++;}else {c.buy--;}if(cands.contains(c)) {if(c.buy == 0) {cands.remove(c);map.remove(id);}else {// 调整一下cands.resign(c);}}else {if(c.buy == 0) {daddy.remove(c);map.remove(id);}else {// 调整一下daddy.resign(c);}}}// 是否要交换位置move(time);// 生成topKans.add(this.getCurAns());}public void move(int time) {if(cands.isEmpty()) {return;}if(daddy.size() < daddyLimit) {Customer c = cands.pop();c.enterTime = time;daddy.push(c);}else {if(cands.peek().buy > daddy.peek().buy) {Customer c1 = cands.pop();c1.enterTime = time;Customer c2 = daddy.pop();c2.enterTime = time;cands.push(c2);daddy.push(c1);}}}// 将中奖区的topK放到 List<Integer> 中public List<Integer> getCurAns() {List<Customer> c =  daddy.getAllElements();List<Integer> list = new ArrayList<>();for (Customer cus : c) {list.add(cus.id);}return list;}
}

Heapgreater

package algorithmbasic.class8;import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;// 加强堆
public class HeapGreater<T> {private ArrayList<T> heap;private int heapSize;private HashMap<T, Integer> indexMap;private Comparator<? super T> comp;public HeapGreater(Comparator<? super T> comp) {this.heap = new ArrayList<>();indexMap = new HashMap<>();this.heapSize = 0;this.comp = comp;}public boolean isEmpty() {return this.heapSize == 0;}public int size() {return this.heapSize;}public boolean contains(T obj) {return this.indexMap.containsKey(obj);}public T peek() {return this.heap.get(0);}// logNpublic void push(T obj) {heap.add(obj);indexMap.put(obj, heapSize);heapInsert(heapSize++);}// logNpublic void heapInsert(int index) {int father = (index - 1) / 2;while (this.comp.compare(heap.get(index), heap.get(father)) < 0) {// 注意交换的时候，ArrayList中的K V需要交换，HashMap中的K V也需要交换。swap(father, index);index = father;father = (index - 1) / 2;}}// logNpublic T pop() {T ans = heap.get(0);swap(0, --heapSize);indexMap.remove(ans);// 注意：其实Arraylist里面已经有一个heapsize这样的尾指针，这里我们自己定义的heapsize只是为了方便我们找到尾节点下标。// 真正意义上删除一个节点还是需要Arraylist里面的尾指针进行操作的。heap.remove(heapSize); // 真正的将尾节点删除。heapFiy(0);return ans;}// logNpublic void heapFiy(int index) {int l = index * 2 + 1;while (l < heapSize) {int minSonIndex = l + 1 < heapSize ? (this.comp.compare(heap.get(l), heap.get(l + 1)) < 0 ? l : l + 1) : (l);if(this.comp.compare(heap.get(minSonIndex), heap.get(index)) < 0) {swap(minSonIndex, index);index = minSonIndex;l = index * 2 + 1;}else {break;}}}// logNpublic void remove(T obj) {// 得到节点的位置indexint index = indexMap.get(obj);// 得到末尾的数 valueT replace = heap.get(--heapSize);// 将hashmap中obj值以及heap中末尾的数直接删掉indexMap.remove(obj);// 真正的删除尾节点。heap.remove(heapSize);// 如果末尾节点值与obj是同一个,不需要一下操作if (obj != replace) {// 将结果塞回去heap.set(index, replace);indexMap.put(replace, index);resign(replace);}}// 重构造// 只会执行其中的一个，logNpublic void resign(T obj) {heapInsert(indexMap.get(obj));heapFiy(indexMap.get(obj));}// 请返回堆上的所有元素public List<T> getAllElements() {List<T> ans = new ArrayList<>();for (T c : heap) {ans.add(c);}return ans;}public void swap(int i, int j) {T value1 = heap.get(i);T value2 = heap.get(j);heap.set(i, value2);heap.set(j, value1);// HashMap新的值覆盖旧的值indexMap.put(value1, j);indexMap.put(value2, i);}
}