一、堆的相关概念1 .堆是完全二叉树。 也就是说,除了最后一层,其他层都满了,最后一层从左向右依次有元素。 如下图所示。
堆通过数组实现,图中的下标是数组的下标,它对应于数组[5、1、7、2、8、6、3、9、4],节点I的左子节点为2i 1节点,右子节点为2i 2,母节点为[I-1]/2
2 .大顶堆和小顶堆大顶堆:当堆中每个非叶节点的值大于或等于其子节点的值时,将该堆称为大顶堆。小顶堆:如果堆中所有非叶节点的值都小于或等于其子节点的值,则此堆称为小顶点堆。
上层堆和下层堆不需要左右子节点的值大小。
二、堆栈排序的基本思想1 .根据大顶堆和小顶堆的概念,可以看出它们的根节点对应于整个堆的最大值和最小值。
2 .将长度为n的要排序数组调整为大的顶堆(或小的顶堆),替换数组的第一个和最后一个元素,将最大值(最小值)放在最后。
3 .继续将数组的前n-1位调整为高位堆或低位堆,将数组的第一个元素与第n-1个元素进行置换,将下一个大的值、下一个小的值配置在对应的位置,通过这样的方法重复调整和置换直到调整对象元素成为一个为止。
4 .最后得到升序(降序)的数列。
三、代码实现分析1 .堆调大顶堆(以大顶堆为例)1)方法概述一个堆调大顶堆的过程比较复杂。函数:其中定义了一个函数,使用该函数可以将堆中非叶节点作为根节点的子树调整为部分大的顶点堆。
思路:从最后一个叶节点开始调整,调整该节点的上一个节点,即数组的上一个元素,直到调整为堆栈的整个根节点(数组的第一个元素)。优点:这确保了每次调整节点时,该节点左侧和右侧的子树都是大堆的。
要点:调节该非叶节点I是放在与左右子节点中的最大值相同的节点上,其中如果该节点是最大值,则以该节点为根节点的树是大山,不需要调整如果该节点不是最大值,则它可能会替换左侧和右侧子节点的最大值,并影响左侧和右侧子树是否仍然是大山。 在这种情况下,需要进一步调整左右子树。 调整方法与前述相同。 直到调整为叶节点为止,以非叶节点I为根节点的树成为大山。
33558 www.Sina.com/: arr.length/2-1。
)2)以图解ARR=[5、1、7、2、8、6、3、9、4]为例:
arr.length/2 - 1=3,第一个飞行噪声索引为3。 更换后:
将索引调整为2 :不更改
将索引调整为1 :
这里左边的树因为交换没有填满大山顶的山,需要调整。
索引为0时:
调节其左边的树:
索引为4的是叶节点,结束调整。
索引为0的节点调节结束后,调节结束,形成大堆。
(3)代码调节节点函数:
对于以/** *为根节点树,调整对象的数组* @param arr、调整对象的数组* @param i、非叶节点在数组内的位置* @param length是调整对象的树的长度第**I个节点的左侧的子节点publicstaticvoidadjustheap (int [ ] arr,int i,int length ) { int temp=arr[i]; //先取出当前元素的值,临时变量//调整开始for(intindex=I*21; 索引长度; 索引=索引*21 )查找if (索引1 length arr [索引] arr [索引1 ] )//左子节点和右子节点的最大索引值; } if (arr [索引] temp ) /子节点大于当前节点的值arr [ I ]=arr [索引]; arr[index]=temp; I=索引; //i指向索引,持续循环比较,大顶(else ) break; } } publicstaticvoidmain (string [ ] args ) int [ ] arr={ 5,1,7,2,8,6,3,9,4 }; //使整个堆成为大的顶堆for (inti=arr.length/2 -
1; i >= 0; i--) { adjustHeap(arr, i, arr.length); } } 2.堆排序算法1.直接嵌套循环(不推荐)
public static void heapSort(int[] arr){ System.out.println("堆排序"); for(int length = arr.length;length > 1;length--){ //调节成大顶堆 for(int i = length/2-1;i>=0;i--){ adjustHeap(arr, i ,length); } int temp = arr[0]; arr[0] = arr[length - 1]; arr[length - 1] = temp; } }调节完成后,进行交换,再调节的短一个的数组(length–),此种方法容易理解,但耗时很大。
2.从0开始调节
我们注意到从第二次开始调节开始(下图为第二次调节开始时),根节点的左右子树都满足大顶堆的概念,无需进行从下至上的排序,直接从根节点开始调节即可。
代码: