基础堆排序

一、概念及其介绍

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆是一个近似 完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

二、适用说明

我们之前构造堆的过程是一个个数据调用 insert 方法使用 shift up 逐个插入到堆中，这个算法的时候时间复杂度是 O(nlogn) ，本小节介绍的一种构造堆排序的过程，称为 Heapify ，算法时间复杂度为 O(n) 。

三、过程图示

完全二叉树有个重要性质，对于第一个非叶子节点的索引是 n/2 取整数得到的索引值，其中 n 是元素个数(前提是数组索引从 1 开始计算)。

索引 5 位置是第一个非叶子节点，我们从它开始逐一向前分别把每个元素作为根节点进行 shift down 操作满足最大堆的性质。

索引 5 位置进行 shift down 操作后，22 和 62 交换位置。

对索引 4 元素进行 shift down 操作

对索引 3 元素进行 shift down 操作

对索引 2 元素进行 shift down 操作

最后对根节点进行 shift down 操作，整个堆排序过程就完成了。

四、Java 实例代码

源码包下载： Download

src/yssmx/heap/Heapify.java 文件代码：

package yssmx.heap ;

import yssmx.sort.SortTestHelper ;

/**
 * 用heapify进行堆排序
 */
public class Heapify < T extends Comparable > {

    protected T [ ] data ;
    protected int count ;
    protected int capacity ;

    // 构造函数, 通过一个给定数组创建一个最大堆
    // 该构造堆的过程, 时间复杂度为O(n)
    public Heapify ( T arr [ ] ) {

        int n = arr. length ;

        data = ( T [ ] ) new Comparable [ n + 1 ] ;
        capacity = n ;

        for ( int i = ; i < n ; i ++ )
            data [ i + 1 ] = arr [ i ] ;
        count = n ;
        //从第一个不是叶子节点的元素开始
        for ( int i = count / 2 ; i >= 1 ; i -- )
            shiftDown ( i ) ;
    }
    // 返回堆中的元素个数
    public int size ( ) {
        return count ;
    }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty ( ) {
        return count == ;
    }
    // 像最大堆中插入一个新的元素 item
    public void insert ( T item ) {
        assert count + 1 <= capacity ;
        data [ count + 1 ] = item ;
        count ++;
        shiftUp ( count ) ;
    }
    // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据
    public T extractMax ( ) {
        assert count > ;
        T ret = data [ 1 ] ;
        swap ( 1 , count ) ;
        count --;
        shiftDown ( 1 ) ;
        return ret ;
    }
    // 获取最大堆中的堆顶元素
    public T getMax ( ) {
        assert ( count > ) ;
        return data [ 1 ] ;
    }


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

    //********************
    //* 最大堆核心辅助函数
    //********************
    private void shiftUp ( int k ) {

        while ( k > 1 && data [ k / 2 ] . compareTo ( data [ k ] ) < ) {
            swap ( k, k / 2 ) ;
            k /= 2 ;
        }
    }

    private void shiftDown ( int k ) {

        while ( 2 * k <= count ) {
            int j = 2 * k ; // 在此轮循环中,data[k]和data[j]交换位置
            if ( j + 1 <= count && data [ j + 1 ] . compareTo ( data [ j ] ) > )
                j ++;
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值

            if ( data [ k ] . compareTo ( data [ j ] ) >= ) break ;
            swap ( k, j ) ;
            k = j ;
        }
    }

    // 测试 heapify
    public static void main ( String [ ] args ) {
        int N = 100 ;
        Integer [ ] arr = SortTestHelper. generateRandomArray ( N, , 100000 ) ;
        Heapify < Integer > heapify = new Heapify < Integer > ( arr ) ;
        // 将heapify中的数据逐渐使用extractMax取出来
        // 取出来的顺序应该是按照从大到小的顺序取出来的
        for ( int i = ; i < N ; i ++ ) {
            arr [ i ] = heapify. extractMax ( ) ;
            System . out . print ( arr [ i ] + " " ) ;
        }

        // 确保arr数组是从大到小排列的
        for ( int i = 1 ; i < N ; i ++ )
            assert arr [ i - 1 ] >= arr [ i ] ;
    }
}