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

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

系统提供的堆无法做到的事情：
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> {@Overridepublic 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> {@Overridepublic 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,  buyOrRefundpublic 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("测试结束");}}