一、概念及其介绍

堆排序（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 实例代码

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

package runoob.heap;import runoob.sort.SortTestHelper;/*** 用heapify进行堆排序*/
public class Heapify {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 = 0 ; 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 == 0;}// 像最大堆中插入一个新的元素 itempublic void insert(T item){assert count + 1 <= capacity;data[count+1] = item;count ++;shiftUp(count);}// 从最大堆中取出堆顶元素, 即堆中所存储的最大数据public T extractMax(){assert count > 0;T ret = data[1];swap( 1 , count );count --;shiftDown(1);return ret;}// 获取最大堆中的堆顶元素public T getMax(){assert( count > 0 );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]) < 0 ){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]) > 0 )j ++;// data[j] 是 data[2*k]和data[2*k+1]中的最大值if( data[k].compareTo(data[j]) >= 0 ) break;swap(k, j);k = j;}}// 测试 heapifypublic static void main(String[] args) {int N = 100;Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);Heapify heapify = new Heapify(arr);// 将heapify中的数据逐渐使用extractMax取出来// 取出来的顺序应该是按照从大到小的顺序取出来的for( int i = 0 ; 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];}
}