懒删除堆

如何「优雅」地删除元素在计算机领域中是一个十分重要的问题：比如删除磁盘中的文件，是每删一条记录就写一次磁盘、还是聚集多条待删除的记录再写磁盘？删除是物理意义上的删除，即将那片空间全部的比特全部设为 0、还是仅仅标记删除？

堆（优先级队列、二叉堆）中删除元素的时间复杂度是 O(n) 级别的，必须遍历一遍元素才能找到待删除的元素；事实上，很多语言的优先级队列的 API 中是没有 remove() 方法的。Java 中的优先级队列虽然支持 remove() 方法，但是不应该频繁使用。本文介绍一种在堆中「懒」删除元素的方法。

例题引入

参考 2353. 设计食物评分系统 - 力扣（Leetcode）

思路分析

这道题中涉及到对堆中的元素进行更新。常规的想法是，我们将旧的值 remove 出去，再 add 新的值。但是 remove 的时间复杂度是线性的，在堆中的效率是很低的。事实上，我们完全可以跳过删除元素这一步，直接把新的值加入堆中；

当需要对堆进行 peek 或是 poll 操作时，必须首先检查堆顶的元素此时是否是「过期」的。我们可以用一个容器来保存某元素当前最新的值，例如哈希表

class FoodRatings {
    class Food {
        String name;
        int rating;
        Food (String name, int rating) {
            this.name = name;
            this.rating = rating;
        }
    }
    HashMap<String, Integer> f2r = new HashMap<>(); // 存储某食物最新的评分
    HashMap<String, String> f2c = new HashMap<>();
    HashMap<String, PriorityQueue<Food>> heaps = new HashMap<>();
    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        int n = foods.length;
        for (int i = 0; i < n; i++) {
            String name = foods[i];
            String cuisine = cuisines[i];
            int rating = ratings[i];
            Food food = new Food(name, rating);
            if (!heaps.containsKey(cuisine)) {
                heaps.put(cuisine, new PriorityQueue<>(new Comparator<Food>() {
                    @Override
                    public int compare(Food o1, Food o2) {
                        if (o1.rating == o2.rating) {
                            return o1.name.compareTo(o2.name);
                        }
                        return o2.rating - o1.rating;
                    }
                }));
            }
            heaps.get(cuisine).add(food);
            f2r.put(name, rating);
            f2c.put(name, cuisine);
        }
    }

    public void changeRating(String food, int newRating) {
        // 仅添加，不删除
        Food f = new Food(food, newRating);
        f2r.put(food, newRating);
        String cuisine = f2c.get(food);
        heaps.get(cuisine).add(f);
    }

    public String highestRated(String cuisine) {
        var heap = heaps.get(cuisine);
        while (heap.peek().rating != f2r.get(heap.peek().name)) {
            // 判断堆顶元素是否是过期的
            heap.poll();
        }
        return heap.peek().name;
    }
}

以下是几点说明

• JDK 原生没有 Pair 类，如果想使用 Pair 类，使用 JavaFX 中的 Pair 类
• 如果确实需要堆中保存的都是最新的元素，可以考虑使用有序集合，在 Java 中对应 TreeSet。有序集合增加、删除元素的时间复杂度是 O(logn)，查找集合中最小元素的复杂度也是 O(logn)；作为对比，二叉堆增加元素的时间复杂度是 O(logn)，删除元素是 O(n)，查找集合中最小元素的复杂度是 O(1)。如果仅关心集合中的最小元素，使用懒删除堆更合适一些

其他例题

• 100258. 最高频率的 ID - 力扣（LeetCode）

  周赛时这题做得很不好…

  这道题也是懒删除堆技巧的典型应用了。我们直接将新构造的 MyClass 实例压入堆中，在需要判断当前出现频率最高的 ID 时，检查当前堆顶元素的 cnt 值是否与哈希表中的新值相等

  class Solution {
      public long[] mostFrequentIDs(int[] nums, int[] freqs) {
          int n = nums.length;
          long[] ans = new long[n];
          HashMap<Integer, Long> map = new HashMap<>();
          PriorityQueue<MyClass> maxHeap = new PriorityQueue<>(new Comparator<MyClass>() {
              @Override
              public int compare(MyClass o1, MyClass o2) {
                  if (o2.cnt - o1.cnt >= 0) {
                      return 1;
                  }
                  return -1;
              }
          });
          for (int i = 0; i < n; i++) {
              int num = nums[i];
              int freq = freqs[i];
              long oldCnt = map.getOrDefault(num, 0L);
              long curCnt = oldCnt + freq;
              map.put(num, curCnt);
              maxHeap.add(new MyClass(num, curCnt));
              while (map.get(maxHeap.peek().id) != maxHeap.peek().cnt) {
                  // delete outdated info
                  maxHeap.poll();
              }
              ans[i] = maxHeap.peek().cnt;
          }
          return ans;
      }
  
      class MyClass {
          int id;
          long cnt;
  
          MyClass(int id, long cnt) {
              this.id = id;
              this.cnt = cnt;
          }
      }
  }

  这道题的另一个解法是维护一个 key 为频率，value 为频率的频率的有序哈希表

  public long[] mostFrequentIDs(int[] nums, int[] freqs) {
      int n = nums.length;
      long[] ans = new long[n];
      HashMap<Integer, Long> map = new HashMap<>();
      TreeMap<Long, Long> treeMap = new TreeMap<>(Collections.reverseOrder()); // in descending order
      for (int i = 0; i < n; i++) {
          int num = nums[i];
          int freq = freqs[i];
          long oldCnt = map.getOrDefault(num, 0L);
          long curCnt = oldCnt + freq;
          treeMap.put(curCnt, treeMap.getOrDefault(curCnt, 0L) + 1L);
          treeMap.put(oldCnt, treeMap.getOrDefault(oldCnt, 1L) - 1L);
          map.put(num, curCnt);
          while (treeMap.firstEntry().getValue() == 0) {
              treeMap.pollFirstEntry();
          }
          if (treeMap.isEmpty()) {
              ans[i] = 0;
          } else {
              ans[i] = treeMap.firstKey();
          }
      }
      return ans;
  }