сортировать элементы в Java, используя приоритетную очередь - PullRequest
Новая
       85

сортировать элементы в Java, используя приоритетную очередь

0 голосов
/ 11 июня 2018

Я хочу отсортировать элементы, используя Очередь приоритетов в Java.

Вот мой код.Что в этом плохого? 

import java.io.*;
import java.util.*;

class PQ {
    static class IntCompare implements Comparator<Integer>{
        @Override
        public int compare(Integer arg0, Integer arg1) {
            if(arg0 > arg1)
                return -1;
            else if(arg0 < arg1)
                return 1;
            else
                return 0;
        }
   }

    public static void main (String[] args) {
        int a[] = { 1, 3, 8, 5, 2, 6 };

        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);

        for(int i = 0; i < a.length; i++)
            pq.add(a[i]);

        System.out.println(pq);
    }
}

мой вывод: 

8, 5, 6, 1, 2, 3

правильный вывод: 

8, 6, 5, 3, 2, 1

Ответы [ 3 ]

0 голосов
/ 11 июня 2018

Попробуйте следующее, список содержит элементы в отсортированном порядке. Ключ приоритета сам по себе не поддерживает элементы в отсортированном порядке, он просто сохраняет верхний элемент как минимальный или максимальный на основе вашей реализации PQ. 

public static void main (String[] args) {
        int a[]={1,3,8,5,2,6};
        Comparator<Integer> c = new IntCompare();
        PriorityQueue<Integer> pq=new PriorityQueue<>(c);
        for(int i=0;i<a.length;i++)
            pq.add(a[i]);
        ArrayList<Integer> list  = new ArrayList<>();
        while(!pq.isEmpty()){
            list.add(pq.poll());
        }
        for(Integer i : list)
            System.out.println(i);
}
0 голосов
/ 11 июня 2018

Когда вы вызываете System.out.println(pq), метод toString вызывается неявно.

Метод toString для PriorityQueue расширяется от AbstractCollection, который

Возвращает строковое представление этой коллекции.Строковое представление состоит из списка элементов коллекции в порядке их возврата ее итератором , заключенным в квадратные скобки ("[]").

В то время как iterator из PriorityQueue не гарантирует прохождение в определенном порядке:

Итератор, предоставленный в методе iterator (), не гарантирует прохождение элементов очереди с приоритетами влюбой определенный порядок.

, поскольку очередь основана на heap .

Вы можете опрашивать элементы один за другим, чтобы получить упорядоченные элементы: 

while (pq.size() != 0) {
    System.out.print(pq.poll() + ","); // 8,6,5,3,2,1,
}
0 голосов
/ 11 июня 2018

Вы должны poll() все элементы, пока очередь не станет пустой, и сохранить их где-нибудь, чтобы упорядочить их.

...