将对插入堆的方案

Question

这是我似乎无法理解的家庭作业的一部分。我想知道是否有人可以指出正确的方向？

问题如下：

(insert-list-of-pairs vw-pair-list heap) evaluates to the heap resulting from inserting all of the value-weight pairs from the list vw-pair-list into the heap heap.

以下函数是早先在作业中创建的，用于解决此问题：

(define (create-heap vw-pair left right)
    (list vw-pair left right))

(define (h-min heap)
    (car heap))

(define (left heap)
    (cadr heap))

(define (right heap)
    (caddr heap))

在上一个问题中，我能够使用以下代码成功地将一对添加到堆中：

(define (insert vw-pair heap)
    (if (null? heap)
        (create-heap vw-pair '() '())
        (if (< (weight vw-pair) (weight (h-min heap)))
            (create-heap vw-pair (right heap) (insert (h-min heap) (left heap)))
            (create-heap (h-min heap) (right heap) (insert vw-pair (left heap))))))

我尝试使用以下代码实现类似的过程但没有成功：

(define (insert-list-of-pairs vw-pair-list heap)
    (if (null? vw-pair-list)
        heap
        (if (< (car vw-pair-list) (h-min heap))
            (create-heap (car vw-pair-list) (right heap) 
                          (insert-list-of-pairs (cdr vw-pair-list) heap))
            (create-heap (h-min heap) (right heap) 
                          (insert-list-of-pairs vw-pair-list heap)))))

我们将不胜感激任何帮助！

Answer 1

您之前的问题是定义 insert。
有充分的理由您现在不仅知道如何实现 insert，而且您还拥有一个可用于插入的函数，因此您无需再次实现它。

因为这样的对列表是什么？

如果不为空，则为一对后跟一对列表。
并且您已经有一个将一对插入堆中的函数。

如果你有一个将成对列表插入堆的函数，你可以使用它来将列表的其余部分插入堆，然后 insert 将列表的第一个元素插入 that堆，然后就大功告成了。

但是 - 尤里卡！ - "insert a list of pairs into a heap" 函数就是您正在编写的函数。
所以，你递归：

(define (insert-list-of-pairs vw-pair-list heap)
    (if (null? vw-pair-list)
        heap
        (insert (car vw-pair-list)
                (insert-list-of-pairs (cdr vw-pair-list) heap))))

然后你就完成了。

将对插入堆的方案

Scheme Inserting Pairs into Heap

heap

recursion

scheme

data-structures