理解add_to_heap(+-Heap 0，+优先级，?Key，-Heap)

Question

来自文档

add_to_heap(+Heap0, +Priority, ?Key, -Heap)是半行距 将具有优先级的Key添加到Heap0，在Heap中构造新的堆。

如果我正确理解它，那么add_to_heap会向Heap0添加一个键及其优先级，然后将Heap0添加到Heap中。那么，Heap基本上是一盒堆？

Answer 1

No. Prolog是一种声明性语言。这意味着，除了进一步接地之外，一旦变量有了一个值，您就不能再更改值了(通过回溯，您可以撤销该值，但在这种情况下，您当然会丢失上一次调用路径的上下文)。因此，不能向现有的堆添加密钥。

因此，声明性语言构建了新的结构。例如，append(A,B,C)将构造一个新的list C，其等价于A，后面跟着B。另一个例子是https://en.wikipedia.org/wiki/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).

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

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