Customized priority function in DataStructure["PriorityQueue"]?

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.

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} *)