Поиск min/max движущегося окна в O (log (n))

Question

У меня есть это школьное задание, где мне нужно создать макс/мин-искатель из движущегося окна в O (log (n)). Присвоение дает подсказку использовать java-класс java.util.TreeMap или очереди в реализации. До сих пор мне удалось создать рабочий код, который работает в O (n), используя очереди. В соответствии с тем, что я сделал до сих пор с treeMap, но у меня проблемы с пониманием класса treeMap. Я просто не считаю нужным использовать инструменты. Теперь он удаляет самое большое значение, а не самое раннее. Я попытался также сопоставить значения с индексами, но тогда я не смог сравнить значения, чтобы найти самое большое значение.

import java.util.TreeMap._ 

class FastMaxMin[A <% Ordered[A]](windowSize: Int) { 
    val tree = new java.util.TreeMap[A,A]() 
    var size = 0 

    /** 
    * Every apply should insert new value to the moving window, removes the earliest 
    * one and returns (min, max) of the current window. 
    */ 

    def insert(value: A): (A, A) = { 
     if(size = windowSize){ 
     tree.pollLastEntry() 
     size-=1 
     } 
     tree.put(value, value) 
     size+=1 
     (tree.firstKey(), tree.lastKey() 
    } 
} 

Если бы кто-нибудь мог даже подтолкнуть меня вперед этой штукой, я был бы доволен.

Answer 1

У вас есть readTreeMap документация?

Red-Black tree Навигационная карта. Карта сортируется в соответствии с естественным порядком ее ключей или Компаратором, предоставленным при создании карты, в зависимости от того, какой конструктор используется.

Эта реализация обеспечивает гарантированную log (n) временную стоимость для операций containsKey, get, put и remove. Алгоритмы являются адаптацией к тем, которые применяются в работе Cormen, Leiserson и «Rivest's Introduction to Algorithms».

Так что это упорядоченная структура данных. Хотя он не говорит, вы можете предположить, что firstKey и lastKey являются постоянными или O (log N), поэтому вызов четырех из put, firstKey, lastKey и remove дает вам O (log N).

Для того, чтобы это сработало, вам нужно дать конструктору карты дерева подсказку, как сортировать ключи. У вас немного рассогласование между Scala, где вы запрашиваете неявный параметр преобразования A => Ordered[A] и конструктор TreeMap (который не знает этого параметра), поэтому он «использует естественный порядок своих ключей», что может или может быть неверным в вашем случае.

Если вы хотите, чтобы ключи были правильно отсортированы, вы должны либо убедиться, что A <: Comparable, либо указать явное Comparator.

Поскольку вы сохраняете то же значение, что и ключ и значение, и никогда не используете значение, вы можете сделать его также TreeMap[A, Unit], или действительно TreeSet. Вы также можете поменять java.util.TreeMap на подходящую коллекцию Scala, например collection.mutable.SortedSet. Это обеспечивает упорядочение с помощью экземпляра Ordering[A] (так называемый тип класса). Он имеет те же методы firstKey и lastKey.

---

Подсказка: Чтобы удалить старое значение как окно слайдов, нет ничего плохого в сохранении второй структуры данных, который имеет быстрое добавление и удаление первого или последний элемент. Ваш вопрос также упоминает эту структуру данных.