堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根结点的值小于（或大于）两个子节点的值，同时，根节点的两个子树也分别是一个堆。 堆排序就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。 堆排序的实现需要解决的两个关键问题： （1）将一个无序序列构成一个堆。
（2）输出堆顶元素后，调整剩余元素成为一个新堆。
堆排序的时间复杂度为O(nlogn)，由于堆排序对原始记录的状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。空间复杂度为O（1），为不稳定排序。
public class HeapSort{ public static void main(String[] args) { int[] arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; heapSort(arr); printHeap(arr); } //堆排序函数 public static void heapSort(int[] arr) { int len = arr.length; buildHeap(arr, len); //首次建堆，建成一个完整的大顶堆（根节点为最大值） for (int i = 0; i < len; i++) { swap(arr, 0, len - 1 - i); //将堆顶元素（通过调整堆获得的最大值）和最后一个交换（剩余未排好序部分的最后一个） adjustHeap(arr, len - 1 - i, 0); //之后每次从堆顶开始调整，最大的值将上升到根节点 } } //第一次建堆的过程 public static void buildHeap(int[] arr, int maxlen) { int len = maxlen / 2 - 1; //完全二叉树的最后一个非叶子结点 for (int i = len; i >= 0; i--) { adjustHeap(arr, maxlen, i); } } /** * maxlen 此次调整堆的最大元素个数(因为堆排序过程中，后面已经调整好的就不需要调整了) * i 表示此次调整堆的父节点 * */ public static void adjustHeap(int[] arr, int maxlen, int i) { int left = 2 * i + 1; //获得该父节点的左孩子 int right = 2 * i + 2; //获得该父节点的右孩子 int maxpos = i; while (left < maxlen) { if (right < maxlen && arr[maxpos] < arr[right]) { maxpos = right; } if (arr[maxpos] < arr[left]) { maxpos = left; } if (maxpos != i) { swap(arr, i, maxpos); i = maxpos; //继续向下调整，因为此次调整可能会破坏原来下面的堆 left = 2 * i + 1; right = 2 * i + 2; } else { break; } } } //交换堆中任意两个数 public static void swap(int[] arr, int from, int to) { int temp = arr[from]; arr[from] = arr[to]; arr[to] = temp; } //打印堆中的数据 public static void printHeap(int[] arr) { int len = arr.length; for (int i = 0; i < len; i++) { System.out.print(arr[i] + " "); } System.out.println(); }}
