基于1索引的三叉堆排序首弹出值异常问题排查求助

首先说明：本次实现的是基于索引1的数组堆排序，若从索引0开始计算会打乱逻辑，基础框架逻辑来自教材提示，也是教授要求的实现规范，因此沿用当前的通用实现模式。

堆排序整体可运行，但几乎每次的首个弹出值都是错误的。多次运行程序尝试总结错误规律，发现偶尔能实现完整排序，偶尔会有1-2个随机值位置异常（95%概率为首个输出值出错）。最新一次运行输出如下：

[20, 14, 411, 157, 37, 295, 549, 682, 686, 41]
37
14
20
41
295
157
411
549
682
686

Process finished with exit code 0

现有代码逻辑较为简洁，部分基础逻辑来自教材的二叉堆实现，在此基础上扩展方法，尝试将二叉堆排序逻辑修改为三叉堆排序。如果需要了解算法逻辑细节，可以补充说明。

• 首先怀疑因为是1索引排序，大概率是索引0未被正确处理，但对照上面的输出可以排除该问题：如果确实是该原因，输出首值应该是791而非135，与实际情况不符。
• 之后猜测可能是数值处理方法存在差1错误，尝试调整相关逻辑但没有进展，也可能是遗漏了某些细节。
• 最后核对了索引计算逻辑：1索引堆排序下，索引k的父节点为(k+1)/3，子节点为3k、3k-1、3k+1，认为该计算逻辑是正确的。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class HeapSort {
    static Random rand;

    // 该类不允许实例化
    private HeapSort() { }

    /**
     * 按自然升序重排数组
     */
    public static void sort(Comparable[] pq) {
        int n = pq.length;

        // 堆化阶段
        for (int parent = (n+1)/3; parent >= 1; parent--)
            sink(pq, parent, n);

        // 排序下沉阶段
        int parent = n;
        while (parent > 1) {
            exch(pq, 1, parent--);
            sink(pq, 1, parent);
        }
    }

    /***************************************************************************
     * 恢复堆不变性的辅助函数
     ***************************************************************************/

    private static void sink(Comparable[] pq, int parent, int n) {
        while (3*parent <= n) {
            int child = 3*parent;
            // 检查左右相邻子节点，每个父节点对应3个子节点
            if (child < n && less(pq, child, child+1)) child++;
            else if (child < n && less(pq, child, child-1)) child--;

            if (!less(pq, parent, child)) break;
            exch(pq, parent, child);
            parent = child;
        }
    }

    /***************************************************************************
     * 比较和交换的辅助函数
     * 索引统一减1以支持1-based索引规则
     ***************************************************************************/
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

    // 打印数组到标准输出
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    /**
     * 生成指定长度的随机不重复整数数组
     */
    public static Integer[] createIntegerKeys(int length) {
        rand = new Random();
        ArrayList<Integer> keys = new ArrayList<>();
        // 填充列表
        while(keys.size() < length) {
            int i = rand.nextInt(1000) + 1;
            if (!keys.contains(i)) {
                keys.add(i);
            }
        }
        // 打乱列表
        Collections.shuffle(keys);
        System.out.println(keys);

        Integer[] shuffled = keys.toArray(new Integer[keys.size()]);
        return shuffled;
    }

    public static void main(String[] args) {
        Integer[] a = createIntegerKeys(10);
        HeapSort.sort(a);
        show(a);
    }
}

错误根因 #

问题出在sink方法的子节点选择逻辑上，当前代码使用else if判断子节点大小，只会比较最多2个子节点，无法正确选出3个子节点中的最大值：

1. 如果第一个if条件成立（child节点小于child+1节点），child指针后移一位后，不会再和第三个子节点child-1比较，可能漏掉更大的子节点
2. 如果第一个if不成立，才会去和child-1比较，同样无法覆盖三个子节点全量对比的场景，导致堆不变性被破坏，排序结果出错。

修复代码 #

修改sink方法的子节点选择逻辑，遍历所有存在的子节点，选出最大值对应的索引即可：

private static void sink(Comparable[] pq, int parent, int n) {
    while (3*parent <= n) {
        int child = 3*parent;
        // 先比较3k和3k-1
        if (child - 1 >= 1 && less(pq, child, child - 1)) {
            child = child - 1;
        }
        // 再和3k+1比较，注意判断边界避免越界
        if (child + 1 <= n && less(pq, child, child + 1)) {
            child = child + 1;
        }

        if (!less(pq, parent, child)) break;
        exch(pq, parent, child);
        parent = child;
    }
}

验证说明 #

你之前的父子节点索引计算逻辑是正确的，不需要调整，仅修正子节点选择逻辑后，堆排序就能正常输出升序结果。

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