Java数据结构与Java算法学习Day06---堆(简略笔记记录)
创始人
2024-03-22 06:00:18
0

目录

一、堆 96

1.1堆的定义 96 

1.2堆的API设计 97

1.3堆---堆的插入方法 98

1.4堆---堆的删除最大元素方法 99

1.5堆---堆的测试 100

二、堆排序 101

2.1堆排序  101


一、堆 96

1.1堆的定义 96 

堆实际上也是利用数据结构实现的,用树实现的特殊结构,也是树的一种。

堆的特性:

特性1, 堆:完全二叉树

 

特性2,通过数组实现完全二叉树的表达:(利用数组来实现堆的这个二叉树)

下面的图就是表现的是上面完全二叉树的形式。

 

注:

1、已知结点的索引位置,便可知道其父结点和其两个子节点的索引位置。前提是完全二叉树

如果一个结点的位置为k,则它的父结点的位置为(k/2),它的子结点的位置为2k和(2k+1)。

例如:结点p,则其父结点索引位置为2,子结点的位置为8和9

2、根据索引的位置变换,实现结点层数的变化。

向上移动一层,就将k值变为原来的一半即k/2,如果想向下移动一层,就将k值变为原来的二倍(2k)或者二倍基础上再加1(2k+1)。

特性3,同一个结点下的两个子节点没有大小区分。

父结点的值要比其两个子结点的值大。 

二叉查找树:左子结点小于右子结点。.

堆:左子结点和右子结点之间没有大小区分。

1.2堆的API设计 97

这个地方错误,修改为:Heap>

根据特性3,可以知道这个堆是个有序的树,索引需要这个Comparable,来提供比较规则

本部分代码的实现在/heap/Heap中

1.3堆---堆的插入方法 98

堆的插入方法的实现的原理见文档P4。

1.4堆---堆的删除最大元素方法 99

最大元素:实际上就是堆的第一个值,即根结点就是最大的元素

根结点的删除的原理图请查看文档P6。

其中最不好处理的问题是:删除掉最大元素后,谁来替换最大元素的位置呢?

第一步:

虽然堆的特性是结点比其两个子结点大,但是并不知道哪个结点大。在这个地方采取一个巧的方法。将根结点先于左子树的最后一个元素与根结点进行交换。

第二步:

进行交换后,再将T进行删除。删除之后,此时的堆已经变成没有序了。需要对堆的序进行调整。

第三步:

通过对堆的下沉进行调整,使其变为有序。

 

 

 

代码部分的实现在/heap/Heap中

1.5堆---堆的测试 100

本部分代码实现在/test/HeapTest

二、堆排序 101

2.1堆排序  101

对堆的元素大小进行排序处理。

实现将原数据数组,构造成堆heap。102

实现堆的下沉方法。103 

根据待排序的数组来构造成一个堆,完成堆排序 103

测试代码 105

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...
有效的括号 一、题目 给定一个只包括 '(',')','{','}'...
【Ctfer训练计划】——(三... 作者名:Demo不是emo  主页面链接:主页传送门 创作初心ÿ...