Customized priority function in DataStructure["PriorityQueue"]?

Question

I'm using Mathematica 12.1. The documentation for DataStructure["PriorityQueue"] claims that,

... the highest-priority element is always returned.

The priority of two elements is determined by the Order function.

I'm wondering if I could use my own priority function with it, so I tried "overloading" the Order function (semantically) like

With[{f = 20 - # &},
 Block[{Order = Order[f[#1], f[#2]] &},
  Module[{hp = CreateDataStructure["PriorityQueue"]},
   Scan[hp["Push", #] &, Range[20]];
   hp["Pop"]
   ]]]

but failed to change its behavior -- outcome is still 20 while 0 is expected.

Could this be achieved or one has to do the implementation by oneself since seemingly DataStructures don't support functions like SortBy?

Answer 1

Following the lead of your own workaround you might consider an abstraction like this:

pqpat = PQ : DataStructure["PriorityQueue", ___];

orderQueue[pqpat, ofn_]["Push", val_] := PQ["Push", {ofn@val, val}]
orderQueue[pqpat, ofn_]["Pop"] := PQ["Pop"][[2]]

hp = CreateDataStructure["PriorityQueue"];

foo = orderQueue[hp, 20 - # &];

Do[foo["Push", i], {i, 20}]

Table[foo["Pop"], {20}]

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

I'll leave it to you to implement the remaining methods.

Answer 2

I just found that, when Order compares two lists, if their first elements are already unequal, the result is in effect the Order between them. So here is a solution I can come up with:

With[{f = 20 - # &},
 Module[{hp = CreateDataStructure["PriorityQueue"]},
  Scan[hp["Push", {f[#], #}] &, Range[20]];
  Table[hp["Pop"][[2]], 20]
 ]]
(* {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} *)

You push data together with their priorities. When you pop, you need to discard the priority.

Other test:

With[{f = -RealAbs[# - 10] &}, (* Minimize |x-10| *)
 Module[{hp = CreateDataStructure["PriorityQueue"]},
  Scan[hp["Push", {f[#], #}] &, Range[20]];
  Table[hp["Pop"][[2]], 20]
 ]]
(* {10, 11, 9, 12, 8, 13, 7, 14, 6, 15, 5, 16, 4, 17, 3, 18, 2, 19, 1, 20} *)

Output is the same compared to

Reverse@SortBy[Range[20], -RealAbs[# - 10] &]
(* {10, 11, 9, 12, 8, 13, 7, 14, 6, 15, 5, 16, 4, 17, 3, 18, 2, 19, 1, 20} *)

Answer 3

numElements = 12;

(*
 Here is a way to reverse the order function i.e. 
 use**Order[#2, #1]** & for *ascending* and
 **Order[#1, #2] &** for *descending*.
*)

data = Table[ RandomInteger[1000], {i, numElements}];
pq = CreateDataStructure["PriorityQueue", data, Order[#2, #1] &];
Print["Pushed values = ", data];
For [i = 1, i <= numElements, i++, (
  impq = 
   Rasterize[pq["Visualization"], ImageSize -> Small, 
    ImageResolution -> 400];
  Print[impq];
  Print["Popped value = ", pq["Pop"]];
  )
 ]