堆是一个近似完全二叉树完全二叉树)的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
大顶堆：子节点的键值或索引总是小于(或等于)它的父节点
小顶堆：子节点的键值或索引总是大于(或等于)它父节点
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法，是选择排序的扩展，它的最好和最坏的平均复杂度都为O(nlogn)，是不稳定排序算法。
堆排序步骤案例：使用大顶堆模式对数组[5, 15, 10, 20, 13]进行升序排序
步骤一：对给定数组[5, 15, 10, 20, 13]进行调整，转换成大顶堆数组（一般升序使用大顶堆，降序使用小顶堆）
(1). 创建一个指针指向调整起点(第一次调整时指向给定数组的二叉树结构的最后一个非叶子节点 )
(1.1). 将指针指向的节点的值与它子节点的最大值进行比较，当指针指向的节点的值小于子节点的最大值时，进行调整交换
(1.2). 当发生交换时将指针指向与它发生交换的子节点位置循环步骤(1)，如果没有发生交换或指针指向叶子节点则结束步骤(1)
(2). 再从最后一个非叶子节点开始，往上遍历节点，以遍历节点为调整起点循环步骤(1)，直到遍历完根节点
步骤二：将堆顶元素(即数组0下标位置)与末尾元素进行交换，使得尾部元素最大。
(1). 因为经过步骤一后，数组已经变成了大顶堆结构，这时数组的第一个元素就是数组中最大的元素，而排序要求是升序，所以要把第一个元素与最后一个元素 (排除掉切割出的长度) 进行交换，使得最大元素在操作数组的最后。交换完后需把操作数组中的末尾元素切割出去（实际操作通过调整长度来实现切割，而不是创建一个新的数组）。
(2). 因为经过步骤(1)后，数组的大顶堆结构已经被破坏了，所以需重新调整，即跳到步骤一，又因为根节点元素发生了变化，所以此时调整起点为根节点。
步骤三：循环执行步骤一和步骤二，当操作数组的元素都被切割出去时（调整长度为0），则表明数组已经按升序顺序排序完成
public class HeapSort { public static void main(String[] args) { int array[] = {5, 15, 10, 20, 13}; heapSort(array); System.out.println(Arrays.toString(array)); } //堆排序(从小到大排序，大顶堆模式实现) public static void heapSort(int array[]){ int temp = 0; /* 在二叉树中由下到上，把二叉树数组调整成大顶堆数组 array.length/2-1 ：指向最后一个非叶子节点 */ for (int i = array.length/2-1; i>=0; i--){ adjustHeap(array, i, array.length); } /* 在经过调整后，数组的第一个索引0的值必定是数组调整长度内最大的值， 因为是从小到大进行排序，所以要把索引0的值放到调整长度内最后一个索引的值， 即放到调整长度-1的索引位置 */ for (int j = array.length-1; j>0; j--){ //将调整长度内最大值array[0]和调整长度内最后位置的值array[j]进行交换 temp = array[j]; array[j] = array[0]; array[0] = temp; /* 又因为经过交换后，大顶堆的结构会被破坏，所以要重新进行调整， 调整起点应为根节点(因为根节点发生了变化)，即数组0下标位置， 而array[j]已经是不需要调整的了，所以调整长度为j(因为在调整方法里j参数是被当作长度处理的，所以无需-1) */ adjustHeap(array,0, j); } } /** * 将数组调整成大顶堆数组 * @param array 需调整的数组 * @param i 索引指针，开始指向传入的非叶子节点，后面指向最后进行交换(插入)的节点 * @param length 需调整的长度，即调整的元素个数，从0下标索引开始 */ public static void adjustHeap(int array[], int i, int length){ //辅助变量，存储传入的非叶子节点的值 int temp = array[i]; /* 遍历传入的非叶子节点下的子节点，i*2+1为左节点，i*2+2为右节点 如果该节点不是非叶子节点则退出循环 */ for (int k = i*2+1; k<length; k = k*2+1){ /* 判断该节点是否有右节点，即k+1是否超过数组范围索引 如果有，则比较大小，拿出最大值的节点 */ if (k+1 < length && array[k] < array[k+1]){ //如果右节点大，把索引k+1即可使k指向右节点 k++; } //判断传入的非叶子节点的值是否小于它子树节点的最大值 if (temp < array[k]){ //如果小于则把大于它的子节点的值赋给该节点 array[i] = array[k]; //再把非叶子节点的指针指向该子节点的位置，继续循环 i = k; }else { /* 因为在调整二叉树数组成大顶堆数组时，是从下到上进行遍历调整的， 而循环条件是从上到下递减的，所以当上诉条件不成立时直接退出即可 */ break; } } /* 因为在上面节点和节点的交换中使用的是插入算法，所以在退出循环时， 需要将初始传入的非叶子节点的值temp赋给最后一个实现交换(插入)的节点,即i指向的节点 */ array[i] = temp; } }