Как в приоритетной очереди найти и удалить запись?

317
15 июня 2017, 05:04

Можно ли реализовать в данном примере поиск и удаление одной записи?

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

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
public class test {
    public static void main(String[] args) {
        //Компаратор
        Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
        add(customerPriorityQueue);
        poll(customerPriorityQueue);
    }
    //Класс компаратора
    public static Comparator<Customer> idComparator = new Comparator<Customer>(){
        @Override
        public int compare(Customer c1, Customer c2) {
            return (int) (c1.getId() - c2.getId());
        }
    };
    //Метод добавления элементов в очередь
    private static void add(Queue<Customer> customerPriorityQueue) {
        Random rand = new Random();
        for(int i=0; i<7; i++){
            int id = rand.nextInt(100);
            customerPriorityQueue.add(new Customer(id, "Name "+id));
        }
    }
    //Метод для обработки данных очереди
    private static void poll(Queue<Customer> customerPriorityQueue) {
        while(true){
            Customer cust = customerPriorityQueue.poll();
            if(cust == null) break;
            System.out.println("Обработка клиента с id=" + cust.getId() + " \\\\ " + cust.getName());
        }
    }
}
class Customer {
    private int id;
    private String name;
    public Customer(int i, String n){
        this.id=i;
        this.name=n;
    }
    public int getId() {
        return id;
    }
    public String getName() {
        return name;
    }
}
Answer 1

Полный ответ не пишу. Только идею.

  1. добавим в хранимую структуру флаг <удалено>, значение по умолчанию ложь
  2. Сделаем хеш-таблицу или что вам нравится вида <ключ> -> <структура>.
  3. Для удаления используя таблицу из пункта 2, найдём сам элемент и выставим флаг удалено.
  4. флаг должен либо игнорироваться при проверке на минимальность элемента (чтобы инвариант не нарушить) либо удалённый элемент может быть меньше не удалённого, но тогда нужно делать подъём в куче (кучу руками писать придётся).
  5. если верхний элемент кучи (очереди) удалён, то выталкиваем (удаляем) его.
  6. повторяем шаг 5.

Я думаю вы понимаете, что приоритетная очередь и куча это одно и тоже. Вам в любом случае придётся писать свою обёртку над стандартным классом (или кучи или очереди), над чем - дело вкуса, я бы предпочёл над кучей, чтобы не тянуть реализацию не нужных методов.

Сложность операции удаления - O(1) (если хеш контейнер, O(ln K) в противном случае). Остальные операции - O(ln K), где K - максимальное число элементов в очереди (зависит от реализации компаратора).

READ ALSO
Как привязать приложение к аккаунту Google?

Как привязать приложение к аккаунту Google?

Нужно привязать приложение к аккаунту Google, чтобы при смене девайса или на разных девайсах с одним аккаунтом все работалоКак это делается?...

486
Отслеживание нажатия клавиш в фоне

Отслеживание нажатия клавиш в фоне

Столкнулся с такой проблемойКак отследить нажатие клавиши в фоне

1274
Что конкретно нужно знать Android-разработчику? [требует правки]

Что конкретно нужно знать Android-разработчику? [требует правки]

Хочу стать Android-разработчикомЧто нужно знать для этого? Сейчас учу java SE

340