Java代码为例讲解堆的性质和基本操作以及排序方法
作者:林寿山 时间:2021-08-27 05:32:25
堆的性质
堆是一棵完全二叉树,实际中可以通过一个数组来实现,它最重要的一个性质是:任意节点都小于(大于)等于其子节点。将根节点最小的堆称为最小堆,根节点最大的堆称为最大堆。下图给出了一个最大堆的示例及其数组表示,可以直观地看出每个节点都比它的孩子们都要大。
在上图中可以看到,完全二叉树的节点可以从根节点编号为1开始按顺序排列,对应数组A中的索引(注意此处下标是从1开始的)。给定一个节点i,我们很容易可以得到它的左孩子是2i,右孩子是2i+1,父节点是i/2
堆的基本操作
堆有两种基本操作(下面以最小堆为例):
插入元素k:直接将k添加到数组最后,然后向上冒泡(bubble-up)调整堆。向上冒泡操作:将要调整的元素与其父节点比较,如果大于其父节点则交换,直到恢复堆的性质。
提取最值:最值即根元素。然后将其删除,令根元素=最后的叶子结点元素,然后从根元素开始向下冒泡(bubble-down)调整堆。向下冒泡操作:每次应该从要调整节点,其左右孩子一共三个节点中选择最小的子节点来交换(如果最小就是其本身就不用交换),直到恢复堆的性质。
实际中经常需要将一个包含n个元素无序数组建立成堆,下面的Heap类中的构造方法将展示如何通过_bubbleDown向下冒泡调整来建堆。堆实质上是一棵完全二叉树,树高总为lognlogn,每种基本操作的耗时操作都在于冒泡调整以满足堆的性质,因此它们的时间复杂度都是O(nlogn)O(nlogn)。
Java示例:
//上浮
public void swim(int k){
while(k/2>=1 && less(pq[k/2],pq[k])){
exch(pq,k/2,k);
k=k/2;
}
}
//下沉
private void sink() {
int k=1;
while(2*k<N){
int j=2*k;
if(less(pq[j],pq[j+1])) j++;
if(less(pq[k],pq[j])) exch(pq,k,j);
else break;
k = j;
}
}
堆排序实现原理
分为两步:
1.把数组排成二叉堆的顺序
2.调换根节点和最后一个节点的位置,然后对根节点进行下沉操作。
实现:
可能我的代码和上面的动画略有出入,不过基本原理差不多。
public class HeapSort extends BaseSort {
private int N;
@Override
public void sort(Comparable[] a) {
N =a.length-1;
int k = N/2;
while(k>=1){
sink(a,k);
k--;
}
k = 1;
while(k<=N){
exch(a,k,N--);
sink(a,k);
}
}
}
标签:Java,堆
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
java实战之猜字小游戏
2022-03-31 14:48:01
![](https://img.aspxhome.com/file/2023/7/63487_0s.png)
RocketMQ生产者一个应用不能发送多个NameServer消息解决
2022-05-18 15:56:11
![](https://img.aspxhome.com/file/2023/7/69687_0s.png)
Java中BigDecimal的舍入模式解析(RoundingMode)
2021-10-16 15:28:16
SpringBoot分离打Jar包的两种配置方式
2023-01-30 09:06:59
java微信公众号支付开发之现金红包
2023-09-01 17:28:38
![](https://img.aspxhome.com/file/2023/3/66163_0s.jpg)
Java面向对象基础知识之抽象类和接口
2023-02-10 03:02:58
java实现打砖块小游戏
2021-07-26 14:47:11
java中的this引用及对象构造初始化
2023-03-07 09:38:17
![](https://img.aspxhome.com/file/2023/6/60996_0s.png)
java实现鲜花销售系统
2023-08-29 20:23:42
![](https://img.aspxhome.com/file/2023/3/58333_0s.jpg)
Springboot使用POI实现导出Excel文件示例
2021-09-22 08:18:31
![](https://img.aspxhome.com/file/2023/8/61398_0s.jpg)
SpringBoot2使用Jetty容器操作(替换默认Tomcat)
2023-11-24 01:17:15
![](https://img.aspxhome.com/file/2023/9/59779_0s.jpg)
jQuery.event.trigger()的简单解释
2023-05-24 03:41:37
![](https://img.aspxhome.com/file/2023/2/62232_0s.png)
java调用微信现金红包接口的心得与体会总结
2022-12-22 19:55:12
JAVA包装类及自动封包解包实例代码
2022-10-23 13:28:54
解析C# 程序结构
2021-11-15 05:22:59
SpringBoot集成mybatis实例
2023-03-09 16:57:01
SpringBoot FreeWorker模板技术解析
2023-08-09 09:14:39
![](https://img.aspxhome.com/file/2023/6/57826_0s.png)
spring Bean创建的完整过程记录
2022-04-14 03:57:51
![](https://img.aspxhome.com/file/2023/0/71180_0s.jpg)
Java应用多机器部署解决大量定时任务问题
2023-10-28 17:07:17
![](https://img.aspxhome.com/file/2023/1/58691_0s.png)
mybatis源码解读之executor包懒加载功能
2022-09-17 00:28:05