8.3：加强堆的应用

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 topK (int[] arr, boolean[] op, int k)

// 暴力解法思路：
// 1：根据题目要求我们可以得出，用户对象Customer有属性buy（购买数量），enterTime（进入时间），id（独自的ID）这三个属       性，与此同时我们还分析出有得奖区和等候区两个区域，即两个容器。返回的结果是List>类型，即一个链表，       链表中存储的一个存储类型是Integer类型的一个链表，记录每一次的TOPK的顾客的ID。
// 2：根据题意我们知到：当没有这个人时，这个人还退货，那么直接跳过，进行下一次的操作。这里出现了一个问题，我们如何知到       有没有这个人，因为传进来的参数只有(ID, buyOrReund, k),难道我们要遍历那两个容器吗，时间复杂度太高，所以我们需要	   根据ID查找有没有这个人。所以我们可以写一个hashmap,这样可以快速的查找又没有这个人，并且可       以快速的拿到这个人，需要注意是，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中一般的堆，你只能存与取，非常的单一。不可以对堆中的元素进行修改，一修改就废了。因为他没法自己调整成正确       的堆。但是加强堆不同，她可以对堆中的元素进行修改，它可以自己调整成正确的堆。
1
2
3
4
5
6
7
8
9
10
11
12

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

暴力解法

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);
                    // 只会执行其中一个
                    // N
                    cleanZeroBuy(cands);
                    cleanZeroBuy(daddy);
                }
            }
            // 调整
            // NlogN
            cands.sort(new CandsComparator());
            daddy.sort(new DaddyComparator());
            // 是否要交换位置
            move(k, i);
            // 生成topK
            // K
            ans.add(getCurAns());
        }
        return ans;
    }

    // 将中奖区的topK放到 List 中
    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> {
        @Override
        public 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> {
        @Override
        public int compare(Customer o1, Customer o2) {
            return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

大根堆解法：

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> {
        @Override
        public 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> {
        @Override
        public 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);
        // 生成topK
        ans.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 中
    public List<Integer> getCurAns() {
        List<Customer> c =  daddy.getAllElements();
        List<Integer> list = new ArrayList<>();
        for (Customer cus : c) {
            list.add(cus.id);
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

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);
    }

    // logN
    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    // logN
    public 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;
        }
    }

    // logN
    public T pop() {
        T ans = heap.get(0);
        swap(0, --heapSize);
        indexMap.remove(ans);
        // 注意：其实Arraylist里面已经有一个heapsize这样的尾指针，这里我们自己定义的heapsize只是为了方便我们找到尾节点下标。
        // 真正意义上删除一个节点还是需要Arraylist里面的尾指针进行操作的。
        heap.remove(heapSize); // 真正的将尾节点删除。
        heapFiy(0);
        return ans;
    }

    // logN
    public 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;
            }
        }
    }

    // logN
    public void remove(T obj) {
        // 得到节点的位置index
        int index = indexMap.get(obj);
        // 得到末尾的数 value
        T 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);
        }
    }

    // 重构造
    // 只会执行其中的一个，logN
    public 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);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128