Почему они назвали PriorityQueue
, если вы не можете insertWithPriority? Это похоже на кучу. Есть ли различия? Если нет разницы, то почему он был назван PriorityQueue
, а не кучей?
Как Java PriorityQueue отличается от минимальной кучи?
Ответ 1
Добавить() работает как insertWithPriority.
Вы можете определить приоритет для типа, который вы хотите использовать с помощью конструктора:
PriorityQueue(int, java.util.Comparator)
смотреть под http://download.oracle.com/javase/1,5.0/docs/api/java/util/PriorityQueue.html
Порядок, который дает компаратор, будет представлять приоритет в очереди.
Ответ 2
Приоритет PriorityQueue используется с Min-Heap, то есть верхний элемент является минимальным в куче.
Чтобы реализовать максимальную кучу, вы можете создать свой собственный компаратор:
import java.util.Comparator;
public class MyComparator implements Comparator<Integer>
{
public int compare( Integer x, Integer y )
{
return y - x;
}
}
Итак, вы можете создать мини-кучу и максимальную кучу следующим образом:
PriorityQueue minHeap=new PriorityQueue();
PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator());
Ответ 3
Для макс-кучи вы можете использовать:
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
Ответ 4
Неограниченная очередь приоритетов на основе кучи приоритетов. Элементы очереди приоритетов упорядочиваются в соответствии с их естественным порядком или с помощью
Comparator
, предусмотренного во время построения очереди, в зависимости от того, какой конструктор используется.
Приоритет должен быть неотъемлемым свойством объектов в очереди. Элементы упорядочиваются на основе какого-то сравнения. Чтобы вставить какой-либо объект с заданным приоритетом, вы просто установите любое поле на объект, влияющее на упорядочение, и add()
it.
И, как отметил @Daniel,
В общем случае объекты Java называются на основе функциональности, которую они предоставляют, а не называются на основе того, как они реализованы.
Ответ 5
Очередь приоритетов представлена как сбалансированная двоичная куча: два дочерних очереди [n] - это очередь [2 * n + 1] и очередь [2 * (n + 1)]. Очередь приоритетов упорядочивается с помощью компаратора или с помощью элемента естественного упорядочения.
Вот рабочий код для maxHeap и minHeap с помощью PriorityQueue
-
class HeapDemo {
private final static int HEAP_SIZE = 10; //size of heap
//INNER CLASS
static class maxHeapComparator implements Comparator<Integer> {
@Override
public int compare (Integer x, Integer y) {
return y-x; //reverse order
}
}
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE, new maxHeapComparator());
for(int i=1; i<=HeapDemo.HEAP_SIZE; ++i){
int data = new Random().nextInt(100) +1; //number between 0 to 100
minHeap.add(data);
maxHeap.add(data);
}
System.out.print("\nMIN Heap : ");
Iterator<Integer> iter = minHeap.iterator();
while(iter.hasNext()){
System.out.print(iter.next() + " ");
}
System.out.print("\nMAX Heap : ");
iter = maxHeap.iterator();
while(iter.hasNext()) {
System.out.print(iter.next() + " ");
}
}
}
образец o/p:
MIN Heap : 20 32 37 41 53 91 41 98 47 86
MAX Heap : 98 91 41 53 86 20 37 41 32 47
Ответ 6
От http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
Неограниченная приоритетная очередь, основанная на куче приоритетов. Элементы приоритетной очереди упорядочены в соответствии с их естественным порядком или компаратором, предоставленным во время построения очереди.
для целых, длинных, чисел с плавающей запятой, двойных, символьных, логических (то есть примитивных типов данных) естественный порядок возрастания, поэтому Arrays.sort(arr) {где arr массив массивов примитивных типов} сортирует значение arr в в порядке возрастания Вы можете изменить естественный порядок, используя Comparator
Компаратор можно использовать двумя способами:
-
Одним из способов является то, как DpGeek показал
-
Другой способ - использование анонимного класса. Например
Arrays.sort(arr, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
return y - x;
}
});
- Если у вас есть java8, то вы можете использовать лямбда-выражение
Arrays.sort(arr, (Integer x, Integer y) → y - x);
Это сортирует массив arr в порядке убывания