更新时间:2023-11-28 17:30:04
The paper says this about the priority queue that is being used:
Given these needs, a priority queue is an attractive choice, especially since this data structure natively supports multiple items with the same priority (dequeuing in them arbitrary order).
Since duplicate entries are not really useful in the algorithm they have to be treated specially.
The adjust
function, which removes the minimal composite, keeps adjusting the priority queue until it can be sure that all duplicates of the minimal element are removed:
adjust table
| n <= x = adjust (PQ.deleteMinAndInsert n_ ns table)
| otherwise = table
where ...
If the currently first element (n
) was small enough to be removed, adjust calls itself again to also check the next element in the remaining queue. Only when there are no small elements left it stops recursing.