堆排序原理

程序员文章站 2022-03-12 23:30:58

...

堆排序原理（heapsort）

概述

堆排序时间复杂度为O(nlogn),使用一个数组进行存储。堆分为最大堆与最小堆

最大堆满足的条件

A[PARENT(i)]>=A[i]

最小堆满足的条件

A[PARENT(i)]<=A[i]

堆是一个数组，可以被看成一个近似的完全二叉树。以(a)二叉树和(b)数组形式展现的一个最大堆。二叉树结点上方的数字是它在数组中相应的下标。

堆排序原理

A[i] 的左节点为A[2*i]

A[i]的右节点为A[2*i+1]

建立最大堆

在无序数组自底向上建立最大堆,先代码后面有图。

public static void main(args[]String){
   int []A=new int[];
    int length=A.length();
    //(length/2)+1 是二叉树中最小的叶子节点   叶子节点不需要进行调整
    for(int i=length/2;i>-1;i--){
    	adjustMaxTree（A[i],i）;
    }
}

adjustMaxTree(int value,int index){
//如果 该节点为叶子节点则不需要调整
if(index>A.length()/2)
	return ;
  int largest=value;
  //如果左子节点大于A[index] 则值交换，并对左节点进行调整
  if(largest<A[index*2]){
      largest=A[index*2];
      A[index*2]=A[index];
      A[index]=largest;
      adjustMaxTree(A[index*2],index*2);
  }
    //如果右子节点大于A[index] 则值交换，并对右节点进行调整
 
   if(largest<A[index*2+1]){
      largest=A[index*2+1];
      A[index*2+1]=A[index];
      A[index]=largest;
       adjustMaxTree(A[index*2+1],index*2+1);
      
  }
    
}

堆排序原理