堆排序优化中有一些不理解的地方

Question

package bobo.algo;

import java.util.*;

// 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序
public class HeapSort {

    // 我们的算法类不允许产生任何实例
    private HeapSort(){}

    public static void sort(Comparable[] arr){

        int n = arr.length;

        // 注意，此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始,为什么要除以2？
        // 最后一个元素的索引 = n-1
        //这个for的作用是什么？
        for( int i = (n-1-1)/2 ; i >= 0 ; i -- )
            shiftDown2(arr, n, i);

        for( int i = n-1; i > 0 ; i-- ){
            swap( arr, 0, i);
            shiftDown2(arr, i, 0);
        }
    }

    // 交换堆中索引为i和j的两个元素
    private static void swap(Object[] arr, int i, int j){
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // 原始的shiftDown过程
    private static void shiftDown(Comparable[] arr, int n, int k){

        while( 2*k+1 < n ){
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;

            if( arr[k].compareTo(arr[j]) >= 0 )break;

            swap( arr, k, j);
            k = j;
        }
    }

    // 优化的shiftDown过程, 使用赋值的方式取代不断的swap,
    // 该优化思想和我们之前对插入排序进行优化的思路是一致的
    private static void shiftDown2(Comparable[] arr, int n, int k){

        Comparable e = arr[k];
        while( 2*k+1 < n ){//为什么是2*k+1？是不是表示左孩子？
            int j = 2*k+1;
            if( j+1 < n && arr[j+1].compareTo(arr[j]) > 0 )
                j += 1;

            if( e.compareTo(arr[j]) >= 0 )
                break;

            arr[k] = arr[j];
            k = j;
        }

        //为什么要写这行代码？e是arr[k]，没有重新赋值，现在又要赋值给arr[k]，看不懂？
        arr[k] = e;
    }

    // 测试 HeapSort
    public static void main(String[] args) {

        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("bobo.algo.HeapSort", arr);

        return;
    }
}

老师你好，麻烦解释下打问号的地方，谢谢！

Answer 1

liuyubobobo 2019-06-04 10:54:54

就是4-5小节所介绍的Heapify的过程。可以参考4-5小节从4:30开始的讲解。

同时，也是我们在上一小节所添加的新的构造函数中一样的逻辑，可以参考课程的官方代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/04-Heap/Course%20Code%20(C%2B%2B)/05-Heapify/Heap.h 58-59行。

注意，在这一小节，我们的heapsort处理的数组，索引是从0开始，在上一小节，我们的索引堆中，索引是从1开始，所以索引有变化：）

==========

为什么arr[k] = e; 这个过程和我们插入排序的时候放置那个带插入元素的道理是一样的。

我们不断地把上面的元素往下移，直到找到e的正确位置，然后把e放到这个位置。

请看我们2-6小节插入排序的代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/02-Sorting-Basic/Course%20Code%20(C%2B%2B)/06-Insertion-Sort-Advance/main.cpp

和30行的意思是一样的。

再插入排序中，每一轮都不断地把前面的元素后移，直到找到正确的带插入的位置，把e放到这个位置：）

==========

继续加油！：）

• 提问者 我有明珠一颗 #1

  非常感谢！

• 提问者 我有明珠一颗 #2

  看了相关章节的视频和github上的代码，理解了，谢谢老师