理解 add_to_heap(+Heap0, +Priority, ?Key, -Heap)

Question

来自docs:

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

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

如果我没理解错的话，那么add_to_heap在Heap0中添加一个key及其优先级，然后在Heap中添加Heap0。所以 Heap 基本上是一盒堆？

Answer 1

否。 Prolog 是一种声明式 语言。这意味着 - 除了 进一步 基础 - 一旦变量有一个值，你就不能再改变那个值 （通过回溯你可以 undo 那个，但在那种情况下你当然失去了先前调用路径的上下文）。因此，您无法将键添加到现有堆。

因此，声明性语言构造了新的结构。例如 append(A,B,C) 将构造一个 new 列表 C 等同于 A 后跟 B。另一个例子是 finger tree.

这也是这个谓词的工作原理：你构造一个等于Heap0的新堆Heap，但不同的是Key 添加给定的 Priority。因此，您仍然可以使用旧的 Heap。

例如：

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

因此，这将测试第一个空堆 H0 在添加 foo 后仍然具有大小 0。 foo 仅添加到新堆 H1（大小为 1）。

您可以——公正地——说构建新的数据结构在计算上是昂贵的。这就是为什么声明式语言通常有一组专用的数据结构——例如，Haskell 和 Prolog 默认使用（链接）列表而不是数组，因为这允许在 O(1 )。 手指树是一种树状数据结构，允许快速push/pop/inspect/...

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