今天学习了一下左式堆,总结一下。
一、左式堆定义:
具有,如下性质
1、父节点属性值小于子节点属性值;
2、堆中的任何节点,其左儿子的零路径长>=右儿子的零路径长;
的二叉树。
注:零路径长(npl)是指:从一个节点X开始到一个不具有两个儿子的Y节点的最短路径的长,可以看出有0个或者一个儿子的节点的npl=0,并且定义npl(null)=-1;
二、左式对的节点定义:
class Node<T> {
// 元素
T element;
// 左节点
Node<T> left;
// 右节点
Node<T> right;
// 零路径长
int npl;
public Node(T element) {
this(element, null, null);
}
public Node(T element, Node<T> left, Node<T> right) {
this.element = element;
this.left = left;
this.right = right;
this.npl = 0;
}
}
三、左式对的操作:
对于左式堆主要操作是“合并”,因为合并会破坏左式堆的特性,而insert、delete等操作,都会涉及到堆的合并,例如:delete根节点,相当于将一棵树边为了两个树,在将两棵树合并为一棵树。这里我们使用了一种递归的思想,若h1,h2本身是左式堆,则其子树也一定是左式堆,其子树的子树也一定是左式堆,一直退到树的每个叶子节点,都符合这个规则,那么我们合并时就可以从反方向思考,先形成一个个的小左式堆,然后在形成一棵大的左式堆。
四、左式堆定义代码:
public class LeftistHeap<T extends Comparable<T>> {
// 左式堆节点定义
private static class Node<T> {
// 元素
T element;
// 左节点
Node<T> left;
// 右节点
Node<T> right;
// 零路径长
int npl;
public Node(T element) {
this(element, null, null);
}
public Node(T element, Node<T> left, Node<T> right) {
this.element = element;
this.left = left;
this.right = right;
this.npl = 0;
}
}
private Node<T> root;
public LeftistHeap() {
this.root = null;
}
// 合并兩個左式堆
public void merge(LeftistHeap<T> rhs) {
if (rhs == null)
return;
root = merge(root, rhs.root);
rhs.root = null;
}
// 向左式堆中添加元素
public void insert(T element) {
root = merge(new Node<T>(element), root);
}
// 找寻左式堆中最小节点
public T findMin() {
if (isEmpty())
return null;
return root.element;
}
/**
* 删除堆中最小节点,由于堆的最小节点就在根上,所以可以直接删除,但是删除根后,需要在将左右子树合并
*
* @return
*/
public T deleteMin() {
if (isEmpty())
return null;
T minItem = root.element;
root = merge(root.left, root.right);
return minItem;
}
// 判断左式堆是否为空
public boolean isEmpty() {
return root == null;
}
// 将左式堆设置为空堆
public void makeEmpty() {
this.root = null;
}
/**
* 1、若第一个根节点为空,则返回第二个根节点; 2、若第一个不为空第二个为空,则返回第一个根节点;
* 3、一、二节点都不为空时,判断那个是根较小的节点,将根较小的节点作为第一个参数传递给merge1方法
*
* @param h1
* @param h2
* @return
*/
private Node<T> merge(Node<T> h1, Node<T> h2) {
if (h1 == null)
return h2;
if (h2 == null)
return h1;
if (h1.element.compareTo(h2.element) < 0) {
return merge1(h1, h2);
} else {
return merge1(h2, h1);
}
}
/**
* 将根节点较大的树合并到根节点较小的树上去: 1、若根节点较小的树无左子树,则将根节点较大的树作为其左子树
* 2、若根节点较小的树有左子树,则将根节点较大的树和根节点较小的树的右子树合并,作为根节点较小的树的右子树
* 3、若左子树的零路径长小于右子树的零路径长,则交换左右子树 4、根节点较小的树的零路径长修正为其右子树的零路径长度+1
*
* @param h1
* @param h2
* @return
*/
private Node<T> merge1(Node<T> h1, Node<T> h2) {
if (h1.left == null)
h1.left = h2;
else {
h1.right = merge(h1.right, h2);
if (h1.left.npl < h1.right.npl)
swapChildren(h1);
h1.npl = h1.right.npl + 1;
}
return h1;
}
// 交换两个子树
private void swapChildren(Node<T> t) {
Node<T> tmp = t.left;
t.left = t.right;
t.right = tmp;
}
}
参考资料:《数据结构与算法分析--java语言描述》Mark Allen Weiss著
分享到:
相关推荐
左心室 (LV) 的手动分割是一项繁琐而细致的任务,可能因患者、磁共振图像 (MRI) 切口和专家的不同而有所不同。直到今天,我们仍将专家的人工描述视为心脏诊断医生的基本事实...堆叠式自动编码器 可变形模型 测试和指标
神经元的身体位于图的左下部,从那里出现的分支称为树突(信号的接收者),神经元具有轴突(信号的发送者),即将神经元的身体连接到其他神经元的长尾巴,在深度学习术语中通常称为突触。 然后,信号通过突触传递到...
2、本项目适合作为计算机、数学、电子信息等专业的竞赛项目学习资料,作为参考学习借鉴。 3、本资源作为“参考资料”如果需要实现其他功能,需要能看懂代码,并且热爱钻研,自行调试。 JDDC大赛第4名解决方案参赛...
051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 061 二叉树遍利 062 浮点数转换为...
交互式图形,探索数据集和机器学习。 交互式图形页面包含许多图形,以探索物理化学性质对葡萄酒质量的影响。 在左侧,用户可以选择酒的类型(例如,红葡萄酒,白葡萄酒)以及感兴趣的理化特征,并根据需要选择子集...
直观的菜单选项可用于排序、堆叠、转置数据并对其进行重新编码。 轻松展示演示文稿 将图形和输出结果直接导出到 Microsoft Word 或 PowerPoint,从而轻松创建演示文稿并共享结果。 发现和探索 查看当前和过去的...
随时查看我的投资组合,您会看到我从事的一大堆项目,如有任何问题,请随时通过以下链接与我联系。 怎么进入? 该网站位于以下地址: : 屏幕截图: 该网站已通过以下方式开发: 每个页面上的导航栏都包含指向...
堆栈 [stæk] (对应 heap 堆) statement 程序语句; 语句 ['steitmәnt]' n. 陈述,指令 subclass n.子类 ['sʌbklɑ:s]' (supertype 父类) switch (关键字) 选择语句。 n.开关,道岔 [switʃ] synchronized (关键字)...
第7章 深入学习for推导式 189 7.1 内容回顾:for推导式组成元素 189 7.2 for推导式:内部机制 192 7.3 for推导式的转化规则 194 7.4 Option以及其他的一些容器类型 197 7.4.1 Option容器 197 ...
《 SPSS 统计分析基础教程》&《SPSS 统计分析高级教程》张文彤等著 阅读人 群:编程 这两本书手把手地教你如何使用 SPSS 分析数据,加上 SPSS 本身“傻瓜式” 设计,因此配合这两本书进行一定的学习足够了。...
如何在配合销售部门给客户演示产品时用恰当的语言把公司的软件产品的优良特性展现给客户,让客户听能真正了解自己的需求,同时信赖我们的软件产品,进而选择和你合作,是作为一名技术部门的员工所必须要学习的课程。...
第七章 表 达 式 .58 7.1 操 作 符 .58 7.2 算术操作符和算术表达式.59 7.3 赋值操作符和赋值表达式.64 7.4 关系操作符和关系表达式.65 <<page 2>> page begin==================== 7.5 逻辑操作符和...
3.12 我不想学习那些复杂的规则,怎样才能避免这些未定义的求值顺序问题呢? 其他的表达式问题 *3.13 ++i和i++有什么区别? 3.14 如果我不使用表达式的值,那我应该用i++还是++i来做自增呢? 3.15 我要检查...
1.19 为什么不能像下面这样在初始式和数组维度值中使用const值?const int n=5; int a[n]; 10 1.20 const char *p、char const *p和char *const p有什么区别? 10 复杂的声明 11 1.21 怎样建立和理解非常复杂...
编译器提示 ``非法初始式" 云云。 o 2.13 以下的初始化有什么区别?char a[] = "string literal"; char *p = "string literal"; 当我向 p[i] 赋值的时候, 我的程序崩溃了。 o 2.14 我总算弄清除函数指针的声明...
法初始式” 云云。. . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.13 以下的初始化有什么区别?char a[] = "string literal"; char *p = "string literal"; 当我向p[i] 赋值的时候, 我的程序崩溃了。. ...