1 package Sort; 2  3 import org.junit.Test; 4  5 public class HeapSort { 6  7     // 交换数组中的两个元素 8     public void exchange(int[] array, int index1, int index2) { 9         int tmp = array[index1];10         array[index1] = array[index2];11         array[index2] = tmp;12     }13 14     /**15      * 功能 保证index索引后的元素都满足最大堆的性质16      * 17      * @param array18      *            一个无序的数组19      * @param index20      *            数组的一个下标21      * @parem heapSize 真正有效的堆元素数量22      */23     public void MaxHeapify(int[] array, int index, int heapSize) {24 25         // 假设根节点为array[left],array[right]满足最大堆的性质26         int left = 2 * index;27         int right = left + 1;28         int largest = index;29         // largest用来指向最大元素的下标30         if (left <= heapSize && array[left] > array[index])31             largest = left;32         if (right <= heapSize && array[right] > array[largest])33             largest = right;34         if (largest != index) {35             exchange(array, largest, index);36             MaxHeapify(array, largest, heapSize);37         }38     }39 40     // 构建最大堆，注意下标从1开始，类似于完全二叉树41     public void BuildMaxHeap(int[] array) {42 43         // 不考虑array[0]44         int i = (array.length - 1) / 2;45         while (i >= 1) {46             // 此时堆中有效的元素是数组的长度-1个47             MaxHeapify(array, i, array.length - 1);48             --i;49         }50     }51 52     // 真正的堆排序算法要开始了53     public void heapSort(int[] array) {54         int heapSize = array.length - 1;55         BuildMaxHeap(array);56         for (int i = array.length - 1; i > 1; --i) {57             exchange(array, 1, i);58             MaxHeapify(array, 1, --heapSize);59         }60     }61 62     // 返回数组中的最大元素,并从数组中删除它63     // 返回优先队列中优先级最高的元素,出队64     // 实际上出队的过程只是把元素拿到了数组的尾部65     public int heapExtractMax(int[] array, int heapSize) {66         // 注意优先队列中并不存储下标为0的元素67         if(array.length == 1 || array == null)68             return -1;69         int max = array[1];70         array[1] = array[heapSize];71         MaxHeapify(array, 1, heapSize);72         return max;73     }74     75     // 将数组下标为i的值更改为key,如果key值小于原来索引位置的值,则直接退出76     public void heapIncreaseKey(int[] array, int i, int key) {77         if (key < array[i])78             return;79         array[i] = key;80         while (i > 1 && array[i / 2] < array[i]) {81             exchange(array, i / 2, i);82             i = i / 2;83         }84     }85 86     @Test87     public void test() {88         int[] array = { -1, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };89         heapSort(array);90         Array.print(array);91     }92 93 }