堆排序

堆排序

堆排序(Heapsort) 是指利用堆这种数据结构所设计的一种排序算法. 堆是一个近似完全二叉树的结构, 并同时满足堆的性质: 即子节点的键值或索引总是大/小于它的父节点

若堆是什么样的结构不清楚的, 可以点这里

堆节点的访问

通常堆是通过数组来实现的, i是堆中的一个节点的下标, 则:

父节点下标: (i -1) >>> 1;
左子节点的下标: 2*i + 1;
右子节点的下标: 2*1 + 2;

堆排序的策略

1. 从最后一个 parent节点开始, 塑造最大堆(就是将parent, left, right 中的最大值放置到 parent位置), 一直到堆顶, 经过这一步, 整个堆中的最大值就位于index=0的位置
2. 将第一步中的最大值(index=0)与数组的末尾节点兑换(注意这时 index=2 和 index=3都是下面子堆的最大值), 再在剩余部分构建最大值, 然后再重复将最大值与剩余数组中最后节点更换值, 再次构建最大堆, 直到最后一个元素.

废话不说了, 直接上代码:

import java.util.Arrays;

/**
 * Created by xjk on 1/12/17.
 */
public class HeapSort {

    private static int[] sort = new int[]{1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11};

    public static void main(String[] args) {
        buildMaxHeapify(sort);
        heapSort(sort);
        System.out.println(Arrays.toString(sort));
    }

    /**
     * 创建最大树
     * @param data
     */
    private static void buildMaxHeapify(int[] data){
        // 获取数组的最后一个父节点的index
        int startIndex = getParentIndex(data.length - 1);
        // 从最后一个父节点开始排序
        // 每次调用 maxHeapify 其实是将一颗二叉树中最大的值放到parent位置, 而这里是从底层往上
        // 从而最终效果是, 整个数组中的每棵树的最大值都在parent位置
        for(int i = startIndex; i >= 0; i--){
            maxHeapify(data, data.length, i);
        }
    }

    private static void heapSort(int[] data){
        // 1. 将最大树的头节点(即整棵树的最大值)与末尾节点交换
        // 2. 排除最大值, 数组的剩余部分进行最大值排序
        // 3. 重复 1, 2 步骤, 直达最顶的那个节点
        for(int i = data.length - 1; i > 0; i--){
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            maxHeapify(data, i, 0);
        }
    }

    /**
     * 创建最大堆
     * @param data
     * @param heapSize 需要创建最大堆的大小, 一般在sort时候会用到
     * @param index 当前需要创建最大堆的位置
     */
    private static void maxHeapify(int[] data, int heapSize, int index){
        // 当前点与左右子节点的比较
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        int largest = index;
        if(left < heapSize && data[index] < data[left]){
            largest = left;
        }
        if(right < heapSize && data[largest] < data[right]){
            largest = right;
        }

        // 获取子节点中的最大值后可能需要交换, 交换后最大的值就在父节点
        if(largest != index){
            int temp = data[index];
            data[index] = data[largest];
            data[largest] = temp;
            maxHeapify(data, heapSize, largest);
        }
    }

    /**
     * 获取父节点
     * @param current
     * @return
     */
    private static int getParentIndex(int current){
        return (current - 1) >>> 1;
    }

    /**
     * 获取左子节点的
     * @param current
     * @return
     */
    private static int getLeftChildIndex(int current){
        return (current << 1) + 1;
    }

    /**
     * 获取右子节点的坐标
     * @param current
     * @return
     */
    private static int getRightChildIndex(int current){
        return (current << 1) + 2;
    }

}

总结

整堆排序过程其实就三步:

1. 构建最大堆(buildMaxHeapify)
2. 将头节点与为节点更换, 更换后将除尾节点外的数组看作一个堆, 对这个堆进行最大值排序(heapSort)
3. 重复第二步, 直达最后一个节点 (heapSort)

参考资料:
HeapSort
vickyqi 堆排序