堆排序-heapSort(代码实现-JAVA

前言:

二叉堆可以分钟两种形式,最大堆和最小堆。本文章实现的是最大堆。

最大堆性质:除了根节点以外的所有节点i都要满足 A[PARENT(i)]>=A[i];

最小堆性质:除了根节点以外的所有节点i都要满足A[PARENT(i)]<=A[i];

维护堆:maxHeapify是用于维护最大堆性质的重要过程

//n表示有多少个堆元素存储在数组种
public static void maxHeapify(int arr[],int i,int n){
  int largest=i;
  //左子节点
  int lson=i*2+1;
  //右子节点
  int rson=i*2+2;
  //如果左子节点不越界并且违背了最大堆的性质
  if(lson<n&&arr[lson]>arr[largest]){
	largest=lson;
  }
  if(rson<n&&arr[rson]>arr[largest]){
	largest=rson;
  }
  //如果当前的值不是最大值(即largest不等于当前节点的索引'i'),则进行节点值交换,将最大值交换到当前节点的位置
  if(largest!=i){
	int temp=arr[i];
	arr[i]=arr[largest];
	arr[largest]=temp;
  }
  //递归调用确保子树也满足最大堆性质
	maxHeapify(arr,largest,n)
}

建堆

我们可以通过自底向上的方法利用过程MAX-HEAPIFY把一个大小为n=A.length的数组转换成最大堆

public static void buildMaxHeap(int arr[],int n){
//选择 i = n/2 - 1 是因为在一个完全二叉树中，叶子节点占据了大部分的位置，而非叶子节点相对较少。最后一个非叶子节点的索引可以通过 (n-1)/2 得到
	for(int i=n/2-1;i>=0;i--){
		maxHeapify(arr,i,n);
	}
  //堆排序
  for(int i=n-1;i>0;i--){
	//交换堆顶元素和当前未排序部分的最后一个元素
	int temp=arr[i];
	arr[i]=arr[0];
	arr[0]=temp;
	//对交换后的堆进行维护
	maxHeapify(arr,0,i);
}

发明堆排序的人可真是个天才