Следует ли объединять / объединять биномиальные кучи за один или два прохода?

Question

Реализация Okasaki в Purely Functional Data Structures (стр. 22) делает это двумя: один для объединения леса и один для распространения переносов. Это кажется мне более сложным для анализа и, вероятно, медленнее, чем однопроходная версия. Я что-то пропустил?

Реализация Окасаки:

Функтор BinomialHeap (Элемент:ORDERED):HEAP= структура структуры Elem= Тип данных элемента Дерево = Узел типа int*Elem.T* Тип списка дерева Куча = ссылка на список дерева (t1 как узел (r,x1,c1), t2 как узел (_,x2,c2))= если Elem.leq(x1,x2), то Node (r+1,x1,t2::c1)
    else Node (r+1,x2,t1::c2)
  fun insTree (t,[])=[t]
     |insTree (t,ts как t ':: ts') = если rank t 
Это кажется мне трудным для анализа, потому что вы должны доказать верхнюю границу стоимости распространения всех переносов (см. Ниже). Реализация нисходящего слияния, с которой я столкнулся, гораздо более очевидна: O(log n), где n - размер большей кучи:
функтор BinomialHeap (элемент:ORDERED):HEAP=
структура
  структура Элем = Элемент
  Тип данных Tree = Узел int*Elem.T* Список деревьев
  Тип Heap = Список деревьев
  забавный ранг (Node(r,_,_))=r
  забавная ссылка (t1 как узел (r,x1,c1), t2 как узел (_,x2,c2))=
    if Elem.leq(x1,x2)
    затем узел (r + 1, x1, t2:: c1)
    еще узел (r+1,x2,t1::c2)
  fun insTree (t,[])=[t]
     |insTree (t,ts as t'::ts')=
        если ранг t <ранг t ', то t:: ts, иначе insTree (ссылка (t, t'), ts ')
  забавная вставка (x, ts) = insTree (Node (0, x, []), ts)

  Веселое слияние (ts1, []) = ts1
     | Слияния ([], TS2) = TS2
     | объединить (ts1 как t1:: ts1 ', ts2 как t2:: ts2') =
        если ранг t1 <ранг t2, то t1:: merge (ts1 ', ts2)
        иначе, если ранг t2 <ранг t1, то t2:: слияние (ts1, ts2 ')
        остальное mwc (ссылка (t1, t2), ts1 ', ts2')
  (* mwc = объединить с переносом *)
  и mwc (c, ts1, []) = insTree (c, ts1)
     | mwc (c, [], ts2) = insTree (c, ts2)
     | mwc (c, ts1 как t1:: ts1 ', ts2 как t2:: ts2') =
        если ранг с <ранг t1
        тогда если ранг c <ранг t2, то c:: merge (ts1, ts2)
                  иначе mwc (ссылка (c, t2), ts1, ts2 ')
        остальное mwc (ссылка (c, t1), ts1 ', ts2)
конец
Доказательство того, что реализация Okasaki - O(log n): если перенос "дорогой" (требует одну или несколько ссылок), то он выдает ноль. Поэтому следующий дорогой перенос прекратится, когда он достигнет этой точки. Таким образом, общее количество ссылок, необходимых для распространения всех переносов, составляет не более общей длины двоичного представления перед распространением, которое ограничено сверху ceil (log n), где n - размер большей кучи.