Правильная функциональная реализация на биномиальной куче

Question

Я читаю Binomial Heap в чисто функциональных структурах данных.

Реализация insTree функция меня сильно смутила. Вот набор кодов

datatype Tree = Node of int * Elem.T * Tree list

fun link (t1 as Node (r, x1, c1), t2 as Node (_, x2, c2)) = 
  if Elem.leq (x1, x2) then Node (r+1, x1, t2::c1)
  else Node (r+1, x2, t1::c2)

fun rank (Node (r, x, c)) = r

fun insTree (t, []) = [t]
  | insTree (t, ts as t' :: ts') =
      if rank t < rank t' then t::ts else insTree (link (t, t'), ts')

Мое замешательство лежит на insTree вот почему он не учитывает ситуацию с рангом т> ранг т '?

В if rank t < rank t' then t::ts else insTree (link (t, t'), ts'),

1. если ранг t меньше чем ранг t, то поместите t в кучу, без вопросов
2. остальное имеет два случая: равный и больший.
3. Для равных, да, мы можем связать два дерева (мы связываем только два дерева с одинаковым рангом), а затем попытаться вставить новое связанное дерево в кучу, без вопросов.
4. но даже более крупный случай будет таким же, как равный, почему? Даже если ранг t > ранг t', мы все еще связываем их?

---

редактировать

Я думал, что процесс inserting a binomial tree into a binomial heap должно быть так:

1. Мы получаем дерево т и кучу
2. В куче (фактически в списке) мы сравниваем ранг дерева t с каждым деревом в куче
3. Мы находим отсутствующий ранг (возрастающий порядок в куче), который соответствует рангу t, мы помещаем t в этот слот
4. Мы находим дерево в куче с таким же рангом, что и t, затем связываем два дерева и обрабатываем rank+1 новое дерево и попробуйте еще раз вставить новое дерево в кучу.

Итак, я считаю правильным fun insTree может быть так:

fun insTree (t, []) = [t]
      | insTree (t, ts as t' :: ts') =
          if rank t < rank t' then t::ts 
          else if rank t = rank t' then insTree (link (t, t'), ts')
          else t'::(insTree (t, ts'))

Answer 1

insTree - вспомогательная функция, которая не видна пользователю. Пользователь вызывает insert, который, в свою очередь, вызывает insTree с деревом ранга 0 и списком деревьев возрастающего ранга. У insTree есть инвариант, что ранг t равен <= ранг первого дерева в списке. Так что, если это не <, то это должно быть =.

Вы правы в том, что если бы insTree была общедоступной функцией общего назначения, а не частной функцией специального назначения, то ей пришлось бы иметь дело с отсутствующим случаем.

Answer 2

Важной деталью этого является то, что биноминальная куча - это не дерево, в котором есть k детей. Это дерево строго определено как

Биномиальное дерево порядка 0 является единственным узлом, а биномиальное дерево порядка n является одним узлом с биномиальными деревьями порядка 0, 1, 2, ..., n - 1 в качестве дочерних.

Этот ответ объясняет, почему функция вставки, которая необходима для построения биномиальной кучи, не управляет этими случаями (теоретически они не могут происходить). Возможно, предлагаемые вами случаи имеют смысл для операции слияния (но базовая реализация должна отличаться).