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

11

Приведите следующую проблему:

"Храните самые большие 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++
}
Вы можете использовать сбалансированное дерево поиска, такое как AVL или подобное En.wikipedia.org / вики / AVL_tree). Но решение на основе кучи является более естественным. Yves Daoust

Ваш Ответ

2   ответа
37

Куча максимального размера 5000.

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

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

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

@ redzedi Он будет заменен, когда придет следующий номер. Предположим, у вас есть куча размером 5000, с 1 вверху, а затем с 5. Он проверяет, больше ли 5, чем наименьший элемент (1) - он делает, поэтому 1 выталкивается, а вместо него вставляется 5. Помните, что это минимальная куча, поэтому 1 - это «голова». amit
+ 1 для алгоритма выбора. Просто хочу добавить: STL C ++ имеет реализацию для этого. Не уверен насчет Java, хотя. Однако этот метод автономных вычислений требует сложности O (n). nhahtdh
Отличное замечание об алгоритме выбора. OTOH это требует O (n) памяти. valdo
Вы можете использовать алгоритм выбора, чтобы найти верхние k элементов, но использовать только O (k) память, храня массив из 2k элементов. Каждый раз, когда вы заполняете массив, используйте алгоритм выбора, чтобы отбросить низшее k. Это работает с получением O (n) времени независимо от значения k, так как вы выполняете O (n / k) алгоритмы выбора, каждый из которых занимает время O (k). Он также использует только O (k) память. templatetypedef
@ amit в этом подходе, скажем, мы получаем 1 из потока в начало (давайте предположим, что поток имеет только натуральные числа), затем он переходит к вершине минимальной кучи и остается там и один раз размер кучи (5000) Достигнута, больше не будет замен для остальной части потока, поэтому ответ может быть неправильным в том смысле, что это не первые 5000 чисел. redzedi
1

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

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

Похожие вопросы