Храните самые большие 5000 номеров из потока номеров

Учитывая следующую проблему:

"Сохранение 5000 самых больших номеров из потока номеров"

Решение, которое приходит на ум, — это двоичное дерево поиска, поддерживающее подсчет количества узлов в дереве и ссылку на наименьший узел, когда количество достигает 5000. Когда количество достигает 5000, каждое новое добавляемое число можно сравнить с самый маленький элемент в дереве. Если больше, можно добавить новое число, затем удалить наименьшее и вычислить новое наименьшее (что должно быть очень просто, уже имея предыдущее наименьшее).

Меня беспокоит это решение, потому что бинарное дерево, естественно, будет искажено (поскольку я удаляю только одну сторону).

Есть ли способ решить эту проблему, который не приведет к созданию сильно перекошенного дерева?

Если кому-то это нужно, я включил псевдокод для своего решения ниже:

process(number)
{
  if (count == 5000 && number > smallest.Value)
  {
    addNode( root, number)
    smallest = deleteNodeAndGetNewSmallest ( root, smallest)
  }
}

deleteNodeAndGetNewSmallest( lastSmallest)
{
  if ( lastSmallest has parent)
  {
    if ( lastSmallest has right child)
    {
      smallest = getMin(lastSmallest.right)
      lastSmallest.parent.right = lastSmallest.right
    }
    else
    {
      smallest = lastSmallest.parent
    }
  }
  else 
  {
    smallest = getMin(lastSmallest.right)
    root = lastSmallest.right
  }
  count--
  return smallest
}

getMin( node)
{
  if (node has left)
    return getMin(node.left)
  else
    return node
}

add(number)
{
  //standard implementation of add for BST
  count++
}

algorithm binary-search-tree
person Rich    schedule 25.05.2012    source источник
comment
Вы можете использовать сбалансированное дерево поиска, такое как AVL или подобное (en.wikipedia.org/wiki/AVL_tree). Но решение на основе кучи более естественно.   -  person Yves Daoust    schedule 13.09.2015

Ответы (2)


arrow_upward
38
arrow_downward

Простейшим решением для этого является поддержание минимальной кучи максимального размера 5000.

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

Это решение имеет сложность O(nlogk), где n — количество элементов, а k — количество необходимых вам элементов (5000 в вашем случае).

Это можно сделать и в O(n) с помощью алгоритма выбора - сохранить все элементы, а затем найти 5001-й самый большой элемент и вернуть все, что больше его. Но это сложнее реализовать и для ввода разумного размера - может быть, не лучше. Кроме того, если поток содержит дубликаты, требуется дополнительная обработка.

person amit    schedule 25.05.2012
comment
+1 за алгоритм выбора. Просто хочу добавить: STL C++ имеет реализацию для этого. А вот насчет Java не уверен. Однако этот метод офлайн-вычислений требует пространственной сложности O(n). - person nhahtdh; 25.05.2012
comment
Отличное замечание об алгоритме выбора. OTOH требует O(n) памяти. - person valdo; 14.07.2012
comment
Вы можете использовать алгоритм выбора, чтобы найти верхние k элементов, но использовать только O (k) памяти, сохраняя массив из 2k элементов. Каждый раз, когда вы заполняете массив, используйте алгоритм выбора, чтобы отбрасывать наименьшее значение k. Это требует времени O (n) независимо от значения k, поскольку вы выполняете алгоритмы выбора O (n/k), каждый из которых занимает время O (k). Он также использует только память O(k). - person templatetypedef; 24.09.2012
comment
@amit в этом подходе позволяет сказать, что мы получаем 1 из потока к началу (давайте предположим, что поток состоит только из натуральных чисел), затем он переходит к вершине минимальной кучи и остается там, и когда размер кучи (5000) равен достигнут не будет больше замен для остального потока, поэтому ответ может быть неверным в том смысле, что это не первые 5000 номеров. - person redzedi; 30.01.2015
comment
@redzedi Он будет заменен, когда придет следующее число. Предположим, у вас есть куча размером 5000, с 1 вверху, затем идет 5. Он проверяет, больше ли 5 ​​наименьшего элемента (1) — да, поэтому 1 выталкивается, а вместо него вставляется 5. Помните, что это минимальная куча, поэтому 1 — это голова. - person amit; 30.01.2015

arrow_upward
1
arrow_downward

Используйте очередь с (минимальным) приоритетом. Добавляйте каждый входящий элемент в очередь и, когда размер достигает 5000, удаляйте минимальный (верхний) элемент каждый раз, когда вы добавляете входящий элемент. Очередь будет содержать 5000 самых больших элементов, и когда ввод прекратится, просто удалите содержимое. Этот MinPQ также называется кучей, но это перегруженный термин. Вставки и удаления занимают около log2(N). Когда N достигает максимального значения 5000, это будет чуть более чем в 12 [log2(4096) = 12] раз больше количества обрабатываемых вами элементов.

Отличным источником информации являются «Алгоритмы» (4-е издание) Роберта Седжвика и Кевина Уэйна. На сайте coursera.org есть отличный МООК, основанный на этом тексте.

person user1295785    schedule 01.11.2013