基于原论文实现堆排序：INHEAP与SETHEAP工作机制疑问

我正尝试根据一篇原论文实现堆排序，但无法理解INHEAP的工作原理。

以下是论文中的代码：

procedure INHEAP (A, n, in);
    value in; integer n; real in; real array A;
    comment INHEAP is given an array A, elements A[1] to 
        A[n] forming a heap and n≥0. INHEAP adds the element in
        to the heap and adjusts n accordingly. The cycle labeled
        scan may be repeated log₂n times, but on average is repeated
        twice only;
    begin integer i,j;
        i:=n:=n+1;
    scan: if i>1 then
        begin j := i÷2;
            if in<A[j] then
            begin A[i] := A[j];
                i := j;
                go to scan
            end
        end;
        A[i] := in
    end INHEAP;

procedure SETHEAP (A,n) ;
    value n; integer n; real array A;
    comment SETHEAP rearranges the elements A[1] to A[n] to form a heap;
    begin integer j;
        j:=1;
        L: INHEAP(A,j,A[j+1]);
        if j<n then go to L
    end SETHEAP

我的疑问：

• 我认为INHEAP中的i:=n:=n+1;语句表示i在n之前完成初始化，对吗？
• SETHEAP中的begin integer j;应当启动一个从1到n的循环，但调用INHEAP时传入了A的第一个和第二个元素作为参数，为何INHEAP会通过A[i] := in将第二个元素加入堆中？

解答 #

关于i:=n:=n+1;的执行逻辑

这是Pascal的连续赋值语法，执行顺序是从右往左：

1. 先计算n+1，把结果赋值给n（此时n变为原n+1，也就是新堆的大小）；
2. 再把更新后的n赋值给i，所以i最终等于新的n，也就是新元素要插入的堆的最后位置索引。

你的理解刚好反了，不是i先初始化，而是n先更新，i再同步为新的n。

关于SETHEAP与INHEAP的协作逻辑

SETHEAP的目标是把数组A[1..n]整理成堆，思路是逐个插入元素构建堆：从只有A[1]的初始堆开始，依次把A[2]、A[3]…A[n]插入堆中，逐步扩大堆的范围。

注：原代码里的SETHEAP有个明显问题——循环里没有j:=j+1，会导致j一直是1，无限调用INHEAP(A,1,A[2])。正确逻辑应该是每次调用后j自增，直到j=n-1（因为要插入的是A[j+1]，j=n时j+1会超出数组范围）。

回到你的疑问：当SETHEAP第一次调用INHEAP(A,j,A[j+1])时，参数是：

• A：目标数组；
• j=1：当前堆的大小（此时堆只有A[1]）；
• A[j+1]=A[2]：要插入堆的新元素。

INHEAP的工作流程：

1. 先把堆的大小n从1更新为2，同时让i=2（新元素的初始位置）；
2. 进入scan循环：因为i>1，计算父节点索引j=i÷2=1；
3. 比较要插入的元素in=A[2]和父节点A[1]：
   • 如果in < A[1]，说明父节点更大，不符合小顶堆性质，把A[1]移到A[2]的位置，i跳到父节点1，退出循环；
   • 如果in >= A[1]，说明位置合适，直接退出循环；
4. 最后把in赋值给A[i]，把新元素放到正确位置，完成插入。

所以INHEAP并不是“传入第一个和第二个元素”，而是传入当前堆的大小j=1和要插入的元素A[2]，通过调整位置把A[2]加入堆结构，这就是A[i] := in的作用。

内容的提问来源于stack exchange，提问作者Nocxy