Резюме:
PriorityQueue в Java реализуется бинарной малой верхней кучей, которая может быть представлена полным бинарным деревом. Эта статья начинается с функции интерфейса Queue в сочетании с яркими диаграммами, анализирует конкретный процесс и временную сложность каждой операции PriorityQueue простым языком и позволит читателям получить четкое и глубокое понимание PriorityQueue.
PriorityQueue в Java реализует интерфейс Queue и не допускает пустых элементов, реализуется через кучу, а именно небольшую верхнюю кучу, реализуемую полным бинарным деревом (вес любого нелистового узла не больше его значения). веса левого и правого дочерних узлов), что означает, что массив может использоваться в качестве базовой реализации PriorityQueue.
Общее введение
В качестве примера для объяснения стека и очереди использовался Java ArrayDeque.На самом деле существует специальная очередь PriorityQueue, которая является очередью с приоритетом. Функция приоритетной очереди состоит в том, чтобы гарантировать, что извлекаемые каждый раз элементы имеют наименьший вес в очереди (очередь приоритетов Java каждый раз принимает наименьший элемент, а очередь приоритетов C++ каждый раз принимает наибольший элемент). Здесь задействовано отношение размера.О размере элементов можно судить по естественному порядку самих элементов или по компаратору (Comparator, подобно функтору C++), переданному во время построения.
На приведенном выше рисунке мы пронумеровали каждый элемент в порядке иерархического обхода.Если вы достаточно внимательны, вы обнаружите, что номера родительского узла и дочернего узла связаны.Точнее, количество родительских и дочерних узлов имеет следующее отношение:
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
С помощью приведенных выше трех формул можно легко вычислить индексы родительского узла и дочернего узла узла. Вот почему вы можете напрямую использовать массивы для хранения кучи.
Операции peek() и элементов PriorityQueue имеют постоянное время, а временная сложность методов add(), offer(), remove() без параметров и poll() равна log(N).
API
1. Внутренние свойства
//默认用于存储节点信息的数组的大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//用于存储节点信息的数组
transient Object[] queue;
//数组中实际存放元素的个数
private int size = 0;
//Comparator比较器
private final Comparator comparator;
//用于记录修改次数的变量
transient int modCount = 0;
Мы знаем, что существует две основные категории структур данных, такие как кучи, большие корневые кучи и малые корневые кучи. И каждый раз, когда мы корректируем структуру, мы постоянно сравниваем значение двух элементов по определенному правилу, а затем корректируем структуру, здесь нам нужно использовать наш компаратор. Таким образом, создание экземпляра PriorityQueue в основном предназначено для инициализации емкости массива и компаратора, и в PriorityQueue есть следующие конструкторы:
2. Конструктор
/**
* Creates a {@code PriorityQueue} with the default initial
* capacity (11) that orders its elements according to their
* {@linkplain Comparable natural ordering}.
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* Creates a {@code PriorityQueue} with the specified initial
* capacity that orders its elements according to their
* {@linkplain Comparable natural ordering}.
*
* @param initialCapacity the initial capacity for this priority queue
* @throws IllegalArgumentException if {@code initialCapacity} is less
* than 1
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* Creates a {@code PriorityQueue} with the default initial capacity and
* whose elements are ordered according to the specified comparator.
*
* @param comparator the comparator that will be used to order this
* priority queue. If {@code null}, the {@linkplain Comparable
* natural ordering} of the elements will be used.
* @since 1.8
*/
public PriorityQueue(Comparator comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* Creates a {@code PriorityQueue} with the specified initial capacity
* that orders its elements according to the specified comparator.
*
* @param initialCapacity the initial capacity for this priority queue
* @param comparator the comparator that will be used to order this
* priority queue. If {@code null}, the {@linkplain Comparable
* natural ordering} of the elements will be used.
* @throws IllegalArgumentException if {@code initialCapacity} is
* less than 1
*/
public PriorityQueue(int initialCapacity,
Comparator comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified collection. If the specified collection is an instance of
* a {@link SortedSet} or is another {@code PriorityQueue}, this
* priority queue will be ordered according to the same ordering.
* Otherwise, this priority queue will be ordered according to the
* {@linkplain Comparable natural ordering} of its elements.
*
* @param c the collection whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of the specified collection
* cannot be compared to one another according to the priority
* queue's ordering
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(Collection c) {
if (c instanceof SortedSet) {
SortedSet ss = (SortedSet) c;
this.comparator = (Comparator) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue) {
PriorityQueue pq = (PriorityQueue) c;
this.comparator = (Comparator) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified priority queue. This priority queue will be
* ordered according to the same ordering as the given priority
* queue.
*
* @param c the priority queue whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of {@code c} cannot be
* compared to one another according to {@code c}'s
* ordering
* @throws NullPointerException if the specified priority queue or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue c) {
this.comparator = (Comparator) c.comparator();
initFromPriorityQueue(c);
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified sorted set. This priority queue will be ordered
* according to the same ordering as the given sorted set.
*
* @param c the sorted set whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of the specified sorted
* set cannot be compared to one another according to the
* sorted set's ordering
* @throws NullPointerException if the specified sorted set or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet c) {
this.comparator = (Comparator) c.comparator();
initElementsFromCollection(c);
}
Выше есть четыре основных конструктора, и первые три внутренне вызывают последний конструктор. Два параметра, один из которых указывает емкость массива для инициализации, а другой используется для инициализации компаратора. Если их значения не указаны, по умолчанию они равны DEFAULT_INITIAL_CAPACITY (11) для емкости и null для компаратора. Давайте посмотрим, как добавлять и удалять узлы в экземпляре PriorityQueue, сохраняя при этом исходную структуру кучи неизменной.
3. Часто используемые функции
Анализ метода
логическое добавление (E e) и логическое предложение (E e)
/**
* Inserts the specified element into this priority queue.
*
* @return {@code true} (as specified by {@link Collection#add})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
return offer(e);
}
/**
* Inserts the specified element into this priority queue.
*
* @return {@code true} (as specified by {@link Queue#offer})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
На самом деле внутренний вызов метода add по-прежнему является методом предложения, поэтому мы в основном смотрим на то, как реализовано предложение, чтобы добавить элемент в структуру кучи и сохранить эту структуру от разрушения. Прежде всего, этот метод определяет переменную для получения количества элементов, фактически хранящихся в очереди, за которым следует оценка if, если массив был полностью использован (нет свободного места), будет вызван метод роста для расширения , а метод наращивания будет основан на конкретном Судя по ситуации, если исходный массив больше, он будет удвоен +2, иначе емкость будет увеличена на 50%.Поскольку конкретный код относительно ясен, он будет здесь не повторяться.
/**
* Increases the capacity of the array.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
Затем оцените, является ли полное бинарное дерево пустым.Если нет узла, то новый узел может быть непосредственно использован в качестве корневого узла.В противном случае будет вызван siftUp для добавления новых элементов и корректировки структуры, поэтому этот метод является ключевым точка.
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons. the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
/**
* Retrieves, but does not remove, the head of this queue. This method
* differs from {@link #peek peek} only in that it throws an exception if
* this queue is empty.
*
*
This implementation returns the result of peek
* unless the queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
@SuppressWarnings("unchecked")
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
удалить() и опрос()
Семантика remove() и poll() абсолютно одинакова, оба получают и удаляют элемент в начале очереди, разница в том, что первый генерирует исключение, когда метод терпит неудачу, а второй возвращает null. Поскольку операция удаления изменит структуру очереди, для сохранения характера малой верхней кучи необходимо внести необходимые корректировки.
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll poll} only in that it throws an exception if this
* queue is empty.
*
*
This implementation returns the result of poll
* unless the queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* Retrieves and removes the head of the queue represented by this deque
* (in other words, the first element of this deque), or returns
* {@code null} if this deque is empty.
*
*
This method is equivalent to {@link #pollFirst}.
*
* @return the head of the queue represented by this deque, or
* {@code null} if this deque is empty
*/
public E poll() {
return pollFirst();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
head = (h + 1) & (elements.length - 1);
return result;
}
remove(Object o)
Метод remove(Object o) используется для удаления в очереди элемента, равного o (при наличии нескольких равных удаляется только один) Этот метод не является методом в интерфейсе Queue, а методом в интерфейсе Интерфейс коллекции. Поскольку операция удаления изменит структуру очереди, ее необходимо настроить, а поскольку положение удаляемого элемента может быть произвольным, процесс настройки несколько более громоздкий, чем другие функции. В частности, remove(Object o) можно разделить на 2 случая: 1. Удаляется последний элемент. Просто удалите его напрямую, никаких настроек не требуется. 2. Удален не последний элемент.
/**
* Removes a single instance of the specified element from this queue,
* if it is present. More formally, removes an element {@code e} such
* that {@code o.equals(e)}, if this queue contains one or more such
* elements. Returns {@code true} if and only if this queue contained
* the specified element (or equivalently, if this queue changed as a
* result of the call).
*
* @param o element to be removed from this queue, if present
* @return {@code true} if this queue changed as a result of the call
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
Если индекс удаления не является последней позицией, значение последнего узла будет получено и удалено первым, а затем значение последнего узла будет перезаписано значением удаляемого узла, и структура будет скорректирована. После того, как уравнивание завершено, очередь будет оцениваться.[i]==move, если true означает, что структура не корректируется после добавления элементов (для удовлетворения структуры кучи), то структура будет корректироваться вверх. (Если структура была скорректирована вниз, нет необходимости корректировать ее вверх.) Если значение queue[i] != move равно true, это означает, что структура была скорректирована вверх, тогда будет возвращено перемещение. (Что касается того, зачем возвращать перемещение после корректировки структуры вверх, то это в основном используется для итераторов, которые пока не будут здесь представлены).
/**
* Removes the ith element from queue.
*
* Normally this method leaves the elements at up to i-1,
* inclusive, untouched. Under these circumstances, it returns
* null. Occasionally, in order to maintain the heap invariant,
* it must swap a later element of the list with one earlier than
* i. Under these circumstances, this method returns the element
* that was previously at the end of the list and is now at some
* position before i. This fact is used by iterator.remove so as to
* avoid missing traversing elements.
*/
@SuppressWarnings("unchecked")
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
фокус
Точка — это метод siftDown(int k, E x).Функция этого метода состоит в том, чтобы начать с позиции, заданной k, и поменять местами x вниз слой за слоем с меньшим из левого и правого дочерних элементов текущей точки, пока x меньше или равен левому и правому дочерним элементам любого из них.
/**
* Inserts item x at position k, maintaining heap invariant by
* demoting x down the tree repeatedly until it is less than or
* equal to its children or is a leaf.
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
Вот общий процесс удаления узла.Этот метод является относительно низкоуровневым.На самом деле есть и другие методы удаления узлов в PriorityQueue,но почти все они внутренне вызывают метод removeAt.
Суммировать:
Способ и использование этой приоритетной очереди относительно громоздки, и, условно говоря, в этом нужно разобраться.Здесь перечислены лишь некоторые из методов повседневного использования, и многие из них не объясняются подробно, как раньше.Слишком много внутренних Вызов методов. Хорошие примеры, я должен позволить каждому взглянуть на исходный код самостоятельно. Эта статья эквивалентна вводной информации.