优先级队列不要用来存实时更新的值

在做692. 前K个高频单词这道题的时候&＃xff0c;我想的是用一个哈希表存储各个单词出现的次数&＃xff0c;用优先级队列存储出现次数最多的K个单词&＃xff0c;自定义优先级队列的比较函数为比较哈希表中每个单词的次数。然后一次遍历&＃xff0c;构建哈希表的同时不断向优先级队列插入和弹出&＃xff0c;保持优先级队列只有出线次数最多的K个元素&＃xff0c;并且头部是出线次数第K多的元素。

这种方法最后证明是错误的。主要原因是哈希表是在线更新的&＃xff0c;这种更新导致过程中优先级队列不是一个正确的堆。比如原来的堆是[“yan", "jia", "shi", "sha", "cha"]&＃xff0c;三个字符串出现的次数依次为5, 2, 2, 1, 1。然后在线更新将"sha"的出现次数更新为4&＃xff0c;而我的算法这时候是不对堆做任何处理的&＃xff0c;这时候其实这个优先级队列已经不是堆了&＃xff0c;"sha"的父节点的次数比它小。然后将头部弹出后&＃xff0c;堆会被调整成["jia", "shi", "sha", "cha"]&＃xff0c;这明显是错误的&＃xff0c;"sha"本应该在头部的。因为堆调整的时候会默认它的所有节点都小于等于其父节点的次数&＃xff0c;这个假设已经不正确了&＃xff0c;导致最终结果也不正确了。

不要在线更新&＃xff0c;影响到堆的实时排序。