堆结构是一种通过数组实现的堆结构。
使用场景：
1.DelayQueue中维护PriorityQueue优先队列
2.线程池ScheduledThreadPoolExecutor中维护优先队列
3.堆排序
特点(索引从0开始)：
1.父节点大于(或小于)子节点
2.父节点的左节点在2n+1位置上
3.父节点的右节点在2n+2位置上
4.一个节点的父节点为(n-1)/2
public class HeapSort {
private static void buildMaxHeapify(int[] data) {
// 没有子节点的才需要创建最大堆,从最后一个的父节点开始
int startIndex = getParentIndex(data.length - 1);
// 从尾端开始创建最大堆,每次都是正确的堆
for (int i = startIndex; i >= 0; --i) {
maxHeapify(data, data.length, i);
}
}
/**
* 最大堆
*
* @param heapSize 需要创建最大堆的大小, 一般在sort的时候用到, 因为最大值放在末尾, 末尾就不再归入最大堆
* @param index 当前需要创建最大堆的位置
*/
private static void maxHeapify(int[] data, int heapSize, int index) {
// 当前点和左右子节点比较
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int max = index;
if (left < heapSize && data[index] < data[left]) {
max = left;
}
if (right < heapSize && data[max] < data[right]) {
max = right;
}
// 得到最大值后如果交换,其子节点可能就不是最大堆,需要重新调整
if (max != index) {
int temp = data[index];
data[index] = data[max];
data[max] = temp;
maxHeapify(data, heapSize, max);
}
}
private static void buildMinHeapify(int[] data) {
int startIndex = getParentIndex(data.length - 1);
for (int i = startIndex; i >= 0; --i) {
minHeapify(data, data.length, i);
}
}
private static void minHeapify(int[] data, int heapSize, int index) {
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int min = index;
if (left < heapSize && data[index] > data[left]) {
min = left;
}
if (right < heapSize && data[min] > data[right]) {
min = right;
}
if (min != index) {
int temp = data[index];
data[index] = data[min];
data[min] = temp;
minHeapify(data, heapSize, min);
}
}
/**
* 排序
*
* data是最大堆,最大值放在末尾,排序后就成递增
*/
private static void heapSort(int[] data) {
// 末尾与头交换,交换后调整最大堆
for (int i = data.length - 1; i > 0; --i) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
/**
* 父节点位置
*/
private static int getParentIndex(int current) {
return (current - 1) >> 1;
}
/**
* 左子节点position,注意括号,加法优先级更高
*/
private static int getChildLeftIndex(int current) {
return (current << 1) + 1;
}
/**
* 右子节点position
*/
private static int getChildRightIndex(int current) {
return (current << 1) + 2;
}
public static void main(String[] args) {
int[] array1 = new int[]{21, 10, 10, 20, 13, 5, 6, 4, 19, 8, 12, 17, 34, 11};
buildMinHeapify(array1);
heapSort(array1);
for (int i = 0; i < array1.length; ++i) {
System.out.print(array1[i] + ",");
}
System.out.println();
buildMaxHeapify(array1);
heapSort(array1);
for (int i = 0; i < array1.length; ++i) {
System.out.print(array1[i] + ",");
}
}
}