Как реализовать универсальный PriorityQueue с базовыми методами в Java?
Мне нужно реализовать пользовательскую очередь приоритетов без использования формы PriorityQueue Java.Util... У меня есть три основных метода: вставить, удалить и очистить. Все операции должны выполняться за постоянное время O (log n). Как я могу сделать это? Какие алгоритмы я должен использовать для этих операций? И, наконец, какой тип контейнера следует использовать для хранения общих значений?
Это то, что я сделал до сих пор...
public class PriorityQueue<E extends Comparable<? super E>> implements Comparable {
private Stack<E> queue = new Stack<>();
private int size;
public PriorityQueue(int size) {
this.size = size;
}
public PriorityQueue() {
size = 50000;
}
public void insert(E value) {
if (value == null) {
throw new NullPointerException();
}
//how can I insert a value and what container should I use ?
}
public void remove() {
//remove largest
}
public int compareTo(Object o) {
if (o != null && o instanceof PriorityQueue) {
PriorityQueue anotherQueue = (PriorityQueue) o;
return this.size - anotherQueue.size;
} else {
throw new ClassCastException();
}
}
}
не очень.. но помощь будет принята с благодарностью!
1 ответ
Я вижу, ваша операция удаления занимает самый большой элемент. Похоже, "Max Heap" подойдет вашим целям.
Здесь я использовал maxHeap, чтобы разместить элементы в отсортированном порядке, и эта куча реализована с использованием массива.
max_size - это размер массива, а size - это количество элементов, которые в настоящее время хранятся в массиве.
- offer() - вставьте элемент в конечную позицию и вызовите метод shiftUp().
- poll() - для этого верните первый элемент массива. Затем замените первый элемент массива одним из его листьев. Затем вызовите метод shiftDown() для первого элемента. Первый элемент в массиве всегда будет иметь наивысший приоритет.
- peek() - здесь мы просто возвращаем первый элемент массива. Мы его не снимаем.
Есть еще два метода, которые мне не удалось реализовать в случае универсального массива. Если бы это был массив целых чисел, проблем не было бы. Эти два метода -
- remove(E e) - удалить элемент из очереди. Для этого мне нужно было изменить приоритет e на бесконечность, а затем вызвать метод shiftUp() для e. После этого мне просто нужно вызвать метод poll().
Но я не смог найти, как изменить приоритет универсального элемента на бесконечность. Если бы это было целое число, я бы просто заменил элемент в резервном массиве на Integer.MAX_VALUE.
- replace(E e1, E e2) - Здесь мне просто нужно удалить элемент e1 и вставить элемент e2. Поскольку этот метод вызывает метод remove(), я не смог его реализовать.
_
import java.util.Comparator;
public class PriorityQueueUsingHeap<E>
{
private int size;
private Object H[];
public PriorityQueueUsingHeap(int max_size)
{
H = new Object[max_size];
}
private Comparator<E> comparator;
public PriorityQueueUsingHeap(int max_size, Comparator<E> comparator)
{
this.comparator = comparator;
H = new Object[max_size];
}
private E parent(int i)
{
return (E) H[(i - 1) / 2];
}
private E left(int i)
{
return (E) H[2 * i + 1];
}
private E right(int i)
{
return (E) H[2 * i + 2];
}
private boolean greaterThanOrEqualTo(E e1, E e2) // return e1>=e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) >= 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) >= 0;
}
}
private boolean lessThan(E e1, E e2) // return e1<e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) < 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) < 0;
}
}
private boolean lessThanOrEqualTo(E e1, E e2) // return e1<=e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) <= 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) <= 0;
}
}
private boolean greaterThan(E e1, E e2) // return e1>e2
{
if (comparator != null)
{
return comparator.compare(e1, e2) > 0;
}
else
{
return ((Comparable<E>) e1).compareTo(e2) > 0;
}
}
private void swap(int i1, int i2)
{
E temp = get(i1);
H[i1] = H[i2];
H[i2] = temp;
}
private E get(int i)
{
return (E) H[i];
}
private void shiftUp(int i)
{
while (i > 0 & greaterThanOrEqualTo(get(i), parent(i)))
{
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
private void shiftDown(int i)
{
int max_index = i;
if ((2 * i + 1) <= size-1 && lessThan(get(max_index), left(i)))
max_index = 2 * i + 1;
if (((2 * i + 2) <= size-1) && (lessThan(get(max_index), right(i))))
max_index = 2 * i + 2;
if (i != max_index)
{
swap(i, max_index);
shiftDown(max_index);
}
}
public void offer(E data)
{
if(size == H.length)
System.out.println("Queue is full");
else
{
H[size] = (E) data;
shiftUp(size);
size++;
}
}
public E peek()
{
return get(0);
}
public E poll()
{
if(size==0)
{
System.out.println("Queue is empty");
return null;
}
else
{
E result = get(0);
H[0] = H[size-1];
size--;
shiftDown(0);
return result;
}
}
public E remove(E e)
{
// Logic
return e;
}
public void replace(E e1, E e2)
{
offer(e2);
remove(e1);
}
}
Вот основной класс для того же -
public class Main_PriorityQueueUsingHeap
{
public static void main(String[] args)
{
PriorityQueueUsingHeap<Integer> q1 = new PriorityQueueUsingHeap<>(10);
for (int i = 0; i < 5; i++)
{
q1.offer(i);
}
for (int i = 0; i < 5; i++)
{
System.out.print(q1.poll() + " ");
}
System.out.println();
PriorityQueueUsingHeap<String> q2 = new PriorityQueueUsingHeap<>(10);
q2.offer("Jatin");
q2.offer("Ashvini");
q2.offer("Ram");
q2.offer("Mahesh");
q2.offer("Kamal");
for (int i = 0; i < 5; i++)
{
System.out.print(q2.poll() + " ");
}
System.out.println();
PriorityQueueUsingHeap<String> q3 = new PriorityQueueUsingHeap<>(10,
(s1, s2) -> {
return (s1.length() != s2.length()) ? s1.length() - s2.length() : s1.compareTo(s2);
});
q3.offer("Jatin");
q3.offer("Ashvini");
q3.offer("Ram");
q3.offer("Mahesh");
q3.offer("Kamal");
for (int i = 0; i < 5; i++)
{
System.out.print(q3.poll() + " ");
}
System.out.println();
PriorityQueueUsingHeap<Integer> q4 = new PriorityQueueUsingHeap<>(10);
q4.offer(12);
q4.offer(2);
q4.offer(42);
q4.offer(62);
q4.offer(12);
for (int i = 0; i < 5; i++)
{
System.out.print(q4.poll() + " ");
}
}
}
И вот результат -
4 3 2 1 0
Ram Mahesh Kamal Jatin Ashvini
Ashvini Mahesh Kamal Jatin Ram
62 42 12 12 2
Пояснение к основному классу - я создал 4 очереди приоритета и сделал следующее:
- q1: Общая очередь целых чисел. Добавил целые числа от 0 до 4, а затем опросил элементы один за другим. Выходные данные показывают, что каждый из них пришел в порядке убывания их приоритета (чем больше число, тем выше его приоритет).
- q2: Общая очередь строки без заданного компаратора. Следовательно, две строки будут сравниваться на основе метода compareTo(E e), присутствующего в интерфейсе Comparable. Вывод сортируется в лексикографическом порядке.
- q3: Общая очередь строки с компаратором. Этот компаратор сравнивает длину двух строк, и если они одинаковы, строки сортируются в лексикографическом порядке.
- q4: Общая очередь целых чисел. Добавлены некоторые случайные числа, и при опросе одно за другим все они пришли в порядке убывания их приоритета. Поскольку компаратор не передается, приоритет был определен на основе метода compareTo(E e).