共计 4677 个字符,预计需要花费 12 分钟才能阅读完成。
写在后面:
大家好,我是时光。
明天给大家带来的是排序算法中的堆排序,这种排序跟二叉树相干。
我采纳图解形式解说,争取写透彻。话不多说,开始!
思维导图:
1,堆排序概念
堆排序 (Heapsort)
是指利用堆这种数据结构所设计的一种排序算法。沉积是一个近似齐全二叉树的构造,并同时满足沉积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
相干概念:
1.1,二叉树
特色:每个节点最多只有 2 个子节点(不存在度大于 2 的节点)
1.2,满二叉树
满二叉树:
叶子节点全副都在最底层;
除叶子节点外,每个节点都有左右孩子;
1.3,齐全二叉树
齐全二叉树:
叶子节点全副都在最底的两层;
最初一层只短少左边的叶子节点,右边肯定有叶子节点;
除了最初一层,其余层的节点个数均达到最大值;
1.4,最大堆和最小堆
最大堆:堆顶是整个堆中 最大元素
最小堆:堆顶是整个堆中 最小元素
2,算法思路
咱们先搞清楚这个堆排序思维,先把逻辑搞清楚,不焦急写代码。
咱们首先有一个无序数组,比方说
int[] arr={4,2,8,0,5,7,1,3,9};
既然用到堆,必定先要将数组构建成二叉堆。须要对数组从小到大排序,则构建成最大堆;须要对数组从小到大排序,则构建成最小堆。
2.1,第一个步骤,初始化堆
咱们先来看看数组是如何存储二叉树的
留神:这里思考的以后节点,必须是齐全二叉树的 非叶子节点。并且节点的左孩子和右孩子必须小于数组长度,所以前面须要增加限度条件。
看到上图中的公式,咱们明确了数组是能够存储齐全二叉树,同时保留节点之间的关系。以上述数组为例
那么存储好之后,如何将二叉树构建成二叉堆呢?持续往下看
以这个图为例,咱们以最大堆举例,若要构建二叉堆,则 A 要比 B 和 C 都大,B 要比 D 和 E 都大,C 要比 F 和 G 都大。也就是说父节点要比子节点都大才行。
在这个图中,显著不满足最大堆的要求。咱们先拿序号为 3,7,8 的三个节点来钻研,i= 3 的节点比 i = 7 和 i = 8 的节点都小,所以须要替换地位。留神此图是从 0 开始,也就是模仿数组下标从 0 开始。
怎么替换呢?很简略。咱们看节点 0,设为以后节点index
,那么它的lchild=index*2+1
,它的rchild=index*2+2
;留神下标从 0 开始。
// 初始化堆
public static void HeapAdjust(int[] arr,int index,int len){
// 先保留以后节点的下标
int max = index;
// 保留左右孩子数组下标
int lchild = index*2+1;
int rchild = index*2+2;
// 开始调整,左右孩子下标必须小于 len,也就是确保数组不会越界
if(lchild<len && arr[lchild] > arr[max]){max=lchild;}
if(rchild<len && arr[rchild] > arr[max]){max=rchild;}
// 若产生了替换,则 max 必定不等于 index 了。此时 max 节点值须要与 index 节点值替换,下面替换索引值,这里替换节点值
if(max!=index){int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// 替换完之后须要再次对 max 进行调整,因为此时 max 有可能不满足最大堆
HeapAdjust(arr,max,len);
}
}
下面代码很好了解,两头的两个 if 语句就是替换节点索引值,只有有一个孩子节点大于 index
,就须要进行替换。若父节点index
比两个孩子节点都大,那么就不须要替换了。
最初面的 if 语句是替换节点值,咱们晓得,只有 index
与lchild
和 rchild
有替换,则 index
肯定不等于 max
了!
那为什么最初的 if
语句外面还要加上一个递归写法呢?咱们举个例子就明确了,还是以上述数组为例,先看看一轮替换之后的样子:
第一次替换,0 与 9 替换,此时 Index=9;
第二次替换,8 曾经比 7 和 1 都大了,此时不须要替换;
第三次替换,2 与 9 替换,此时
Index
=9;
第四次替换,4 与 9 替换,此时
Index
=9,第一轮替换到此结束。
一轮完结后,有小伙伴儿曾经发现问题了,尽管 9 胜利的成为最大堆的堆顶元素,然而上面的其余元素并不满足最大堆的要求,比如说左下角的元素 2, 元素 3, 元素 0 等这种二叉树就不满足,元素 4,元素 2,元素 5 也不满足。
因而在替换节点值这个步骤里,咱们须要进行递归操作,替换完之后再次对 index
进行堆调整:
// 若产生了替换,则 max 必定不等于 index 了。此时 max 节点值须要与 index 节点值替换,下面替换索引值,这里替换节点值
if(max!=index){int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// 替换完之后须要再次对 max 进行调整,因为此时 max 有可能不满足最大堆
HeapAdjust(arr,max,len);
}
堆排序的测试:
// 堆排序
public static int[] HeapSort(int[] arr){
int len=arr.length;
/**
* 第一步,初始化堆,最大堆,从小到大
* i 从齐全二叉树的第一个非叶子节点开始,也就是 len/2- 1 开始(数组下标从 0 开始)
*/
for(int i=len/2-1;i>=0;i--){HeapAdjust(arr,i,len);
}
// 打印堆顶元素,应该为最大元素 9
System.out.println(arr[0]);
return arr;
}
上述代码就是从齐全二叉树的第一个非叶子节点开始调换,还顺便打印堆顶元素,此时应为 9;
至此,第一个步骤,初始化堆实现,最初的后果应该为下图:
2.2,第二个步骤,堆排序
堆排序的过程就是将堆顶元素(最大值或者最小值)与二叉堆的最开端叶子节点进行调换,不停的调换,直到二叉堆的程序变成从小到大或者从大到小,也就实现了咱们的目标。
咱们这里以最大堆的堆顶元素(最大元素)为例,最初调换的后果就是从小到大排序的后果。
第一次替换,咱们间接将元素 9 与元素 0 替换,此时堆顶元素为 0,设以后节点
index
=0;
这时,咱们须要将剩下的元素(排除元素 9)进行堆排序,直到上面这个后果:
代码:
/**
* 第二步,替换堆顶(最大)元素和二叉堆的最初一个叶子节点元素。目标是替换元素
* i 从二叉堆的最初一个叶子节点元素开始,也就是 len- 1 开始(数组下标从 0 开始)
*/
for(int i=len-1;i>=0;i--){int temp=arr[i];
arr[i]=arr[0];
arr[0]=temp;
// 替换完之后须要从新调整二叉堆,从头开始调整,此时 Index=0
HeapAdjust(arr,0,i);
}
留神:这里有个小细节问题,后面咱们写的初始化堆办法有三个参数,别离是数组 arr
,以后节点index
以及数组长度len
,如下:
HeapAdjust(int[] arr,int index,int len)
那么,为何不间接传入两个参数即可,数组长度间接用 arr.length
示意不就行了吗?初始化堆的时候是能够,然而前面在替换堆顶元素和开端的叶子节点时,在对剩下的元素进行排序时,此时的数组长度可不是 arr.length
了,应该是变动的参数i
,因为替换之后的元素(比方 9)就不计入堆中排序了,所以须要 3 个参数。
咱们进行第二次替换,咱们间接将元素 8 与元素 2 替换,此时堆顶元素为 2,设以后节点
index
=2;
这时,咱们须要将剩下的元素(排除元素 9 和 8)进行堆排序,直到上面这个后果:
到这个时候,咱们再反复上述步骤,一直调换堆顶和最开端的节点元素即可,再一直地对剩下的元素进行排序,最初就能失去从小到大排序好的堆了,如下图所示,这就是咱们想要的后果:
3,残缺代码
import java.util.Arrays;
public class Head_Sort {public static void main(String[] args) {int[] arr={4,2,8,0,5,7,1,3,9};
System.out.println("排序前:"+Arrays.toString(arr));
System.out.println("排序后:"+Arrays.toString(HeapSort(arr)));
}
// 堆排序
public static int[] HeapSort(int[] arr){
int len=arr.length;
/**
* 第一步,初始化堆,最大堆,从小到大。目标是对元素排序
* i 从齐全二叉树的第一个非叶子节点开始,也就是 len/2- 1 开始(数组下标从 0 开始)
*/
for(int i=len/2-1;i>=0;i--){HeapAdjust(arr,i,len);
}
/**
* 第二步,替换堆顶(最大)元素和二叉堆的最初一个叶子节点元素。目标是替换元素
* i 从二叉堆的最初一个叶子节点元素开始,也就是 len- 1 开始(数组下标从 0 开始)
*/
for(int i=len-1;i>=0;i--){int temp=arr[i];
arr[i]=arr[0];
arr[0]=temp;
// 替换完之后须要从新调整二叉堆,从头开始调整,此时 Index=0
HeapAdjust(arr,0,i);
}
return arr;
}
/**
* 初始化堆
* @param arr 待调整的二叉树(数组)
* @param index 待调整的节点下标,二叉树的第一个非叶子节点
* @param len 待调整的数组长度
*/
public static void HeapAdjust(int[] arr,int index,int len){
// 先保留以后节点的下标
int max = index;
// 保留左右孩子数组下标
int lchild = index*2+1;
int rchild = index*2+2;
// 开始调整,左右孩子下标必须小于 len,也就是确保 index 必须是非叶子节点
if(lchild<len && arr[lchild] > arr[max]){max=lchild;}
if(rchild<len && arr[rchild] > arr[max]){max=rchild;}
// 若产生了替换,则 max 必定不等于 index 了。此时 max 节点值须要与 index 节点值替换,下面替换索引值,这里替换节点值
if(max!=index){int temp=arr[index];
arr[index]=arr[max];
arr[max]=temp;
// 替换完之后须要再次对 max 进行调整,因为此时 max 有可能不满足最大堆
HeapAdjust(arr,max,len);
}
}
}
运行后果:
4,算法剖析
4.1,工夫复杂度
建堆的时候初始化堆过程 (HeapAdjust)
是堆排序的要害,工夫复杂度为O(log n)
,上面看堆排序的两个过程;
第一步,初始化堆,这一步工夫复杂度是O(n)
;
第二步,替换堆顶元素过程,须要用到 n - 1 次循环,且每一次都要用到(HeapAdjust)
,所以工夫复杂度为((n-1)*log n)~O(nlog n)
;
最终工夫复杂度:O(n)+O(nlog n)
,后者复杂度高于前者,所以 堆排序的工夫复杂度为 O(nlog n);
4.2,空间复杂度
空间复杂度是O(1)
,因为没有用到额定开拓的汇合空间。
4.3,算法稳定性
堆排序是不稳固的,比方说二叉树[6a,8,13,6b],(这里的 6a 和 6b 数值上都是 6,只不过为了区别 6 所以这样)通过堆初始化后以及排序过后就变成[6b,6a,8,13];可见堆排序是不稳固的。