使用优先级队列PriorityQueue类解决topK问题

tech2024-06-10  69

top K问题 求解第top K大的问题,通过priorityqueue构造小顶堆和限制堆的大小解决。 求解第top K小的问题,通过priorityqueue构造大顶堆和限制堆的大小解决。 参考:https://blog.csdn.net/hefenglian/article/details/81807527

非线程安全 此实现不是同步的。如果多个线程中的任意线程修改了队列,则这些线程不应同时访问 PriorityQueue 实例。相反,请使用线程安全的 PriorityBlockingQueue 类

priorityqueue.toString() 不保证完全有序 priorityqueue.toString() 不保证完全有序,只有按迭代顺序priorityqueue.poll() [也即],才能保证打印出来的元素完全有序。 因为priorityqueue的实现基于数组实现的最小堆,是一个完全二叉树,熟悉堆的特性的可以知道,最小堆只是保证左右子树大于堆顶元素,但两个子元素谁大谁小并没有规定,这跟入队顺序有关系。 参考:PriorityQueue是否真正有序 https://blog.csdn.net/michaelgo/article/details/81983360

最新回复(0)