5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ It seems to me that a custom ordering function would need to be contained in the data structure, to be used with every "Push" operation. It seems chaotic to have an ad hoc Order behavior for each operation. I suspect you are seeking functionality that isn't (yet) implemented. $\endgroup$ – Mr.Wizard Jun 22 '20 at 6:52
  • $\begingroup$ @Mr.Wizard Yes. So after posting the question I was thinking that, okay, we can't have an ad hoc Order's behavior, but we can change what we pass to it! Then I seem able to answer my own question :-) Please contribute while there's room for improvement. $\endgroup$ – SneezeFor16Min Jun 22 '20 at 7:25
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.