Java代码为例讲解堆的性质和基本操作以及排序方法
作者:林寿山 发布时间:2021-08-27 05:32:25
标签:Java,堆
堆的性质
堆是一棵完全二叉树,实际中可以通过一个数组来实现,它最重要的一个性质是:任意节点都小于(大于)等于其子节点。将根节点最小的堆称为最小堆,根节点最大的堆称为最大堆。下图给出了一个最大堆的示例及其数组表示,可以直观地看出每个节点都比它的孩子们都要大。
在上图中可以看到,完全二叉树的节点可以从根节点编号为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);
}
}
}
0
投稿
猜你喜欢
- Web基础和HTTP协议┌─────────┐┌─────────┐
- 引言♀ 小AD:明哥,我终于出了这口恶气了。♂ 明世隐:打爽了是吧。♀ 小AD:那必须的,打十盘我赢九盘,我随意。♂ 明世隐:那小朋友不是搞
- 背景环境已学习java基础,html,css,js,jquery,bootstrap,layui,maven,servlet和jsp,刚进入
- 前言本文主要讲述如何使用Java + FFmpeg实现对视频文件的信息提取、码率压缩、分辨率转换等功能;之前在网上浏览了一大圈Java使用F
- 原因每次使用idea新建项目,就会在默认的c盘下的一个maven仓库中下载jar包,可是我自己指定maven仓库不是这个。如何让idea在新
- SlidingDrawer效果想必大家也见到过,它就是1.5模拟器上进入应用程序列表的效果。下面是截图一、简介 SlidingDr
- 多播委托简介每一个委托都是继承自MulticastDelegate,也就是每个都是多播委托。带返回值的多播委托只返回最后一个方法的值多播委托
- 近期很多小伙伴问我,为何启动项目的时候Spring 或 Spring MVC资源文件找不到
- 一、背景1.1、前言当我们写好代码并测试功能符合要求时,有可能每天都要执行这个程序(比如我写了一个爬虫脚本,每天定时运行获取我想看的小说更新
- java 线程锁在Java线程中运用synchronized关键字来达到同步的 synchronized可以锁方法,锁类,锁对象,锁代码块方
- 一:问题描述 在已经root过的android设备下,app执行一个linux命令,app需要获取su权限,在某些a
- 一、前言尽管Unity有一个像样的脚本编辑器(Mono),但很多人喜欢使用另一个编辑器。这篇短文解释了如何更改脚本编辑器,并介绍了Mono的
- 1.导入jar包: <!--jmsTemplate--> <dependency> <
- 前言如今多线程编程已成为了现代软件开发中的重要部分,而并发编程中的线程同步问题更是一道难以逾越的坎。在Java语言中,synchronize
- 本文实例为大家分享了java swing实现简单计算器界面的具体代码,供大家参考,具体内容如下已经学习了一部分的swing知识,现在综合运用
- 参考:How to catch an Exception from a threadIs there a way to make Runna
- 1、LongAdder由来LongAdder类是JDK1.8新增的一个原子性操作类。AtomicLong通过CAS算法提供了非阻塞的原子性操
- 环境搭建spring boot的简介以往我们开发时用到spring总是避免不了繁琐的配置,例如我们要配置一个数据库连接,可能需要以下几步:1
- 堆排序介绍:堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并
- 简介MyBatis-Plus (opens new window)(简称 MP)是一个 MyBatis (opens new window)