Структура данных, которая всегда хранит n-лучшие элементы - PullRequest
Новая
       16

Структура данных, которая всегда хранит n-лучшие элементы

8 голосов
/ 19 февраля 2009

Мне нужна структура данных, которая всегда содержит n самых больших элементов, вставленных до сих пор (в произвольном порядке).

Итак, если n равно 3, у нас может быть следующий сеанс, где я вставлю несколько чисел, и содержимое контейнера изменится: 

[]  // now insert 1
[1] // now insert 0
[1,0] // now insert 4
[1,0,4] // now insert 3
[1,4,3] // now insert 0
[1,4,3] // now insert 3
[4,3,3]

Вы поняли идею. Как называется структура данных? Какой лучший способ реализовать это? Или это в какой-то библиотеке?

Я думаю использовать контейнер, который имеет priority_queue для своих элементов (делегирование), который использует обратное сравнение, поэтому pop удалит наименьший элемент. Таким образом, функция insert сначала проверяет, больше ли новый элемент для вставки, чем самый маленький. Если это так, мы выбрасываем это наименьшее и выталкиваем новый элемент.

(Я имею в виду реализацию C++, но вопрос, тем не менее, не зависит от языка.)

Ответы [ 8 ]

13 голосов
/ 19 февраля 2009

Конкретная структура данных, которую вы хотите, это, вероятно, неявная куча . Необработанная структура данных - это просто массив; для удобства, скажем, что это N = 2 ^ n элементов по размеру, и вы хотите сохранить самые большие элементы N-1.

Идея состоит в том, чтобы рассматривать массив (назовите его A) как полное двоичное дерево глубины n:

  • игнорировать A [0]; трактовать A [1] как корневой узел
  • для каждого узла A [k], потомками являются A [2 * k] и A [2 * k + 1]
  • узлы A [N / 2..N-1] являются листьями

Чтобы дерево было «кучей», вам нужно убедиться, что каждый узел меньше (или равен) его дочерним элементам. Это называется «состояние кучи»:

  • A [k]
  • A [k]

Чтобы использовать кучу для поддержания наибольших N элементов:

По сути, это заставит любой замещающий элемент «фильтровать» дерево, пока оно не достигнет своего естественного места. Это займет не более n = log2 (N) шагов, и это очень хорошо. Кроме того, неявная форма дерева обеспечивает очень быструю реализацию; существующие библиотеки с ограниченными приоритетами, скорее всего, будут использовать неявную кучу.

5 голосов
/ 19 февраля 2009

В Java вы можете использовать реализованный SortedSet, например, с помощью TreeSet. После каждой вставки проверяйте, не слишком ли большой набор, если да, удалите последний элемент.

Это достаточно эффективно, я успешно использовал его для решения нескольких задач Project Euler.

4 голосов
/ 19 февраля 2009

Priority_queue - самая близкая вещь в C ++ с STL. Вы можете поместить его в другой класс, чтобы создать собственную реализацию, которая автоматически подрезает размер.

Не зависит от языка (хотя, возможно, не безопасно для фрагментирования памяти):

  1. Вставить данные
  2. Сортировка
  3. Удалить все после n-го элемента

std :: priority_queue делает для вас шаг 2.

2 голосов
/ 19 февраля 2009

A очередь с ограниченным приоритетом , я думаю ... В стандартной библиотеке Java есть нечто подобное. РЕДАКТИРОВАТЬ : он называется LinkedBlockingQueue. Я не уверен, что в C ++ STL есть что-то похожее.

1 голос
/ 19 февраля 2009

Разве нельзя просто взять первые n элементов из отсортированной коллекции?

0 голосов
/ 28 сентября 2018

В Pyhton используйте heapq. Создайте вокруг него маленькую обертку, примерно так: 

class TopN_Queue:
    def __init__(self, n):
        self.max_sz = n
        self.data = []

    def add(self, x):
        if len(self.data) == self.max_sz:
            heapq.heappushpop(self.data, x)
        else:
            heapq.heappush(self.data, x)

...

0 голосов
/ 05 января 2013

Создайте минимальную кучу, также сохраните счетчик.

Всякий раз, когда счетчик достигнут; экстракт-мин.

Вы можете сделать это в: O (1) insert, get-min и O (log log n) extract-min. [1] В качестве альтернативы вы можете сделать это с O (log n) insert и O (1) для другие упомянутые операции. [2]

[1] М. Торуп, «Очереди с целочисленными приоритетами с ключом уменьшения в постоянное время и проблема кратчайших путей из одного источника», в материалах тридцать пятого ежегодного симпозиума ACM по теории вычислений, Нью-Йорк, Нью-Йорк, США , 2003, с. 149–158.

[2] Г. С. Бродал, Г. Лагогианнис, К. Макрис, А. Цакалидис, К. Цихлас, "Оптимальные деревья поиска пальца в машине указателя", J. Comput. Сист. Sci., Vol. 67, нет. 2, с. 381–418, сентябрь 2003 г.

0 голосов
/ 21 ноября 2012

да, вы можете поддерживать минимальный размер головы N затем вы сравниваете новый элемент с корневым элементом в каждой вставке вставьте корень и вставьте элемент, если он «больше», чем корень в итоге вы получите N самых больших предметов

...