Priority Queues With Distinct Elements
August 9, 2016
I recently needed a priority queue that contains no duplicate elements; if an attempt is made to add an element to the priority queue that is already present in the priority queue, the priority queue remains unchanged. As far as I know, none of the standard priority queue algorithms provide such a feature; they can’t, because they are all based on trees, and any element of the priority queue can be in either branch at any level of the tree.
Your task is to write a program that provides the data structure of priority queues with distinct elements. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Here’s a solution in Java.
It extends Java’s built-in priority queue and overrides *add* and *remove*.
import java.util.Arrays; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; public class PriorityQueueDistinct<E> extends PriorityQueue<E> { private Set<E> elements = new HashSet<>(); @Override public boolean add(E e) { if (elements.contains(e)) return false; boolean added = super.add(e); if (added) elements.add(e); return added; } @Override public boolean remove(Object o) { boolean removed = super.remove(o); if (removed) elements.remove(o); return removed; } public static void main(String[] args) { PriorityQueueDistinct<Integer> priorityQueue = new PriorityQueueDistinct<>(); // Add 0, 1, 2, 3, 4 and output the priority queue. for (int i = 0; i < 5; ++i) priorityQueue.add(i); System.out.println(priorityQueue); // Add 0, 1, 2, 3, 4 again and output the priority queue. // Output should remain the same as above. for (int i = 0; i < 5; ++i) priorityQueue.add(i); System.out.println(priorityQueue); } }Here’s the output from the test in the main method.
Here is a Haskell version that uses the “priority search queue” provided by the psqueues package.
-- There is an existing data structure called the "priority search queue" that -- allows us to easily implement this. It's a priority queue that also supports -- efficient searching. In addition to a priority and a value, each item also -- has a search key. The implementation we use is OrdPSQ, provided by the -- psqueues package. -- -- Our new function, insert', makes use of the alter function provided by -- OrdPSQ. This is sort of a Swiss army knife function that allows us to -- insert, delete or modify items associated with a given key. Insert' simply -- uses its second argument as both the key and the value. -- -- A fuller implementation would wrap OrdPSQ in a new type and provide its own -- API (e.g. hiding the keys) to prevent other functions from screwing up the -- "distinct items" property that we want to maintain. import Control.Arrow ((>>>)) import Control.Monad (mplus) import Data.List (unfoldr) import Data.OrdPSQ -- Insert value v with priority p into the queue, only if the value is absent. insert' :: (Ord v, Ord p) => p -> v -> OrdPSQ v p v -> OrdPSQ v p v insert' p v = snd . alter update v where update pv = ((), pv `mplus` Just (p, v)) -- Demonstrate our new insertion function. demo :: OrdPSQ String Int String -> OrdPSQ String Int String demo = insert' 3 "nematode" >>> insert' 2 "axolotl" >>> insert' 1 "zebra" >>> insert' 0 "axolotl" -- This won't be added because the value already -- exists. So "axolotl" will still appear after -- "zebra" when sorted by priority. -- Sort the values of a queue in order of priority by repeatedly extracting the -- minimum priority item. sortByPriority :: (Ord k, Ord p) => OrdPSQ k p v -> [v] sortByPriority = unfoldr step where step = fmap (\(_, _, v, q') -> (v, q')) . minView main :: IO () main = print $ sortByPriority $ demo emptya bit late but….how about using a heap it acts as a priority queue and we can add an extra condition to check for duplicates and skipping over them
[…] a little bit of time. The second change is more important; we use the distinct priority queue of a previous exercise to eliminate duplicate candidates, which greatly reduced the amount of computation needed to find […]
A solution in Racket.