彻底搞定堆排序:二叉堆
作者:程序dunk 时间:2022-12-06 23:24:15
二叉堆
什么是二叉堆
二叉堆本质上是一种完全二叉树,它分为两个类型
最大堆:最大堆的任何一个父节点的值,都大于等于它的左、右孩子节点的值(堆顶就是整个堆的最大元素)
最小堆:最小堆的任何一个父节点的值,都小于等于它的左、右孩子节点的值(堆顶就是整个堆的最小元素)
二叉堆的根节点叫做堆顶
二叉堆的基本操作
插入节点
删除节点
构建二叉堆
这几种操作都基于堆的自我调整,所谓堆自我调整,就是把一个不符合堆的完全二叉树,调整成一个堆,下面以最小堆为例。
插入
插入节点0的过程
删除
删除节点的过程和插入的过程刚好相反,所删除的是处于堆顶的节点。例如删除1
为了维持完全二叉树的结构,把堆的最后一个元素临时补充到堆顶
删除原来10的位置
对堆顶的节点10执行下沉操作
构建
构建二叉堆,也就是把一个无序的完全二叉树调整为二叉堆,本质就是让所有的非叶子节点一次下沉
二叉堆代码实现
二查堆虽然是一颗完全二叉树,但它的存储方式并不是链式的,而是顺序存储,换句话说,二叉堆的所有节点都存储在数组中
当父节点为parent时,左孩子为2 * parent + 1;右孩子为2 * parent + 2
/**
* @author :zsy
* @date :Created 2021/5/17 9:41
* @description:二叉堆
*/
public class HeapTest {
public static void main(String[] args) {
int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
Heap heap = new Heap(arr);
heap.upAdjust(arr);
System.out.println(Arrays.toString(arr));
arr = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
heap = new Heap(arr);
heap.buildHead();
System.out.println(Arrays.toString(arr));
}
}
class Heap {
private int[] arr;
public Heap(int[] arr) {
this.arr = arr;
}
public void buildHead() {
//从最后一个非叶子节点开始,依次下沉
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
downAdjust(arr, i, arr.length);
}
}
private void downAdjust(int[] arr, int parentIndex, int length) {
int temp = arr[parentIndex];
int childrenIndex = parentIndex * 2 + 1;
while (childrenIndex < length) {
//如果有右孩子,并且右孩子小于左孩子,那么定位到右孩子
if (childrenIndex + 1 < length && arr[childrenIndex + 1] < arr[childrenIndex]) {
childrenIndex++;
}
//如果父节点小于较小孩子节点的值,直接跳出
if (temp <= arr[childrenIndex]) break;
//无需交换,单向赋值
arr[parentIndex] = arr[childrenIndex];
parentIndex = childrenIndex;
childrenIndex = 2 * childrenIndex + 1;
}
arr[parentIndex] = temp;
}
public void upAdjust(int[] arr) {
int childrenIndex = arr.length - 1;
int parentIndex = (childrenIndex - 1) / 2;
int temp = arr[childrenIndex];
while (childrenIndex > 0 && temp < arr[parentIndex]) {
//单向赋值
arr[childrenIndex] = arr[parentIndex];
childrenIndex = parentIndex;
parentIndex = (parentIndex - 1) / 2;
}
arr[childrenIndex] = temp;
}
}
结果:
[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
[1, 5, 2, 6, 7, 3, 8, 9, 10]
来源:https://blog.csdn.net/qq_45796208/article/details/117094130
标签:堆排序,二叉堆
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
c# 图片加密解密的实例代码
2023-08-20 21:21:01
基于SPRINGBOOT配置文件占位符过程解析
2021-06-27 04:25:12
android BitmapFactory.Options使用方法详解
2023-05-04 08:50:20
android教程之使用popupwindow创建菜单示例
2023-01-24 22:08:10
对Java中JSON解析器的一些见解
2023-02-05 20:53:15
微服务间调用Retrofit在Spring Cloud Alibaba中的使用
2022-09-29 23:13:42
![](https://img.aspxhome.com/file/2023/0/75660_0s.png)
基于selenium-java封装chrome、firefox、phantomjs实现爬虫
2022-04-07 19:04:28
QT5实现简单的TCP通信的实现
2023-11-02 21:24:48
![](https://img.aspxhome.com/file/2023/1/105171_0s.png)
netty pipeline中的inbound和outbound事件传播分析
2023-08-27 06:57:00
![](https://img.aspxhome.com/file/2023/5/58285_0s.png)
c# 代理模式
2022-02-19 09:48:31
![](https://img.aspxhome.com/file/2023/3/107773_0s.gif)
Android中实现TCP和UDP传输实例
2021-11-08 14:19:59
![](https://img.aspxhome.com/file/2023/4/114294_0s.png)
C#如何通过probing指定dll寻找文件夹详解
2023-07-22 12:59:37
PowerShell 定时执行.Net(C#)程序的方法
2023-07-09 14:10:39
Spring Boot 集成Dubbo框架实例
2022-02-03 21:23:27
java笔记学习之操作符
2022-10-19 05:31:59
利用C#代码将html样式文件与Word文档互换的方法
2022-04-22 07:11:31
![](https://img.aspxhome.com/file/2023/2/94592_0s.png)
c++代码调试方式的几点建议
2023-07-05 05:31:35
Android网络连接判断与相关处理
2022-02-23 11:25:33
Java编程BigDecimal用法实例分享
2022-05-02 05:40:06
Android Bitmap和Drawable的对比
2021-11-16 06:03:41