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

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

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

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

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

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

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

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++
}

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

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