2

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

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

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;
    }
}
9
  • ответ на ваш вопрос - да, можно. использутйет метод remove или removeIf 13 июн 2017 в 10:44
  • @MikhailVaysman Я не заметил. А поиск?
    – aaa
    13 июн 2017 в 10:48
  • зачем вам нужно что-то искать в очереди? 13 июн 2017 в 10:50
  • @MikhailVaysman Задание такое
    – aaa
    13 июн 2017 в 10:51
  • 2
    и кстати зря вопрос минусовали, вполне нормальный вопрос.
    – pavel
    13 июн 2017 в 11:12

1 ответ 1

2

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

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

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

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

6
  • каким образом поиск занимает O(lnK), или у вас там сбалансированное бинарное дерево вместо кучи ?
    – Artem
    13 июн 2017 в 12:04
  • @ArtemKonovalov а что бывает не сбалансированная куча?) А если серьёзно куча - почти полное двоичное дерево. Там только нижний слой может быть не заполнен.
    – pavel
    13 июн 2017 в 12:08
  • заметьте я не говорил про сбалансированную кучу, я написал про бинарное дерево. А куча это совсем не дерево, у нее другой инвариант. И найти в ней элемент за логарифм не представляется возможным.
    – Artem
    13 июн 2017 в 12:11
  • @ArtemKonovalov перечитайте пункт 2. Там вообще 1 операция будет.
    – pavel
    13 июн 2017 в 12:14
  • чем ваш вариант лучше использования TreeMap ?
    – Artem
    13 июн 2017 в 12:26

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.