Статьи

Обзор очереди приоритетов

Июль 27, 2017

Очередь приоритета представляет собой несколько аналогичную структуру данных в очереди . Разница заключается в том, как элементы обрабатываются:

  • Стандартная очередь строго следует принципу FIFO (первым пришел-последним вышел).
  • Очередь с приоритетом не  соответствует принципу FIFO.

В очереди с приоритетами элементы удаляются из очереди в зависимости от их приоритета. Это означает, что:

Каждый элемент в очереди приоритетов должен иметь связанный с ним приоритет.

Как вы уже догадались, элемент с наивысшим приоритетом удаляется из очереди (исключается из очереди).

Но как определить приоритет элементов в очереди?

Определение приоритетов для элементов

По сути, у вас есть две альтернативы для определения приоритетов элементов в очереди. Вы также можете

  • Элементы заказа основаны на их естественном порядке.
  • Заказать элементы с помощью специального компаратора.

В этой статье мы сосредоточимся на том, как реализовать приоритетную очередь. Поэтому для простоты мы упорядочим элементы на основе их естественного порядка .

В нашем примере приоритетная очередь будет ограничена   int, поэтому естественное упорядочение вполне подойдет. Однако имейте в виду, что это только для демонстрационных целей.

Если вы хотите реализовать очередь с приоритетами в реальной жизни, вы, вероятно, захотите использовать непатентованные средства — или просто сделайте это, как любой другой разработчик, и используйте встроенный java.util.PriorityQueue.

Чтобы поддерживать реализацию нашего примера в соответствии со спецификацией Java, наименьший  элемент определяется как элемент с наивысшим приоритетом.

Название изображения

Операции с приоритетными очередями

Самый базовый набор операций для любой реализации очереди:

  •  enqueue — Вставка элемента в очередь.
  •  dequeue — Удаление элемента из очереди.
  •  isEmpty — Возвращение true, если очередь пуста.
  •  size — Возвращение размера / количества элементов в очереди.
  •  contains — Возвращение true, если очередь содержит данный элемент. 
  •  peek — Возврат переднего элемента очереди, не  удаляя его.

Обратите внимание, что реализация Java очереди с приоритетами использует разные имена для методов. В производственной среде я настоятельно рекомендую вам использовать реализацию очереди с приоритетами по умолчанию вместо того, чтобы «выращивать ее».

Реализация очереди приоритетов

Теперь давайте реализуем очередь неуниверсального приоритета в Java. Мы будем реализовывать одну операцию за раз, но сначала нам нужно решить, какую внутреннюю структуру данных  мы хотим использовать.

Массив прекрасно, так что мы будем катиться с этим. 

Для тех из вас, кто знаком с массивами, вы, вероятно, знаете, что массивы имеют фиксированный размер в Java. Наше решение этой проблемы состоит в том, что мы предоставим приватный метод   double(),  который «увеличивает» емкость массива.

Скелет кода для приоритетной очереди представлен ниже.

package priorityqueue;

public class PriorityQueue {

    private int[] innerArray;
    private int size;

    public PriorityQueue() {
        this.innerArray = new int[10];
        size = 0;
    }

    public void enqueue(int x) {

    }

    public int dequeue() {
        return 0;
    }

    public int peek() {
        return 0;
    }

    public boolean contains(int x) {
        return false;
    }

    public boolean isEmpty() {
        return false;
    }

    public int size() {
        return 0;
    }

    private void doubleArray() {

    }
}

Как видите, мы используем intмассив в качестве внутренней структуры данных и инициализируем его размер по умолчанию в конструкторе до 10. Мы также предоставляем приватную переменную size для отслеживания количества элементов.

Реализация Size, isEmpty и Peek

Реализация sizeи isEmptyметодов так же легко , как он получает. Следует помнить одну вещь: sizeпеременная используется, чтобы избежать цикла по массиву и считать «действительные» целые числа. В конструкторе всем индексам присвоено значение intсо значением 0.

public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

Как насчет peek? На самом деле это тоже довольно просто: если размер больше 0, мы возвращаем первый элемент. Если оно меньше нуля, мы бросаем . NoSuchElementException

public int peek() {
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");
        return innerArray[0];
    }

Реализация содержит

Пришло время для реализации ,  которая должна возвращать true, если очередь содержит предоставленный параметр. contains

Как мы должны это реализовать? Одним наивным способом было бы просто пройтись по массиву и вернуть true, если мы встретимся с указанным intв массиве.

Однако это не сработает! Что если пользователь предоставит нам 0? Как упоминалось ранее, массиву изначально присваивается значение intсо значением по умолчанию, которое равно нулю.

