堆排序栈溢出

Question

最大堆为递增排序，最小堆为递减
与传统排序算法相比，增加了堆的维护成本。
测试方法采用bobo老师的比较法，数据量1000没问题，数据量1W就发生栈溢出，是因为递归太深的原因么（嵌套递归）？请问应该如何改善呢？
所以说递归不一定就好吧？感觉写习惯了就停不下来

public void sortData() {
        data = sortData(data, size() - 1);
    }

    /**
     * 堆排序
     * @param data
     * @param heapIndex
     * @return
     */
    private Array<E> sortData(Array<E> data, int heapIndex) {
        if (heapIndex == 0) {
            return data;
        }
        // swap 将最大值和最后一个元素交换
        E e = data.getFirst();
        data.set(0, data.get(heapIndex));
        data.set(heapIndex, e);
        data = shiftDown(data, data.getFirst(),0, heapIndex);
        heapIndex--;
        return sortData(data, heapIndex);
    }
     private Array<E> shiftDown(Array<E> data, E e, int i, int k) {


        if (leftChild(i) < k && e.compareTo(data.get(leftChild(i))) < 0) {
            if (rightChild(i) < k && data.get(leftChild(i)).compareTo(data.get(rightChild(i))) < 0) {
                data.set(i, data.get(rightChild(i)));
                data.set(rightChild(i), e);
                data = shiftDown(data, e, rightChild(i), k);
            } else {
                data.set(i, data.get(leftChild(i)));
                data.set(leftChild(i), e);
                data = shiftDown(data, e, leftChild(i), k);
            }
        } else if (rightChild(i) < k && e.compareTo(data.get(rightChild(i))) < 0) {
            data.set(i, data.get(rightChild(i)));
            data.set(rightChild(i), e);
            data = shiftDown(data, e, rightChild(i), k);
        }

        return data;
    }

目前我的解决方法是将sort递归改成while循环，处理1KW条数据没有问题：

 private void sortData(Array<E> data, int heapIndex) {
        while (heapIndex > 0) {
            // swap 将最大值和最后一个元素交换
            E e = data.getFirst();
            data.set(0, data.get(heapIndex));
            data.set(heapIndex, e);
            data = shiftDown(data, data.getFirst(),0, heapIndex);
            heapIndex--;
        }
    }

Answer 1

liuyubobobo 2020-06-16 10:40:00

大概率是递归栈溢出。试一试把递归改成非递归？

• 提问者 qq_萌新_4 #1

  这里我在递归里嵌套了一个递归，sort嵌套了shiftdown，sort改成非递归，shiftdown还是递归，可以处理1KW数据