#prolog #heap
#пролог #куча
Вопрос:
Я тестирую свой heapify в prolog, но он работает не так, как я ожидал. В частности, я думаю, что в нем отсутствуют некоторые элементы, и он не генерирует правильную кучу.
min_heapify(H, P) :- heap_has_size(H, S), P = S, !.
min_heapify(H, P) :-
R is (2*P) 1,
heap_has_size(H, S), R =< S,
heap_entry(H, P, K1, _V1),
heap_entry(H, R, K2, _V2),
K1 =< K2, !.
min_heapify(H, P) :-
L is 2*P,
heap_has_size(H, S), L =< S,
heap_entry(H, P, K1, V1),
heap_entry(H, L, K2, V2),
K1 > K2,
retract(heap_entry(H, P, K1, V1)),
retract(heap_entry(H, L, K2, V2)),
assert(heap_entry(H, P, K2, V2)),
assert(heap_entry(H, L, K1, V1)),
min_heapify(H, L).
Комментарии:
1. Кажется, что вы никогда не меняете родительский узел на правильный дочерний узел…
2. Кроме того, когда родительский узел имеет два дочерних узла, его необходимо поменять местами с меньшим дочерним узлом.
Ответ №1:
На самом деле, как я уже говорил ранее в своем комментарии, вы никогда не меняете отца на правильного ребенка.
Посмотрите, как ваш код изменен, чтобы он мог показывать вам, что он делает на каждом шаге (я просто включил предикат, чтобы показать, как изменяется куча во время выполнения).
Я думаю, это поможет вам понять проблему с вашей реализацией).
Подсказка: предикат heapify должен корректировать записи кучи снизу вверх, а не сверху вниз (т. Е. Начиная с записи Size//2 и уменьшаясь до записи 1 ).
:- dynamic heap_entry/4.
min_heapify(H, P) :-
format('~nHeapify node: ~w~n', [P]),
show_tree(H),
get0(_),
fail.
min_heapify(H, P) :-
heap_has_size(H, S),
P = S,
!.
min_heapify(H, P) :-
R is (2*P) 1,
heap_has_size(H, S), R =< S,
heap_entry(H, P, K1, _V1),
heap_entry(H, R, K2, _V2),
K1 =< K2, !.
min_heapify(H, P) :-
L is 2*P,
heap_has_size(H, S), L =< S,
heap_entry(H, P, K1, V1),
heap_entry(H, L, K2, V2),
K1 > K2,
retract(heap_entry(H, P, K1, V1)),
retract(heap_entry(H, L, K2, V2)),
assert(heap_entry(H, P, K2, V2)),
assert(heap_entry(H, L, K1, V1)),
min_heapify(H, L).
heap_has_size(H, S) :-
aggregate_all(count, heap_entry(H,_,_,_), S).
show_tree(H) :-
heap_has_size(H, S),
show_tree(H, S, 1, 0).
show_tree(H, S, I, D) :-
( I =< S
-> R is 2*I 1,
L is 2*I,
show_tree(H, S, R, D 1),
heap_entry(H, I, K, V),
tab(5*D),
writeln([K,V]),
show_tree(H, S, L, D 1)
; true ).
:- initialization
retractall(heap_entry(_,_,_,_)),
assertz(heap_entry(h1, 1, 16, a)),
assertz(heap_entry(h1, 2, 2, b)),
assertz(heap_entry(h1, 3, 4, c)),
assertz(heap_entry(h1, 4, 3, d)),
assertz(heap_entry(h1, 5, 7, e)),
assertz(heap_entry(h1, 6, 10, f)),
assertz(heap_entry(h1, 7, 9, g)),
assertz(heap_entry(h1, 8, 8, h)),
assertz(heap_entry(h1, 9, 14, i)),
assertz(heap_entry(h1, 10, 1, l)).
Вот результат:
?- min_heapify(h1,1).
Heapify node: 1
[9,g]
[4,c]
[10,f]
[16,a]
[7,e]
[1,l]
[2,b]
[14,i]
[3,d]
[8,h]
|:
Heapify node: 2
[9,g]
[4,c]
[10,f]
[2,b]
[7,e]
[1,l]
[16,a]
[14,i]
[3,d]
[8,h]
|:
Heapify node: 4
[9,g]
[4,c]
[10,f]
[2,b]
[7,e]
[1,l]
[3,d]
[14,i]
[16,a]
[8,h]
|:
Heapify node: 8
[9,g]
[4,c]
[10,f]
[2,b]
[7,e]
[1,l]
[3,d]
[14,i]
[8,h]
[16,a]
|:
false.
Ответ №2:
Реализация min_heapify , согласно подсказке, которую я дал вам ранее (вы можете сравнить ее со своей реализацией и посмотреть, что вам нужно изменить):
:- dynamic heap_entry/4.
min_heapify(H) :-
heap_has_size(H, S),
N is S//2,
min_heapify_loop(H, S, N).
min_heapify_loop(H, S, N) :-
( N < 1
-> true
; sift_down(H, S, N),
succ(M, N),
min_heapify_loop(H, S, M) ).
heap_has_size(H, S) :-
aggregate_all(count, heap_entry(H,_,_,_), S).
sift_down(H, S, I) :-
( has_smaller_child(H, S, I, J)
-> swap_entries(H, I, J),
sift_down(H, S, J)
; true ).
has_smaller_child(H, S, I, J) :-
2*I =< S,
J1 is 2*I,
J2 is 2*I 1,
entry_key(H, I, K0),
entry_key(H, J1, K1),
entry_key(H, J2, K2),
( K1 < K2
-> (J, K) = (J1, K1)
; (J, K) = (J2, K2) ),
K < K0.
entry_key(H, I, K) :-
( heap_entry(H, I, K, _)
-> true
; K = inf ).
swap_entries(H, I, J) :-
retract(heap_entry(H, I, K1, V1)),
retract(heap_entry(H, J, K2, V2)),
assertz(heap_entry(H, I, K2, V2)),
assertz(heap_entry(H, J, K1, V1)).
show_tree(Heap) :-
heap_has_size(Heap, Size),
show_tree(Heap, Size, 1, 0).
show_tree(Heap, Size, Root, Depth) :-
( Root =< Size
-> RightChild is 2*Root 1,
LeftChild is 2*Root,
show_tree(Heap, Size, RightChild, Depth 1),
heap_entry(Heap, Root, Key, Value),
tab(5*Depth),
writeln([Key, Value]),
show_tree(Heap, Size, LeftChild, Depth 1)
; true ).
:- initialization
retractall(heap_entry(_,_,_,_)),
assertz(heap_entry(h1, 1, 16, a)),
assertz(heap_entry(h1, 2, 2, b)),
assertz(heap_entry(h1, 3, 4, c)),
assertz(heap_entry(h1, 4, 3, d)),
assertz(heap_entry(h1, 5, 7, e)),
assertz(heap_entry(h1, 6, 10, f)),
assertz(heap_entry(h1, 7, 9, g)),
assertz(heap_entry(h1, 8, 8, h)),
assertz(heap_entry(h1, 9, 14, i)),
assertz(heap_entry(h1, 10, 1, l)),
writeln('nBefore heapifyn'),
show_tree(h1),
min_heapify(h1),
writeln('nAfter heapifyn'),
show_tree(h1).
Результат выполнения:
Before heapify
[9,g]
[4,c]
[10,f]
[16,a]
[7,e]
[1,l]
[2,b]
[14,i]
[3,d]
[8,h]
After heapify
[9,g]
[4,c]
[10,f]
[1,l]
[7,e]
[16,a]
[2,b]
[14,i]
[3,d]
[8,h]