(1 2 3 . #)- 堆排序

Question

我尝试用所有常规操作（合并、删除最小等）实现一个“配对堆”，然后我被要求编写一个函数，使用我新构建的堆实现对列表进行排序。不幸的是，似乎有些地方出了问题......

这是相关的代码：

(define (heap-merge h1 h2)
  (cond ((heap-empty? h1) h2)
    ((heap-empty? h2) h1)
    (else (let ((min1 (heap-get-min h1))
        (min2 (heap-get-min h2)))
        (if ((heap-get-less h1) min1 min2)
        (make-pairing-heap (heap-get-less h1) min1 (cons h2 (heap-get-subheaps h1)))
        (make-pairing-heap (heap-get-less h1) min2 (cons h1 (heap-get-subheaps h2))))))))

(define (heap-insert element h)
(heap-merge (make-pairing-heap (heap-get-less h) element '())
       h))

(define (heap-delete-min h)
(define (merge-in-pairs less? subheaps)
(cond
  ((null? subheaps) (make-heap less?))
  ((null? (cdr subheaps)) (car subheaps))
  (else (heap-merge (heap-merge (car subheaps) (cadr subheaps))
                            (merge-in-pairs less? (cddr subheaps))))))
(if (heap-empty? h) (error "expected pairing-heap for first argument, got an empty heap ")
  (merge-in-pairs (heap-get-less h) (heap-get-subheaps h)))) 

(define (heapsort l less?)
(let aux ((h (accumulate heap-insert (make-heap less?) l)))
(if (not (heap-empty? h))
     (cons (heap-get-min h) 
    (aux (heap-delete-min h)))))) 

这些是一些选择器，可以帮助您理解代码：

(define (make-pairing-heap less? min subheaps) 
(cons less? (cons min subheaps)))
(define (make-heap less?)
(cons less? '()))
(define (heap-get-less h)
(car h))
(define (heap-empty? h)
(if (null? (cdr h)) #t #f))

现在让我们解决问题：当我运行“heapsort”时，它返回带有“void”的排序列表“，如您所见：

> (heapsort (list 1 2 3) <)
(1 2 3 . #<void>)

..我该如何解决它？

问候， 超级守护者

Answer 1

由于这是作业，我将告诉您我用来查找错误的过程。如果您仍然卡住，请告诉我。

老实说，在 Stack Overflow 问题中，代码太多，无法深入分析*。所以我必须使用输出中的线索。具体来说，您有一个其中包含空白的列表。它位于最后，在不正确的列表中。这意味着两件事：

1. 您有一个不返回值的函数。导致这种情况的两件事是 (1) 只编写一个分支的 if - else 分支将返回 void - 或者 (2) 以 < 结束你的函数code>display，返回 void。
2. 你做的最后一件事是cons。您可能打算继续 consing，或者您可能打算在 '() 上进行 cons，而不是正确地结束列表。

所以：第一步是在代码中搜索 cons 的所有用途。你的选择器看起来不错。这样就留下了 heap-merge 中的两个分支和 heapsort 中的 cons 。对 cons 的所有三个调用都使用函数来获取其 cdr。

因此：下一步是查看 heap-get-subheaps 和 aux 来查看其中一个是否具有不返回值的代码路径。也许您错误地留下了一些调试语句。或者也许您有一个只有 true 分支的 if，而您忘记了 false 分支。

---

*注意：大多数方案的调试功能很少，因此启发式方法无论如何都是您的最佳选择。这是一项后天获得的技能。