Как можно реализовать std::make_heap при сравнении не более 3N?
Я заглянул в стандарт C++0x и обнаружил, что make_heap должен выполнять не более 3*N сравнений.
Т.е. накапливать неупорядоченную коллекцию можно в O(N)
/* @brief Construct a heap over a range using comparison functor.
Почему это?
Источник не дает мне никаких подсказок (g++ 4.4.3)
While (true) + __parent == 0 - это не подсказки, а предположение о поведении O(N)
template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
const _DistanceType __len = __last - __first;
_DistanceType __parent = (__len - 2) / 2;
while (true)
{
_ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
__comp);
if (__parent == 0)
return;
__parent--;
}
}
__adjust_heap выглядит как метод log N:
while ( __secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
Для меня это болотный стандартный журнал.
template<typename _RandomAccessIterator, typename _Distance,
typename _Tp, typename _Compare>
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __value, _Compare __comp)
{
const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
if (__comp(*(__first + __secondChild),
*(__first + (__secondChild - 1))))
__secondChild--;
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
__holeIndex = __secondChild;
}
if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
{
__secondChild = 2 * (__secondChild + 1);
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
+ (__secondChild - 1)));
__holeIndex = __secondChild - 1;
}
std::__push_heap(__first, __holeIndex, __topIndex,
_GLIBCXX_MOVE(__value), __comp);
}
Любые подсказки, почему это O <= 3N, будут оценены.
РЕДАКТИРОВАТЬ:
Результаты эксперимента:
Эта фактическая реализация использует
- <2N сравнений для куч кучи
- <1,5 Н для куч кучи в обратном порядке.
2 ответа
Двоичная куча по n элементам может быть создана за O(n) время с использованием умного алгоритма и умного анализа. В дальнейшем я просто расскажу о том, как это работает, предполагая, что у вас есть явные узлы и явные левый и правый дочерние указатели, но этот анализ все еще остается в силе, когда вы сжимаете его в массив.
Алгоритм работает следующим образом. Начнем с того, что берем около половины узлов и рассматриваем их как синглтон-максимальные кучи - поскольку существует только один элемент, дерево, содержащее только этот элемент, должно автоматически быть максимальной-кучей. Теперь возьмите эти деревья и соедините их друг с другом. Для каждой пары деревьев возьмите одно из значений, которое вы еще не использовали, и выполните следующий алгоритм:
Сделайте новый узел корнем кучи, чтобы его левый и правый дочерние указатели ссылались на две максимальные кучи.
В то время как у этого узла есть дочерний элемент, который больше, чем он, поменяйте его с его более крупным дочерним узлом
Я утверждаю, что эта процедура в итоге создает новую максимальную кучу, содержащую элементы двух входных максимальных куч, и это происходит за время O(h), где h - высота двух куч. Доказательством является индукция высоты кучи. В качестве базового случая, если подголовки имеют нулевой размер, тогда алгоритм немедленно завершается с помощью одиночной максимальной кучи, и это происходит за время O(1). Для индуктивного шага предположим, что для некоторого h эта процедура работает с любыми подпучками размера h и рассмотрим, что происходит, когда вы выполняете его для двух куч размера h + 1. Когда мы добавляем новый корень, чтобы объединить два поддерева размера h + 1, есть три варианта:
Новый корень больше, чем корни обоих поддеревьев. Тогда в этом случае мы имеем новую максимальную кучу, так как корень больше, чем любой из узлов в любом поддереве (транзитивностью)
Новый корень больше одного потомка и меньше другого. Затем мы меняем корень с большим дочерним элементом и рекурсивно выполняем эту процедуру снова, используя старый корень и два дочерних дерева, каждое из которых имеет высоту h. По индуктивной гипотезе это означает, что поддерево, в которое мы обменивались, теперь является максимальной кучей. Таким образом, общая куча - это максимальная куча, поскольку новый корень больше, чем все в поддереве, с которым мы обменивались (так как он больше, чем добавленный нами узел, и уже был больше, чем все в этом поддереве), и он также больше, чем все в другом поддереве (так как он больше, чем корень, а корень был больше, чем все в другом поддереве).
Новый корень меньше, чем оба его потомка. Затем, используя слегка измененную версию приведенного выше анализа, мы можем показать, что результирующее дерево действительно является кучей.
Более того, поскольку на каждом шаге высота дочерних куч уменьшается на единицу, общее время выполнения для этого алгоритма должно быть O(h).
На данный момент у нас есть простой алгоритм для создания кучи:
- Возьмите около половины узлов и создайте одноэлементные кучи. (Вы можете явно рассчитать, сколько узлов здесь потребуется, но это примерно половина).
- Соедините эти кучи, затем объедините их, используя один из неиспользуемых узлов и описанную выше процедуру.
- Повторяйте шаг 2, пока не останется одна куча.
Поскольку на каждом шаге мы знаем, что кучи, которые у нас есть, являются действительными максимальными кучами, в конечном итоге это приводит к действительной общей максимальной куче. Если мы хорошо разберемся, как мы выбираем, сколько синглтон-куч нужно создать, это в конечном итоге также приведет к созданию полного двоичного дерева.
Однако, похоже, что это должно выполняться за O(n lg n), поскольку мы выполняем O(n) слияний, каждое из которых выполняется за O(h), и в худшем случае высота деревьев, которые мы объединяем является O (LG N). Но эта граница не является жесткой, и мы можем добиться большего, если будем более точными в анализе.
В частности, давайте подумаем о том, насколько глубоки все деревья, которые мы объединяем. Около половины кучи имеют нулевую глубину, затем половина того, что осталось, имеет глубину один, затем половина того, что осталось, имеет глубину два, и т. Д. Если мы суммируем это, мы получим сумму
0 * n / 2 + 1 * n / 4 + 2 * n / 8 +... + nk / (2 k) = Σ k = 0 ⌈log n⌉ (nk / 2 k) = n Σ k = 0 ⌈ log n⌉ (k / 2 k + 1)
Это верхний предел количества сделанных свопов. Каждый своп требует не более двух сравнений. Поэтому, если мы умножим вышеупомянутую сумму на два, мы получим следующее суммирование, которое ограничивает число сделанных перестановок:
n Σ k = 0 ∞ (k / 2 k)
Суммирование здесь является суммированием 0/2 0 + 1/2 1 + 2/2 2 + 3/2 3 +.... Это известное суммирование, которое можно оценить несколькими различными способами. Один из способов оценить это приведен в этих слайдах лекций, слайды 45-47. В итоге получается ровно 2n, что означает, что количество сравнений, которые в итоге будут сделаны, определенно ограничено сверху 3n.
Надеюсь это поможет!
@templatetypedef уже дал хороший ответ, почему асимптотическое время выполнения build_heap является O (n). Существует также доказательство в главе 6 CLRS, 2-е издание.
Что касается того, почему стандарт C++ требует, чтобы использовалось не более 3n сравнений:
Из моих экспериментов (см. Код ниже) оказалось, что на самом деле требуется менее 2n сравнений. На самом деле, эти лекционные заметки содержат доказательство того, что build_heap использует только 2(n-⌈log n⌉) сравнения.
Оценка из стандарта кажется более щедрой, чем требуется.
def parent(i):
return i/2
def left(i):
return 2*i
def right(i):
return 2*i+1
def heapify_cost(n, i):
most = 0
if left(i) <= n:
most = 1 + heapify_cost(n, left(i))
if right(i) <= n:
most = 1 + max(most, heapify_cost(n, right(i)))
return most
def build_heap_cost(n):
return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))
Некоторые результаты:
n 10 20 50 100 1000 10000
build_heap_cost(n) 9 26 83 180 1967 19960