堆
堆的简介
堆是优先级队列的实现，是一种数据结构，你可以把它看做一棵完全二叉树。
index: 1 2 3 4 5 6 7 8 9 10
+-------------------------------------------------------------+
array: | 16 | 14 | 10 | 8 | 7 | 9 | 3 | 2 | 4 | 1 |
+-------------------------------------------------------------+
|
| 可以把这个数组想像成二叉树
V
index: 1 array: 16
/ \ / \
/ \ / \
2 3 14 10
/\ /\ /\ /\
/ \ / \ / \ / \
4 5 6 7 8 7 9 3
/\ | /\ |
/ \ / / \ /
8 9 10 2 4 1
堆的属性
堆结点的访问
通常堆是通过一维数组来实现的，树的根是第一个元素。
在数组起始位置为 1 的情形中（易于理解，如上图）：
- 父节点 i 的左子节点在位置 (2i)
- 父节点 i 的右子节点在位置 (2i+1)
- 子节点 i 的父节点在位置 floor(i/2)
在数组起始位置为 0 的情形中（用于代码中）：
- 父节点 i 的左子节点在位置 (2i+1)
- 父节点 i 的右子节点在位置 (2i+2)
- 子节点 i 的父节点在位置 floor((i-1)/2)
大根堆和小根堆
大根堆 (Max-heap)
- 大根堆又称最大堆（大顶堆）
- 最大堆中的最大元素值出现在根结点（堆顶）
- 堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
小根堆 (Min-heap)
- 小根堆又称最小堆（小顶堆）
- 最小堆中的最小元素值出现在根结点（堆顶）
- 堆中每个父节点的元素值都小于等于其孩子结点（如果存在）
堆的操作
堆中定义以下几种操作：
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
堆排序
我们假设数组起始位置为 1，方便理解。
Max-Heapify
Max-Heapify 是基本操作，我们会一遍又一遍的递归使用它。
例：对堆 A 的根结点（索引为 1 的结点）进行 Max-Heapify 操作Max-Heapify(A, 1)
(4)
/ \ 根结点是 4，它的孩子大于它，所以这个结点要与
/ \ 它的孩子结点中最大的元素 14 进行交换
(14) 7
/\ /
/ \ /
2 8 1
14
/ \ 交换过后的 4，继续看它的两个孩子是否满足条件
/ \ 发现不满足，这次它和孩子结点中最大的元素 8 进行交换
(4) 7
/\ /
/ \ /
2 (8) 1
14
/ \ 交换过后的 4 没有孩子，Max-Heapify 操作结束
/ \
8 7
/\ /
/ \ /
2 4 1
Build-Max-Heap
Build-Max-Heap(A) 的操作如下 (n 是堆的大小）
for i=n/2 downTo 1:
do Max-Heapify(A, i)
因为在 n/2 之后的结点是没有子结点的，所以只需要从 n/2 开始一直到 1 执行 Max-Heapify 即可。
Heap-Sort
堆排序的过程是：
- 创建一个堆
- 把堆首（最大值）和堆尾互换
- 把堆的尺寸缩小1
- 重复步骤2，直到堆的尺寸为1
Java 代码的实现如下1：
import java.util.Arrays;
public class HeapSort {
private int[] arr;
public HeapSort(int[] arr){
this.arr = arr;
}
/**
* 堆排序的主要入口方法，共两步。
*/
public void sort(){
/*
* 第一步：将数组堆化
* beginIndex = 第一个非叶子节点。
* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
* 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
*/
int len = arr.length - 1;
int beginIndex = (len - 1) >> 1;
for(int i = beginIndex; i >= 0; i--){
maxHeapify(i, len);
}
/*
* 第二步：对堆化数据排序
* 每次都是移出最顶层的根节点 A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
* 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
* 直至未排序的堆长度为 0。
*/
for(int i = len; i > 0; i--){
swap(0, i);
maxHeapify(0, i - 1);
}
}
private void swap(int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 调整索引为 index 处的数据，使其符合堆的特性。
*
* @param index 需要堆化处理的数据的索引
* @param len 未排序的堆（数组）的长度
*/
private void maxHeapify(int index,int len){
int li = (index << 1) + 1; // 左子节点索引
int ri = li + 1; // 右子节点索引
int cMax = li; // 子节点值最大索引，默认左子节点。
if(li > len) return; // 左子节点索引超出计算范围，直接返回。
if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
cMax = ri;
if(arr[cMax] > arr[index]){
swap(cMax, index); // 如果父节点被子节点调换，
maxHeapify(cMax, len); // 则需要继续判断换下后的父节点是否符合堆的特性。
}
}
/**
* 测试用例
*
* 输出：
* [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
*/
public static void main(String[] args) {
int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
new HeapSort(arr).sort();
System.out.println(Arrays.toString(arr));
}
}
tags: #数据结构 #排序 #堆