Этот вопрос был удален сразу после того, как он был первоначально опубликован, потому что ОП не была заранее осведомлена о том, что она задала домашнее задание . Поскольку срок выполнения задания уже истек, я решил восстановить этот ответ.
Я не гуру Пролога, но я немного подумал над вашим вопросом. Я думаю, heap1/1 легче реализовать, чем heap2/1, потому что его «древовидная структура» более очевидна. Фактически, я буду реализовывать heap1/1, после чего я буду реализовывать heap2/1 в терминах heap1/1.
Реализация дерева: heap1/1
Дерево empty представляет собой двоичную кучу . Что касается node(K, L, R), то это куча, если:
L и R - это кучи. - Если
L и / или R не empty, то их ключ меньше или равен K.
- Если
L имеет глубину d , то R имеет глубину d или d - 1 .
Итак, что нужно сделать, это проверить, удовлетворяет ли данное двоичное дерево этим свойствам.
Учитывая node, нам нужно пройти его, чтобы узнать глубину дерева, которое он представляет. Следовательно, мы определим heap/1 в терминах предиката heap/2, в котором вторым аргументом является глубина дерева. В конце концов, нас не волнует фактическая глубина 1055 *, поэтому мы определяем:
heap1(H) :- heap1(H, _).
Так что насчет heap/2? Базовый случай - empty, то есть куча с глубиной 0 (или 1, но это не имеет значения для наших целей). Таким образом:
heap1(empty, 0).
Для node(K, L, R) нам придется возвращаться. Нам нужно протестировать свойства кучи, описанные выше, и рассчитать глубину дерева H. Таким образом:
heap1(empty, 0).
heap1(node(K, L, R), H) :-
heap1(L, LH), heap1(R, RH),
(L = node(LK, _, _) *-> K @>= LK; true),
(R = node(RK, _, _) *-> K @>= RK; true),
(LH is RH; LH is RH + 1), H is LH + 1.
В этом коде используется мягкая резка SWI-Prolog (*->)/2. Этот механизм используется для проверки того, являются ли поддеревья непустыми, и, если это так, для проверки того, что их ключ меньше или равен K (используя (@>=)/2). Предикат true/0 соответствует ситуации, в которой одно из поддеревьев является пустым. (is)/2 используется для сравнения глубин поддеревьев и расчета глубины всего дерева.
Реализация списка: heap2/1
Я предполагаю, что heap2/1 должен проверять, является ли его единственный аргумент списком, представляющим кучу, сохраненную в виде массива (или Ahnentafel list ). Если это так, то, принимая список с нулевым индексом, дочерние элементы узла с индексом i находятся по индексам 2i + 1 и 2i + 2 .
В результате родительский узел не обязательно хранится рядом с его дочерними узлами. Более конкретно, в позиции i в списке нам нужно пропустить i или i + 1 мест, чтобы достичь ключей поддеревьев. Мы определим предикат skipn/3, который поможет нам в этом:
skipn(N, L, E) :- (length(F, N), append(F, E, L)) *-> true; E = [].
skipn(N, L, E) завершается успешно, если E равно L после того, как первые N элементы L были удалены или , если E - пустой список, а длина L не больше N. Эта реализация использует length/2, append/3 и снова (*->)/2 и true/0.
Далее: определение heap2/1. Мы снова вызовем вспомогательный предикат, на этот раз heap2/3. heap2(H, N, T) завершается успешно, если список H, глава которого находится в позиции N возможно большего списка, может быть преобразован в двоичное дерево T. heap2/1 вызовет heap2/3 с начальным индексом 0 и проверит, что результирующее двоичное дерево фактически является кучей. Таким образом:
heap2(H) :- heap2(H, 0, T), heap1(T).
Хорошо, мы почти на месте. В позиции N индекс LI корня левого поддерева равен 2 * N + 1. Аналогично RI = 2 * N + 2 является индексом корня правого поддерева. Поскольку в позиции N уже N элементы списка были пропущены, для достижения индексов LI и RI, соответственно, необходимо пропустить только элементы LI - N и RI - N. Таким образом:
heap2([], _, empty).
heap2([H|T], N, node(H, L, R)) :-
LI is 2 * N + 1, RI is 2 * N + 2,
LS is LI - N, RS is RI - N,
skipn(LS, [H|T], LT), skipn(RS, [H|T], RT),
heap2(LT, LI, L), heap2(RT, RI, R).