相关博客:
一、堆:
1、什么是堆:
堆是一种特殊的树,它满足需要满足两个条件:
(1)堆是一种完全二叉树,也就是除了最后一层,其他层的节点个数都是满的,最后一个节点都靠左排列。
(2)堆中每一个节点的值都必须大于等于(或小于等于)其左右子节点的值。
对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作“小顶堆”。
2、堆的实现:
用数组来存储完全二叉树是非常节省内存空间的,因为我们不需要存储左右子节点的指针,单纯通过数组的下标,就可以找到一个节点的子节点和父节点。
从图中我们可以看到,数组中下标为 i 的节点的左子节点,就是下标为 i∗2 的节点,右子节点就是下标为 i∗2+1的节点,父节点就是下标为i/2的节点。
3、堆的核心操作:
(1)往堆中插入一个元素:
我们新插入一个元素之后,堆可能就不满足堆的特性了,就需要进行调整,让其重新满足堆的特性,即堆化(heapify),堆化非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换。所以分为两种,从下往上 和 从上往下。
①从下往上堆化:
例如:在已经建好的堆中插入值为“22”的结点,这时候就需要重新调整堆结构,过程如下:
Java代码实现:
public class Heap {
private int[] a;//数组,从下标1开始存储数据
private int n;//堆可以存储的最大数据个数
private int count;//堆中已经存储的数据个数
public Heap(int capacity){
a = new int[capacity+1];
n=capacity;
count = 0;
}
//1、插入数据,并从下往上堆化
public void insert(int data){
if(count>=n) return;//堆满了
++count;
a[count]=data;
int i = count;
while(i/2>0 && a[i]>a[i/2]){
swap(a,i,i/2);
i=i/2;
}
}
private void swap(int[] array, int i, int j) {
int temp=array[j];
array[j]=array[i];
array[i]=temp;
}
}
(2)从堆中删除堆顶元素:
删除步骤:把最后一个节点放到堆顶,然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的,互换两个节点,并且重复进行这个过程,直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。
例如:删除堆顶的“33”结点,删除步骤如下:
Java代码实现:
public void removeMax(){
if(count ==0) return;
a[1]=a[count];
--count;
heapity(a,count,1);
}
//2、自上往下堆化
private void heapity(int[] a2, int n, int i) {
while(true){
int MaxPos=i;
if(i*2<=n && a[i]<a[i*2]) MaxPos=i*2;
if(i*2+1<=n && a[MaxPos]<a[i*2+1]) MaxPos=i*2+1;
if(MaxPos==i) break;
swap(a, i, MaxPos);
i=MaxPos;
}
}
一个包含 n个节点的完全二叉树,树的高度不会超过 log2n。堆化的过程是顺着节点所在路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化,所以在堆中插入一个元素和删除堆顶元素的时间复杂度都是O(logn)。
二、堆排序:
1、算法原理:
堆排序是指利用堆这种数据结构进行排序的一种算法。
(1)排序过程中,只需要个别临时存储空间,所以堆排序是原地排序算法,空间复杂度为O(1)。
(2)堆排序的过程分为建堆和排序两大步骤。建堆过程的时间复杂度为O(n),排序过程的时间复杂度为O(nlogn),所以,堆排序整体的时间复杂度为O(nlogn)。
(3)堆排序不是稳定的算法,因为在排序的过程中,存在将堆的最后一个节点跟堆顶节点互换的操作,所以可能改变值相同数据的原始相对顺序。
2、建堆:
(1)第一种是实现思路:借助前面的,在堆中插入元素的思路。将要排序的数组从前往后处理,依次到插入堆中,并且每次都从下往上进行堆化。
(2)第二种实现实现思路:从后往前处理数组,并且每个数据都是从上往下堆化。也就是从二叉树中第一个非叶子节点开始开始堆化,因为叶子节点往下堆化只能自己跟自己比较。如下图:
Java代码实现:
//3、第二种堆化的方法:
public void buildHeap(int[] a,int n){
for(int i=n/2;i>=1;--i){
heapity(a,n,i);
}
}
//2、自上往下堆化
private void heapity(int[] a, int n, int i) {
while(true){
int MaxPos=i;
if(i*2<=n && a[i]<a[i*2]) MaxPos=i*2;
if(i*2+1<=n && a[MaxPos]<a[i*2+1]) MaxPos=i*2+1;
if(MaxPos==i) break;
swap(a, i, MaxPos);
i=MaxPos;
}
}
3、排序:
(1)建堆:建堆结束后,数组中的数据已经是按照大顶堆的特性组织的。数组中的第一个元素就是堆顶。
(2)取出最大值(类似删除操作):将堆顶元素a[1]与最后一个元素a[n]交换,这时,最大元素就放到了下标为n的位置。
(3)重新堆化:交换后新的堆顶可能违反堆的性质,需要重新进行堆化。
(4)重复(2)(3)操作,直到最后堆中只剩下下标为1的元素,排序就完成了。
Java代码实现:
//4、排序,n表示数据的个数。
public void sort(int[] a,int n) {
buildHeap(a,n);
int k=n;
while(k>1){
swap(a, 1, k);
--k;
heapity(a,k,1);
}
}
本篇博客主要参考《极客时间》王争的《数据结构与算法之美》专栏第28节。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114617.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...