【堆 - 专题】“加强堆” 解决 TopK 问题！

站长

2024年03月13日 08:43 · 阅读数 7

前两篇文章我们介绍了有关 堆排序、大小根堆 以及 手写加强堆 的相关知识，（还没看过上篇文章的赶快点我查看哦！）

本篇文章我们使用 加强堆 完成一道较有难度的 TopK 问题！

给购买数前 K 名颁奖

假设现在商场中顾客会进行购买或退货两种操作，每次操作只能购买或退货一件商品。给定两个等长的整形数组 arr 和布尔型数组 op ，arr[i] 表示顾客的编号，op[i] 表示顾客的操作，T 代表该顾客购买了一件商品，F 代表该顾客退了一件商品。例如：

arr = [3, 3, 1, 2, 1, 2, 5...]

op = [T, T, T, T, F, T, F...]

表示 :

3 用户购买一件商品，3 用户购买一件商品，

1 用户购买一件商品，2 用户购买一件商品，

1 用户退货一件商品，2 用户购买一件商品，

5 用户退货一件商品...

要求

现在你作为电商平台负责人，想在每一个事件到来的时候（某个用户购买或者退货的时候），都给购买次数最多的前 K 名用户颁奖。所以 每个事件发生后 ，你都需要得到 得奖名单 。

规则:

若用户购买商品数为 0，但发生了退货事件，则认为该事件无效，得奖名单保持不变；
若用户发生购买事件，商品数 +1，发生退货事件，商品数 -1；
得奖系统分为得奖区和候选区，任何用户只要购买数 >0，一定会在两个区域中的一个；
购买数最大的前 K (传入参数) 名用户进入得奖区，在最初时如果得奖区没有到达 K 个用户，那么新来的用户直接进入得奖区；
购买数不足以进入得奖区的用户，进入候选区；
如果候选区购买数最多的用户，已经足以进入得奖区了，该用户就会替换得奖区中购买数最少的用户( 大于才能替换)；如果得奖区中购买数最少的用户有多个，就替换 最早进入 得奖区的用户；如果候选区中购买数最多的用户有多个，机会会给 最早进入 候选区的用户；
候选区和得奖区是 两套时间，因用户只会在其中一个区域，所以只会有一个区域的时间；从 得奖区出来 进入候选区的用户，得奖区时间删除，进入候选区的时间就是当前事件的时间 ( arr[i] 和 op[i] 中的 i )；从 候选区出来 进入得奖区的用户，候选区时间删除，进入得奖区的时间就是当前事件的时间 ( arr[i] 和 op[i] 中的 i )；
若用户购买数为 0，删除该用户。如果下次该用户又发生购买行为，产生 >0 的购买数，会再次根据之前规则回到某个区域中，进入区域的时间重记。

题目规则有些多，慢慢理解清楚！（其实就是最生活化的排名问题哦~）

首先分析结构体的定义：每个顾客有一个用于区分身份的 id 、购买商品数量的 buy ，根据题目描述，每个顾客仅有一个进入 得奖区 或 候选区 的时间 enterTime 。

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

    public Customer(int id, int buy, int enterTime) {
        this.id = id;
        this.buy = buy;
        this.enterTime = 0;
    }
}

接下来我们定义比较器，思考两个候选区中顾客的比较方式：

候选区：在候选区的顾客若购买商品数量足以达到进入得奖区的要求（超过了得奖区的最后一名），则弹出候选区，进入得奖区。因此，候选区应构建一个大根堆，每次堆顶弹出的是购买数量最多的顾客。

得奖区：若候选区有顾客来了，则弹出候选区，进入得奖区。因此，得奖区应构建一个小根堆，让得奖区中购买数最小的被替换出去。

当 购买数相同 时，两个区域均 弹出时间小 的顾客：在候选区的顾客时间越小说明等的时间较长应该先让其弹出，进入得奖区；在得奖区的顾客时间越小说明在 TopK 区待的时间长了，那就可以让其弹出把位置让给别人。

注意：这里的堆为加强堆（上篇文章里介绍的哦）。

