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

来自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，然后将Heap0添加到Heap 。那么 Heap 基本上是一个堆的盒子？

最佳答案

不。Prolog 是一种声明性语言。这意味着 - 除了进一步基础 - 一旦变量有了值，您就无法再更改该值(通过回溯，您可以撤消该值) ，但在这种情况下，您当然会丢失先前调用路径的上下文)。因此您无法向现有堆添加键。

因此，声明性语言构造了新结构。例如 append(A,B,C) 将构造一个新列表 C ，它相当于后面跟着的 A由 B 提供。另一个例子是 finger tree .

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

例如:

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

这因此测试了添加 foo 后第一个空堆H0的大小仍然为0。 foo 仅添加到新堆 H1(其大小为 1)。

您可以公正地说，构建新的数据结构的计算成本很高。这就是为什么声明性语言通常有一组专用的数据结构 - 例如，Haskell 和 Prolog 默认情况下使用(链接)列表而不是数组，因为这允许在 O(1) 中添加到头部。 手指树是一种树状数据结构，允许快速推送/弹出/检查/...

关于prolog - 了解 add_to_heap(+Heap0, +Priority, ?Key, -Heap)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42489333/