Во-первых, разница между очередью и приоритетной очередью
- очередьэтоFIFO(Первое в первую очередь) в первую очередь, в первую очередь структура данных, соответствующая сцене очередей в жизни, человек впереди всегда проходит первым,последовательно.
- приоритетная очередьэто специальная очередь, от слова "приоритет" видно чтоСуществует «феномен очередей». Например, стоя в очереди на вокзале, некоторые спешащие люди вскочат в очередь и первыми пройдут проверку билетов. приоритетная очередьСостоит не менее чем из двух действующихСтруктура данных:вставлять, т. е. вставка элемента в приоритетную очередь (enqueue); иdeleteMin (удалить наименьший), его роль заключается в поиске и удалении наименьшего элемента в приоритетной очереди (dequeue).
Во-вторых, характеристики приоритетной очереди (кучи)
Реализация приоритетных очередей часто используетсядвоичная куча,В структуре данных приоритетная очередь также обычно относится к куче..
Два свойства кучи:
структурный:Куча представляет собой бинарное дерево, которое полностью заполнено, за исключением нижнего слоя, узлы нижнего слоя заполняются слева направо.Такое дерево называетсяПолное бинарное дерево.
-
Порядок кучи:Поскольку мы хотим быстро найти наименьший элемент, наименьший элемент должен быть в корне,любой узел меньше, чем его потомки,ЭтоМаленькая стопка (MIN-HEAP); если вы ищете максимальный элемент, максимальный элемент должен быть в корне,Любой узел должен быть больше, чем его потомки,ЭтоБольшая верхняя куча (Max-heap).
Структурный:
полное бинарное дерево
Путем наблюдения было установлено, чтоПолное бинарное дерево может быть непосредственно представлено массивомбез использования других структур данных. Таким образом, нам нужно только передать размер, чтобы построить структуру приоритетной очереди (элементы сравниваются с помощью метода compareTo).
public class PriorityQueue<T extends Comparable<? super T>> {
public PriorityQueue(int capacity) {
currentSize = 0;
array = (T[]) new Comparable[capacity + 1];
}
}
Для элемента в любой позиции i в массиве еголевый сынв месте2iНаправильный сынсуществует2i+1начальство,родительский узелвi/2(округлено вниз). Обычно он сохраняется из индекса массива 1. Преимущество этого в том, что легко найти левый и правый и родительские узлы. Если начать с 0, левый дочерний узел находится в 2i+1, правый дочерний узел — в 2i+2, а родительский узел — в (i-1)/2 (округлено вниз).
Порядок кучи:
мы строимМинимальная куча, то есть для каждого элемента X ключ в родительском элементе X меньше (или равен) ключу в X, за исключением корневого узла (у которого нет родителя).
Как показано на рисунке, только левая сторона является кучей, а красный узел справа нарушает порядок кучи. Согласно упорядочению кучи, для нахождения наименьшего элемента требуется только константа O (1).
3. Основные операции с кучей
- вставлять
- верхний фильтр:Чтобы вставить элемент X, мы создали отверстие в следующем доступном месте.(Иначе это сломало бы структуру, а не полное бинарное дерево).Если этот элемент помещается в дыру без нарушения порядка кучи, вставка завершена, в противном случае родительский узел перемещается вниз к дыре, то есть дыра делает шаг в направлении корня.Продолжайте этот процесс, пока X не будет вставлен в полость. Такой процесс называется верхней фильтрацией.
На рисунке показан процесс вставки 18,Установив отверстие в следующей доступной позиции (структурное удовлетворение), обнаруженное как вставленное непосредственно, родительский узел переместится вниз, приняв отверстие. Продолжайте этот процесс, пока не встретите порядок в куче.Таким образом элементы вставляются в приоритетную очередь (кучу).
- Java реализует фильтрацию вверх
/**
* 插入到优先队列，维护堆序性
*
* @param x ：插入的元素
*/
public void insert(T x) {
if (null == x) {
return;
}
//扩容
if (currentSize == array.length - 1) {
enlargeArray(array.length * 2 + 1);
}
//上滤
int hole = ++currentSize;
for (array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2) {
array[hole] = array[hole / 2];
}
array[hole] = x;
}
/**
* 扩容方法
*
* @param newSize ：扩容后的容量，为原来的2倍+1
*/
private void enlargeArray(int newSize) {
T[] old = array;
array = (T[]) new Comparable[newSize];
System.arraycopy(old, 0, array, 0, old.length);
}
Операцию обмена можно использовать повторно для выполнения процесса верхней фильтрации, но если вставлен верхний слой фильтрации X, требуются 3d-назначения; таким образом, нам нужно только d+1 присвоений.
Если вставленный элемент является новым наименьшим элементом и, таким образом, фильтруется до корня, то время вставки равно O(logN). Но в среднем верхний фильтр отключается раньше.Было показано, что выполнение последовательных вставок требует в среднем 2,607 сравнений, поэтому в среднем операция вставки перемещает элементы вверх на 1,607 уровня.Количество загрузок всего на единицу меньше, чем количество вставок.
- deleteMin (удалить наименьший элемент)
- отфильтровать: Аналогично работе верхнего фильтра. Поскольку мы строим минимальную кучу, удаление минимального элемента означает удаление корневого узла, что разрушает структуру. такМы создаем дыру в корневом узле. Чтобы удовлетворить структуру, последний элемент X в куче должен быть перемещен в подходящую позицию. Если он может быть непосредственно помещен в дыру, удаление завершено (вообще невозможно); в противном случае меньший из левого и правого сыновей дыры перемещается в дыру, то есть дыра смещается на один слой вниз. Продолжайте делать это до тех пор, пока X не сможет быть помещен в полость.Таким образом, структура и порядок кучи могут быть удовлетворены. Этот процесс называется фильтрацией вниз.
как показано на рисунке:В корне устанавливается отверстие, и последний элемент помещается в отверстие, которое удовлетворило структуру; для того, чтобы удовлетворить порядок укладки, отверстие необходимо переместить вниз в подходящее положение.
Примечание: кучаПри реализации часто встречающаяся ошибкатолько четное количество элементов,То есть есть узел только с одним ребенком.такНеобходимо проверить существование правильного сына.
/**
* 删除最小元
* 若优先队列为空，抛出UnderflowException
*
* @return ：返回最小元
*/
public T deleteMin() {
if (isEmpty()) {
throw new UnderflowException();
}
T minItem = findMin();
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
/**
* 下滤方法
*
* @param hole ：从数组下标hole1开始下滤
*/
private void percolateDown(int hole) {
int child;
T tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child) {
//左儿子
child = hole * 2;
//判断右儿子是否存在
if (child != currentSize &&
array[child + 1].compareTo(array[child]) < 0) {
child++;
}
if (array[child].compareTo(tmp) < 0) {
array[hole] = array[child];
} else {
break;
}
}
array[hole] = tmp;
}
Наихудшая временная сложность этой операции — O(logN). В среднем элементы, помещенные в корень, фильтруются почти до нижнего слоя (то есть слоя, из которого они пришли), поэтому средняя временная сложность составляет O(logN).
4. Резюме
Очереди с приоритетами часто реализуются с использованием двоичных куч.Эта статья иллюстрирует две самые основные операции с двоичными кучами: вставка и удаление минимальных элементов. insert выполняется за O(1) постоянное время, а deleteMin выполняется за O(logN).Я считаю, что после прочтения вы можете посмотреть исходный код PriorityQueue в java. Сегодня я рассказал только о самых основных операциях с бинарной кучей, а некоторые дополнительные операции и анализ будут рассмотрены в следующий раз. Например, как доказать, что buildHeap является линейным? И применение приоритетной очереди и т.д.
Отказ от ответственности: Все изображения и тексты являются оригинальными, если они воспроизведены, пожалуйста, укажите источник. Если есть какие-либо ошибки, пожалуйста, помогите указать, добро пожаловать на обсуждение;