今天小编给大家分享一下Java如何利用完全二叉树创建大根堆和小根堆的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。
大根堆：每个结点的值不大于他的父亲结点的值
分析如下：
假设对{ 27,15,19,18,28,34,65,49,25,37 }这样一个集合的数据创建成堆；
代码如下：
计算
安全
数据库
网络和加速
企业服务
//建立大根堆
public class TestHeap{
public int[] array;
public int usedSize;//当前有效数组长度
public TestHeap(){
this.array = new int[10];
this.usedSize = 0;
}
//初始化数组
public void InitArray(int[] arrayClone){
array = Arrays.copyOf(arrayClone, arrayClone.length);
usedSize = array.length;
}
//创建大根堆
public void createHeap(){
for(int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--){
adjustment(parent, usedSize);
}
}
//调整
public void adjustment(int parent, int len){
//左子树结点下标
int child = parent * 2 + 1;
//调整
while(child < len){
//先判断有没有右孩子，如果右，找出最大值
if(child + 1 < len && array[child] < array[child + 1]){
child++;//如果右子树大，child++就指向他，如果左子树大，就不用管,直接进行下一步判断交换
}
//若左右子树的最大值大于父亲结点则交换
if(array[child] > array[parent]){
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else{
break;
}
}
}
//交换
public void swap(int[] array, int child, int parent){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}
}小根堆：每个结点的值不小于他的父亲结点的值
分析与大根堆类似，只是比较出更小的进行替换
代码如下：
//建立大根堆
public class TestHeap{
public int[] array;
public int usedSize;//当前有效数组长度
public TestHeap(){
this.array = new int[10];
this.usedSize = 0;
}
//初始化数组
public void InitArray(int[] arrayClone){
array = Arrays.copyOf(arrayClone, arrayClone.length);
usedSize = array.length;
}
//创建大根堆
public void createHeap(){
for(int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--){
adjustment(parent, usedSize);
}
}
//调整
public void adjustment(int parent, int len){
//左子树结点下标
int child = parent * 2 + 1;
//调整
while(child < len){
//先判断有没有右孩子，如果右，找出最小值
if(child + 1 < len && array[child] > array[child + 1]){
child++;//如果右子树小，child++就指向他，如果左子树小，就不用管,直接进行下一步判断交换
}
//若左右子树的最大值小于父亲结点则交换
if(array[child] < array[parent]){
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else{
break;
}
}
}
//交换
public void swap(int[] array, int child, int parent){
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
}
}以上就是“Java如何利用完全二叉树创建大根堆和小根堆”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
