堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
完全二叉树中有几个特殊的性质
- 1.假设父节点索引为x其左孩子索引为2x+1 右孩子结点为2x+2
- 2.假设孩子结点索引值为y,其父结点的值为(y-1)/2
利用完全二叉树的性质我们可以实现数组堆化,实现堆排序
大根堆,孩子节点值总小于父节点,元结点的数据最大
小根堆,孩子节点值总大于父结点,父结点的数据最小
一 .插入比较,实现大根堆
//插入逐步实现大根堆
public static void heapInsert(int[] arr, int curr) {
while (arr[curr]>arr[parent(curr)]){
swap(arr,curr,parent(curr));
curr=parent(curr);
}
}
这里我们每步都假设前面数据已经实现大根堆,所以是将curr当前索引上数据与前面数据比较继续大根堆
如果我们想实现一个数组堆化,只要保证后续每插入一个都保持堆化就好
eg:
//堆化数组
for(int i=0;i<arr.length;i++){
heapInsert(arr,i);
}
二 .当一个结点数据改变后,保持子树依然堆化
//堆的大小为size即数组0~size-1
//维持index结点所在子树为大根堆 (父结点大)
//如果index位置变化也可以用此函数维持大根堆
//size为数组长度,而不是最后一个索引,是最后一个堆位置索引值+1
public static void heapify(int[] arr, int index, int size) {
while (left(index)<size){
//当存在左孩子节点
//判断两个子结点的值大小,得到最大值的索引
//如果存在右节点且大于左结点,返回右节点值
//否则返回左节点值
int largest=right(index)<size&&arr[right(index)]>arr[left(index)]
?right(index)
:left(index);
//将孩子中大值和index父结点比较,得到最大值索引从而交换让父结点得到最大值
largest=arr[largest]>arr[index]?largest:index;
if (largest == index) {
break;
}
swap(arr,index,largest);
index=largest;
}
}
堆排序
综合上面两个方法我们可以得到堆排序的代码:
package com.day1.sort;
import com.day1.comparator.ArrayComparator;
public class HeapSort extends ArrayComparator {
public static void main(String[] args){
int [] iarr={5,4,1,2,8,6};
heapSort(iarr);
printArray(iarr);
}
//堆排序
public static void heapSort(int[] arr) {
if (arr==null||arr.length<2) { //如果数组为空或者长度为小于等于1
return;
}
//堆化数组
for(int i=0;i<arr.length;i++){
heapInsert(arr,i);
}
int heapsize=arr.length;//堆在数组里的长度
while (heapsize!=0){
swap(arr,0,--heapsize);//将头结点和尾结点交换,把最大值放最后
heapify(arr,0,heapsize);//保持树化
}
}
//插入逐步实现大根堆
public static void heapInsert(int[] arr, int curr) {
while (arr[curr]>arr[parent(curr)]){
swap(arr,curr,parent(curr));
curr=parent(curr);
}
}
//堆的大小为size即数组0~size-1
//维持index结点所在子树为大根堆 (父结点大)
//如果index位置变化也可以用此函数维持大根堆
//size为数组长度,而不是最后一个索引,是最后一个堆位置索引值+1
public static void heapify(int[] arr, int index, int size) {
while (left(index)<size){
//当存在左孩子节点
//判断两个子结点的值大小,得到最大值的索引
//如果存在右节点且大于左结点,返回右节点值
//否则返回左节点值
int largest=right(index)<size&&arr[right(index)]>arr[left(index)]
?right(index)
:left(index);
//将孩子中大值和index父结点比较,得到最大值索引从而交换让父结点得到最大值
largest=arr[largest]>arr[index]?largest:index;
if (largest == index) {
break;
}
swap(arr,index,largest);
index=largest;
}
}
//求父结点
public static int parent(int i) {
return (i-1)/2;
}
//求左孩子
public static int left(int i) {
return 2*i+1;
}
//求右孩子
public static int right(int i) {
return 2*i+2;
}
//交换
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
