最近开始做LeetCode的题目，发现自己仅仅能做简单的，中等题做起来就很吃力了。所以，恰有时间，就刷刷《算法导论》，并打算用java把算法导论中简单的算法实现下。加深java编程能力。
堆排序，时间复杂度O(nlogn),原址。原址：任何时刻都只需要常数个额外的元素空间存储临时数据。
最大堆中，除根节点外，所有节点i满足Heap[Parent(i)]>=Heap[i]。排序通常用最大堆，构造优先队列通常用最小堆。最大堆和最小堆实现基本一样，只要修改维护堆性质的函数即可。
废话不多说，直接代码：
public class MaxHeap { int[] heap;//存放堆 int heapsize;//堆元素个数 //初始化，传入数组 public MaxHeap(int[] array) { this.heap = array; heapsize = heap.length; } //求节点i的父节点 public int heapParent(int i) { return (i - 1) / 2; } //求节点i的左子节点 public int heapLeft(int i) { return 2 * i + 1; } //求节点i的右子节点 public int heapRight(int i) { return 2 * i + 2; } //维护堆的性质,此时间复杂度为O(log i) public void heapMaximize(int i) { int l = heapLeft(i); int r = heapRight(i); int maximum = i; if (l < heapsize && heap[l] > heap[i]) maximum = l; if (r < heapsize && heap[r] > heap[maximum]) maximum = r; if (maximum == i || maximum >= heapsize) return; int tmp = heap[i]; heap[i] = heap[maximum]; heap[maximum] = tmp; heapMaximize(maximum); } //构造最大堆,必须从下往上构造 public void buildMaxHeap() { for (int i = heapsize / 2; i >= 0; i--) heapMaximize(i); } //堆排序算法实现 public void heapSort() { for (int i = heapsize - 1; i >= 0; i--) { int tmp = heap[i]; heap[i] = heap[0]; heap[0] = tmp; heapsize--; heapMaximize(0); } } public static void printHeapTree(int[] heap) { for (int i = 1; i < heap.length; i = i * 2) { for (int j = i - 1; j < 2 * i - 1 && j < heap.length; j++) { System.out.print(heap[j] + " "); } System.out.println(); } } private static void printHeap(int[] heap) { for (int i = 0; i < heap.length; i++) { System.out.print(heap[i] + " "); } } public static void main(String[] args) { int[] array = new int[]{10, 11, 12, 1, 2, 3, 4, 5, 13, 19, 6, 7, 8, 9, 5}; MaxHeap heap = new MaxHeap(array); System.out.println("执行最大堆化前堆的结构："); printHeapTree(heap.heap); heap.buildMaxHeap(); System.out.println("执行最大堆化后堆的结构："); printHeapTree(heap.heap); heap.heapSort(); System.out.println("执行堆排序后数组的内容"); printHeap(heap.heap); } }