Другими словами: мы получим ложный положительный результат.

Решение? Только цикл по индексам, которые мы знаем,  содержит вставленные значения.

public boolean contains(int x) {
        // Check for empty.
        if(isEmpty())
            return false;
        // Looping through the positions which contains inserted values,
        // ignoring trailing default 0 values.
        for(int i = 0; i < size; i++) {
            // Comparing
            if(innerArray[i] == x)
                return true;
        }

        // None found
        return false;
    }

Реализация постановки и снятия с очереди

Во-первых, давайте подумаем о том, что мы хотим, если мы вставим / поставим в очередь элемент. Обратите внимание, что мы doubleArray пока игнорируем метод. Мы хотим, чтобы вставленные элементы были помещены в очередь в правильном положении в соответствии с их приоритетом.

Название изображения

Эта визуализация enqueue операции говорит нам о том, что нам придется сместить все элементы с более низким приоритетом на одну позицию вверх в массиве.

public void enqueue(int x) {
        // If it is empty, insert in front
        if (size == 0) {
            size++;
            innerArray[0] = x;
            return;
        }

        // If full, we'll have to double the array
        if (size() == innerArray.length)
            doubleArray();

        // Looping through
        int temp = x;
        for (int i = 0; i < size; i++) {
            // If priority is higher, ie. values is lower, we shift.
            if (x <= innerArray[i]) {
                int next;
                temp = innerArray[i];
                innerArray[i] = x;
                // Shifting
                while (i < size - 1) {
                    next = innerArray[i + 1];
                    innerArray[i + 1] = temp;
                    temp = next;
                    i++;
                }
                break;
            }
        }

        // Placing, increasing size.
        innerArray[size] = temp;
        size++;
    }

 Dequeueработает очень похожим образом.

Название изображения

public int dequeue() {
        // NoSuchElement
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");

        // Storing first int for return
        int retValue = innerArray[0];
        // Shifting all values downwards
        for (int i = 1; i < size; i++) {
            innerArray[i - 1] = innerArray[i];
        }

        innerArray[size - 1] = 0;
        size--;
        return retValue;
    }

Реализация doubleArray

Теперь осталось только реализовать метод, который удваивает массив, если мы превышаем исходный размер. Мы просто копируем содержимое массива в новый массив, который в два раза больше.

private void doubleArray() {
        int[] newArr = new int[innerArray.length * 2];

        for(int i = 0; i < innerArray.length; i++) {
            newArr[i] = innerArray[i];
        }

        innerArray = newArr;
    }

Полная реализация

Полная реализация может быть найдена ниже. Удачного кодирования!

package priorityqueue;

import java.util.NoSuchElementException;

public class PriorityQueue {

    private int[] innerArray;
    private int size;

    public PriorityQueue() {
        this.innerArray = new int[10];
        size = 0;
    }

    public void enqueue(int x) {
        // If it is empty, insert in front
        if (size == 0) {
            size++;
            innerArray[0] = x;
            return;
        }

        // If full, we'll have to double the array
        if (size() == innerArray.length)
            doubleArray();

        // Looping through
        int temp = x;
        for (int i = 0; i < size; i++) {
            // If priority is higher, ie. values is lower, we shift.
            if (x <= innerArray[i]) {
                int next;
                temp = innerArray[i];
                innerArray[i] = x;
                // Shifting
                while (i < size - 1) {
                    next = innerArray[i + 1];
                    innerArray[i + 1] = temp;
                    temp = next;
                    i++;
                }
                break;
            }
        }

        // Placing, increasing size.
        innerArray[size] = temp;
        size++;
    }

    public int dequeue() {
        // NoSuchElement
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");

        // Storing first int for return
        int retValue = innerArray[0];
        // Shifting all values downwards
        for (int i = 1; i < size; i++) {
            innerArray[i - 1] = innerArray[i];
        }

        innerArray[size - 1] = 0;
        size--;
        return retValue;
    }

    public int peek() {
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");
        return innerArray[0];
    }

    public boolean contains(int x) {
        // Check for empty.
        if (isEmpty())
            return false;
        // Looping through the positions which contains inserted values,
        // ignoring trailing default 0 values.
        for (int i = 0; i < size; i++) {
            // Comparing
            if (innerArray[i] == x)
                return true;
        }

        // None found
        return false;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private void doubleArray() {
        int[] newArr = new int[innerArray.length * 2];

        for(int i = 0; i < innerArray.length; i++) {
            newArr[i] = innerArray[i];
        }

        innerArray = newArr;
    }
}

 

63
Share: