堆排序
堆
堆是一种树形结构，在排序的过程中，把元素看成是一颗完全二叉树。用数组来表示一颗完全二叉树的话，对于每个节点 i 存在以下关系：
1）父节点 = (i - 1) / 2
2）左孩子 = 2 * i + 1
3）右孩子 = 2 * i + 2
大根堆，小根堆
父节点都比子节点大的堆成为大根堆，用于升序
父节点都比子节点小的堆成为小根堆，用于降序
如图所示：
大根堆
小根堆
算法思路
因此，我们需要把一个树构造成大根堆或小根堆，以大根堆为例子：
1）构造大根堆
2）把根节点和尾节点进行交换，堆的size--
3）把剩余的堆进行调整，重新调整为大根堆
3）重复2，3步骤，直至堆的size为0
1、构造算法
每次插入一颗子节点，都与父节点进行比较，若比父节点大，则与父节点交换后，再重复以上步骤，直至不比父节点大。
/// 把下标为index的值插入，建立堆
/// 堆与数组的转换：
/// 对于当前下标为index的数，其父亲为 (index - 1) / 2
/// 左节点为 2 * index + 1, 右节点为 2 * index + 2
public static void heapInsert(int[] arr, int index) {
// 比父节点大，则交换，直至比父节点小
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
2、调整算法
父节点依次与左右孩子比较，若其父节点小于左右孩子，则与左右孩子较大者交换，然后重复以上步骤，直至父节点大于左右孩子
/// 重新调整为大根堆，size表示：在数组建立了堆，堆的size
public static void heapify(int arr[], int index, int size) {
// 左节点
int left = index * 2 + 1;
while(left < size) {
// 右节点
int right = left + 1;
// 设左孩子为最大
int largest = left;
if (right < size) {
// 存在右节点，选出其中最大的
largest = arr[left] > arr[right] ? left : right;
}
// 比较父节点和最大子节点的值
largest = arr[index] > arr[largest] ? index : largest;
// 若当前节点就是最大的，则调整完毕
if (largest == index) {
return;
}
// 否则交换
swap(arr, largest, index);
// 继续以上过程
index = largest;
left = index * 2 - 1;
}
}
3、完整代码
public static void heapSort(int arr[]) {
if (arr == null || arr.length < 2) {
return;
}
// 建立大根堆
for(int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
// 将头部换到最后，开始调整，直至size = 0
swap(arr, 0, --size);
while(size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
/// 把下标为index的值插入，建立堆
/// 堆与数组的转换：
/// 对于当前下标为index的数，其父亲为 (index - 1) / 2
/// 左节点为 2 * index + 1, 右节点为 2 * index + 2
public static void heapInsert(int[] arr, int index) {
// 比父节点大，则交换，直至比父节点小
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
/// 重新调整为大根堆，size表示：在数组建立了堆，堆的size
public static void heapify(int arr[], int index, int size) {
// 左节点
int left = index * 2 + 1;
while(left < size) {
// 右节点
int right = left + 1;
// 设左孩子为最大
int largest = left;
if (right < size) {
// 存在右节点，选出其中最大的
largest = arr[left] > arr[right] ? left : right;
}
// 比较父节点和最大子节点的值
largest = arr[index] > arr[largest] ? index : largest;
// 若当前节点就是最大的，则调整完毕
if (largest == index) {
return;
}
// 否则交换
swap(arr, largest, index);
// 继续以上过程
index = largest;
left = index * 2 - 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
网友评论