public static class CandidateComparator implements Comparator<Customer> {
    @Override
    public int compare(Customer o1, Customer o2) {
        // 大根堆，这样才能从 候选堆里 选出买的最多的进入 TopK
        // 购买数一样，先让 时间小 的进入(等待的时间长)
        return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
    }

}

public static class TopComparator implements Comparator<Customer> {
    @Override
    public int compare(Customer o1, Customer o2) {
        // 小根堆，这样才能弹出（淘汰）购买数最小的
        // 购买数一样，先让 时间小 的出去(在TopK中待的时间已经很长了，就走吧)
        return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
    }
}

接下来分析函数主要功能部分。

使用 哈希表 实现查找用户 id 与购买商品数量的索引表功能。

当某个顾客到来后 (即事件发生时)，我们按照规则分析情况：

若顾客购买商品数为 0，但发生了退货行为，忽略。
若顾客不在索引表中，且当前产生了购买行为。新顾客 —— 加入哈希表中，若得奖区没满加入得奖区，否则进入候选区。
若顾客在索引表中，且当前产生了购买行为。老顾客 —— 更新哈希表，更新所在的区域（得奖区 or 等待区）。
若顾客在索引表中，且当前产生了退货行为。老顾客 —— 更新哈希表。若购买数为 0 ，在所属区域中删除该顾客。不为 0 ，更新所在的区域（得奖区 or 等待区）。
每个顾客的行为判断结束后，检查两个区域的堆顶元素，若待定区域的堆顶大于得奖区的堆顶购买数量，更新两个堆中排序。

public static class topK {
    // 反向索引表
    private HashMap<Integer, Customer> customers;
    // 候选堆
    private HeapGreater<Customer> candHeap;
    // TopK 堆
    private HeapGreater<Customer> topHeap;
    private final int K;

    public topK(int k) {
        customers = new HashMap<Integer, Customer>();
        candHeap = new HeapGreater<>(new CandidateComparator());
        topHeap = new HeapGreater<>(new TopComparator());
        K = k;
    }

    // 处理 i 号事件
    public void operate(int time, int id, boolean buyOrRefund) {
        // 未买就退
        if (!buyOrRefund && !customers.containsKey(id)) {
            return;
        }
        // 买了，但没 id ，说明这是个新人，new 一个
        if (!customers.containsKey(id)) {
            customers.put(id, new Customer(id, 0, 0));
        }
        // 有id，老顾客
        Customer c = customers.get(id);
        if (buyOrRefund) {
            c.buy++;
        } else {
            c.buy--;
        }
        if (c.buy == 0) {
            customers.remove(id);
        }

        if (!candHeap.contains(c) && !topHeap.contains(c)) {
            // 新人均不在这两个堆里
            // 得奖区未满，进得奖区
            if (topHeap.size() < K) {
                c.enterTime = time;
                topHeap.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 {
            // 在 topK 堆里
            if (c.buy == 0) {
                topHeap.remove(c);
            } else {
                // 重新调整堆
                topHeap.resign(c);
            }
        }
        // 一个顾客判断结束后，开始比较两个堆大小
        kMove(time);
    }

    private void kMove(int time) {
        if (candHeap.isEmpty()) {
            return;
        }
        // 得奖区未满，直接进
        if (topHeap.size() < K) {
            Customer p = candHeap.pop();
            p.enterTime = time;
            topHeap.push(p);
        } else {
            // 候选区的头 能够替换 得奖区的尾
            if (candHeap.peek().buy > topHeap.peek().buy) {
                Customer oldK = topHeap.pop();
                Customer newK = candHeap.pop();
                oldK.enterTime = time;
                newK.enterTime = time;
                candHeap.push(oldK);
                topHeap.push(newK);
            }
        }
    }
    
    // 输出 得奖区 所有的顾客
    public List<Integer> getAllK() {
        List<Customer> customers = topHeap.getAllElements();
        List<Integer> ans = new ArrayList<>();
        for (Customer c : customers) {
            ans.add(c.id);
        }
        return ans;
    }
}

注意看代码上面的注释哦！

你学会了么？

~点赞 ~ 关注 ~ 不迷路 ~！！！