Understanding add_to_heap(+Heap0, +Priority, ?Key, -Heap)

Question

From the docs:

add_to_heap(+Heap0, +Priority, ?Key, -Heap) is semidet

Adds Key with priority Priority to Heap0, constructing a new heap in Heap.

If I understand it correctly, then add_to_heap adds a key and its priority to Heap0, and then adds Heap0 to Heap. So Heap is basically a box of heaps?

Answer 1

No. Prolog is a declarative language. That means that - aside from further grounding - once a variable has a value, you cannot change that value anymore (by backtracking you can undo that, but in that case you lose of course the context of the previous call path). So you cannot add a key to an existing heap.

As a result declarative languages construct new structures. For instance append(A,B,C) will construct a new list C that is equivalent to A followed by B. Another example is a finger tree.

That is also how this predicate works: you construct a new heap Heap that is equal to Heap0, but the difference is that the Key is added with the given Priority. As a result you can still use the old Heap as well.

For instance:

demonstrate_use_old :-
    empty_heap(H0),
    add_to_heap(H0,0,foo,H1),
    heap_size(H0,0),
    heap_size(H1,1).

This thus tests that the first empty heap H0 still has size 0 after adding foo. foo is only added to a new heap H1 (which has size 1).

You may - justly - say that constructing new datastructures is computationally expensive. That's why declarative languages usually have a set of dedicated datastructures - for instance, Haskell and Prolog by default use a (linked)list instead of an array because this allows adding to the head in O(1). A finger tree is a tree-like datastructure that allows fast push/pop/inspect/...