I have a String I need to sort based on a custom order and I am using priority queues but the priority queue fails with duplicates

Question

public class CustomSortString {

public String customSortString(String order, String s) {
    if (order == null || s == null) {
        return "";
    }
    int len = s.length();
    PriorityQueue<Character> minHeap = new PriorityQueue<>(len, (a, b) -> {
        if (order.indexOf(a) > order.indexOf(b)) {
            return 1;
        } else if (order.indexOf(a) < order.indexOf(b)) {
            return -1;
        } else {
            return 0;
        }
    });
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < len; i++) {
        minHeap.add(s.charAt(i));
    }
    for (char c : minHeap) {
        result.append(c);
    }
    return result.toString();
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    CustomSortString c = new CustomSortString();
    System.out.println(c.customSortString("kqep", "pekeq"));
}

}

But this does not provide desired results. Because when I look at the minHeap after I add all elements I see the problem : enter image description here

the 'e' s don't have the same score for some reason and that is causing the program to fail. Can you please help?

score 1 · Answer 1 · answered Dec 15 '21 at 02:32

You are actually iterating this queue by for-each loop:

for (char c : minHeap) {
     result.append(c);
}

So getting one element per iteration does not rebuild the heap. See PriorityQueue#Itr#next.

Try:

while (!minHeap.isEmpty()) {
    result.append(minHeap.poll());
}

I have a String I need to sort based on a custom order and I am using priority queues but the priority queue fails with duplicates

1 Answers1