堆排序
堆排序(Heapsort) 是指利用堆这种数据结构所设计的一种排序算法. 堆是一个近似完全二叉树的结构, 并同时满足堆的性质: 即子节点的键值或索引总是大/小于它的父节点
若堆是什么样的结构不清楚的, 可以点这里
堆节点的访问
通常堆是通过数组来实现的, i是堆中的一个节点的下标, 则:
父节点下标: (i -1) >>> 1;
左子节点的下标: 2*i + 1;
右子节点的下标: 2*1 + 2;
堆排序的策略
- 从最后一个 parent节点开始, 塑造最大堆(就是将parent, left, right 中的最大值放置到 parent位置), 一直到堆顶, 经过这一步, 整个堆中的最大值就位于index=0的位置
- 将第一步中的最大值(index=0)与数组的末尾节点兑换(注意这时 index=2 和 index=3都是下面子堆的最大值), 再在剩余部分构建最大值, 然后再重复将最大值与剩余数组中最后节点更换值, 再次构建最大堆, 直到最后一个元素.
废话不说了, 直接上代码:
import java.util.Arrays;
/**
* Created by xjk on 1/12/17.
*/
public class HeapSort {
private static int[] sort = new int[]{1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12, 17, 34, 11};
public static void main(String[] args) {
buildMaxHeapify(sort);
heapSort(sort);
System.out.println(Arrays.toString(sort));
}
/**
* 创建最大树
* @param data
*/
private static void buildMaxHeapify(int[] data){
// 获取数组的最后一个父节点的index
int startIndex = getParentIndex(data.length - 1);
// 从最后一个父节点开始排序
// 每次调用 maxHeapify 其实是将一颗二叉树中最大的值放到parent位置, 而这里是从底层往上
// 从而最终效果是, 整个数组中的每棵树的最大值都在parent位置
for(int i = startIndex; i >= 0; i--){
maxHeapify(data, data.length, i);
}
}
private static void heapSort(int[] data){
// 1. 将最大树的头节点(即整棵树的最大值)与末尾节点交换
// 2. 排除最大值, 数组的剩余部分进行最大值排序
// 3. 重复 1, 2 步骤, 直达最顶的那个节点
for(int i = data.length - 1; i > 0; i--){
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
/**
* 创建最大堆
* @param data
* @param heapSize 需要创建最大堆的大小, 一般在sort时候会用到
* @param index 当前需要创建最大堆的位置
*/
private static void maxHeapify(int[] data, int heapSize, int index){
// 当前点与左右子节点的比较
int left = getLeftChildIndex(index);
int right = getRightChildIndex(index);
int largest = index;
if(left < heapSize && data[index] < data[left]){
largest = left;
}
if(right < heapSize && data[largest] < data[right]){
largest = right;
}
// 获取子节点中的最大值后可能需要交换, 交换后最大的值就在父节点
if(largest != index){
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
maxHeapify(data, heapSize, largest);
}
}
/**
* 获取父节点
* @param current
* @return
*/
private static int getParentIndex(int current){
return (current - 1) >>> 1;
}
/**
* 获取左子节点的
* @param current
* @return
*/
private static int getLeftChildIndex(int current){
return (current << 1) + 1;
}
/**
* 获取右子节点的坐标
* @param current
* @return
*/
private static int getRightChildIndex(int current){
return (current << 1) + 2;
}
}
总结
整堆排序过程其实就三步:
- 构建最大堆(buildMaxHeapify)
- 将头节点与为节点更换, 更换后将除尾节点外的数组看作一个堆, 对这个堆进行最大值排序(heapSort)
- 重复第二步, 直达最后一个节点 (heapSort)
参考资料:
HeapSort
vickyqi 堆排序
