概要
前面分别通过C和C++实现了斜堆，本章给出斜堆的Java版本。还是那句老话，三种实现的原理一样，择其一了解即可。
目录
1. 斜堆的介绍
2. 斜堆的基本操作
3. 斜堆的Java实现(完整源码)
4. 斜堆的Java测试程序
转载请注明出处：http://www.cnblogs.com/skywang12345/p/3638552.html
更多内容：数据结构与算法系列 目录
斜堆(Skew heap)也叫自适应堆(self-adjusting heap)，它是左倾堆的一个变种。和左倾堆一样，它通常也用于实现优先队列；作为一种自适应的左倾堆，它的合并操作的时间复杂度也是O(lg n)。
它与左倾堆的差别是：
(01) 斜堆的节点没有"零距离"这个属性，而左倾堆则有。
(02) 斜堆的合并操作和左倾堆的合并操作算法不同。
斜堆的合并操作
(01) 如果一个空斜堆与一个非空斜堆合并，返回非空斜堆。
(02) 如果两个斜堆都非空，那么比较两个根节点，取较小堆的根节点为新的根节点。将"较小堆的根节点的右孩子"和"较大堆"进行合并。
(03) 合并后，交换新堆根节点的左孩子和右孩子。
第(03)步是斜堆和左倾堆的合并操作差别的关键所在，如果是左倾堆，则合并后要比较左右孩子的零距离大小，若右孩子的零距离 > 左孩子的零距离，则交换左右孩子；最后，在设置根的零距离。
1. 基本定义
private SkewNode<T> mRoot; // 根结点
private class SkewNode<T extends Comparable<T>> {
T key; // 关键字(键值)
SkewNode<T> left; // 左孩子
SkewNode<T> right; // 右孩子
public SkewNode(T key, SkewNode<T> left, SkewNode<T> right) {
this.key = key;
this.left = left;
this.right = right;
}
public String toString() {
return "key:"+key;
}
}
...
}
SkewNode是斜堆对应的节点类。
SkewHeap是斜堆类，它包含了斜堆的根节点，以及斜堆的操作。
2. 合并
* 合并"斜堆x"和"斜堆y"
*/
private SkewNode<T> merge(SkewNode<T> x, SkewNode<T> y) {
if(x == null) return y;
if(y == null) return x;
// 合并x和y时，将x作为合并后的树的根；
// 这里的操作是保证: x的key < y的key
if(x.key.compareTo(y.key) > 0) {
SkewNode<T> tmp = x;
x = y;
y = tmp;
}
// 将x的右孩子和y合并，
// 合并后直接交换x的左右孩子，而不需要像左倾堆一样考虑它们的npl。
SkewNode<T> tmp = merge(x.right, y);
x.right = x.left;
x.left = tmp;
return x;
}
public void merge(SkewHeap<T> other) {
this.mRoot = merge(this.mRoot, other.mRoot);
}
merge(x, y)是内部接口，作用是合并x和y这两个斜堆，并返回得到的新堆的根节点。
merge(other)是外部接口，作用是将other合并到当前堆中。
3. 添加
* 新建结点(key)，并将其插入到斜堆中
*
* 参数说明：
* key 插入结点的键值
*/
public void insert(T key) {
SkewNode<T> node = new SkewNode<T>(key,null,null);
// 如果新建结点失败，则返回。
if (node != null)
this.mRoot = merge(this.mRoot, node);
}
insert(key)的作用是新建键值为key的节点，并将其加入到当前斜堆中。
4. 删除
* 删除根结点
*
* 返回值：
* 返回被删除的节点的键值
*/
public T remove() {
if (this.mRoot == null)
return null;
T key =
DbUtility v3 背后的故事时间DbUtility v3构思了差不多大半年，真正开发到第一个版本发布到NuGet却只花了50天。中途大量时间在完善 Jumony 3，只有三周来开发DbUtility v3，其中总工时大概不超过20个小时。
DbUtility项目开始于2003年，2005年增加了实体转换的支持，2007年因为LINQ的发布，认为这个项目将来不会再有更新，遂开源，也是我开源的第一个项目，当时托管于Codeplex。
每当我要快速搞定一个事情的时候，DbUtility总是最称手的工具，事实上在2007年之后DbUtility有四年没有任何修改，因为我觉得没有什么新的功能需要。
如果不是眼馋.NET Framework 4.5新增的异步支持以及越来越多需要定制化查询结果（例如包装成Dictionary）的需求，DbUtility可能到现在都不会重写。
设计DbUtility v3花了很长的时间来构思他的API设计，希望既能兼容之前的形式，保持简洁，流畅的特点，又利于扩展。下了很大的决心才最终敲定db.T( xxx ).ExecuteXXX()这样的形式，这与之前是不兼容的，所以新发布了一个NuGet包，避免原来的项目升级大面积的编译错误。
利用扩展方法实现的API具有可以自行扩展以及整体切换的特点。这一风格是Jumony首创的，DbUtility把这个手法运用的更为娴熟了。
同样花了很长的时间才敲定同时提供T和Template两个一模一样的方法，事实上T是Template的缩写。虽然具备智能提示可以非常便捷的输入Template，但我仍然认为，T这样的缩写，可以最大限度减少代码的行宽，不带来额外的噪声污染。
db.T( xxx )将不会执行查询，必须使用db.T( xxx ).ExecuteNonQuery()一直是整个设计中的一大痛处，因为可能会忘记写.ExecuteNonQuery。但是的确没有办法解决。
DbUtility的结果构建器，即ExecuteXXX方法，原本为了简洁是打算去掉Execute前缀的，例如：db.T( “SELECT * FROM Users” ).ExecuteEntities()原本是打算写成db.T( “SELECT * FROM Users” ).Entities()。但是由于考虑到某些查询构建器（即T(xxx)）可能难以在一个方法内写完，需要多次调用构建最终的查询，此时执行查询的方法和构建查询的方法将没有明显的区分，故而依然保留Execute这个前缀。
- 譬如说
db.Table( "Users" ).Fields( "*" ).ExecuteEntities<User>()。
得益于新的架构设计，Jumony的结果构建器扩展方法写起来非常简单，所以我一口气提供了十几个用于构建不同类型结果的扩展方法。
技术DbUtility拥有理论上性能最好的实体转换器，其原理是根据实体类型直接Emit一个转换器方法出来进行实体转换，而Emit出来的这个方法则巧妙地利用类型字典被缓存。这两项技术都是.NET的不传之秘，较之不使用这两项技术的实现方式性能不在一个数量级。
DbUtility的API将C#的泛型和类型推断运用到了极致，事实上诸如T这样的扩展方法，接受的第一个参数的类型是IDbExecutor，而SqlDbUtiltiy类型恰好实现了这个接口，所以可以调用。也就是说如果哪个数据库的查询器不支持参数化查询（没有实现这个借口），那么就点不出T出来。更神奇的是如果数据库查询器不支持异步查询，那么所有的异步API也会自动消失。
DbUtility的异步API实现贯彻了许多可以异步的地方，如打开数据库连接，执行查询。目前只剩下DataReader.Read方法没有调用异步版本，这将在后面的更新中解决。DbUtility恐怕也是第一个实现异步API的数据库访问帮助器。
Java移植项目在充分利用C#语法特性上简直令人发指，各种莫名其妙不符合.NET命名规则的API搞得各种乌烟瘴气。而DbUtility不仅仅充分利用了泛型、扩展方法一系列特性，更提供了运算符重载，可以非常直观的把参数化查询像拼接字符串一样拼接起来。
在开发DbUtility v3的时候的确考虑过推出一个面向.NET Framework 3.5的版本，但是因为要同时维护两个版本过于费力。且DbUtility并非我的重心，故而作罢。但事实上删除DbUtility内所有的异步API，便可以得到在3.5下编译通过的代码。
优势
DbUtility v3构思了差不多大半年，真正开发到第一个版本发布到NuGet却只花了50天。中途大量时间在完善 Jumony 3，只有三周来开发DbUtility v3，其中总工时大概不超过20个小时。
DbUtility项目开始于2003年，2005年增加了实体转换的支持，2007年因为LINQ的发布，认为这个项目将来不会再有更新，遂开源，也是我开源的第一个项目，当时托管于Codeplex。
每当我要快速搞定一个事情的时候，DbUtility总是最称手的工具，事实上在2007年之后DbUtility有四年没有任何修改，因为我觉得没有什么新的功能需要。
如果不是眼馋.NET Framework 4.5新增的异步支持以及越来越多需要定制化查询结果（例如包装成Dictionary）的需求，DbUtility可能到现在都不会重写。
设计DbUtility v3花了很长的时间来构思他的API设计，希望既能兼容之前的形式，保持简洁，流畅的特点，又利于扩展。下了很大的决心才最终敲定db.T( xxx ).ExecuteXXX()这样的形式，这与之前是不兼容的，所以新发布了一个NuGet包，避免原来的项目升级大面积的编译错误。
利用扩展方法实现的API具有可以自行扩展以及整体切换的特点。这一风格是Jumony首创的，DbUtility把这个手法运用的更为娴熟了。
同样花了很长的时间才敲定同时提供T和Template两个一模一样的方法，事实上T是Template的缩写。虽然具备智能提示可以非常便捷的输入Template，但我仍然认为，T这样的缩写，可以最大限度减少代码的行宽，不带来额外的噪声污染。
db.T( xxx )将不会执行查询，必须使用db.T( xxx ).ExecuteNonQuery()一直是整个设计中的一大痛处，因为可能会忘记写.ExecuteNonQuery。但是的确没有办法解决。
DbUtility的结果构建器，即ExecuteXXX方法，原本为了简洁是打算去掉Execute前缀的，例如：db.T( “SELECT * FROM Users” ).ExecuteEntities()原本是打算写成db.T( “SELECT * FROM Users” ).Entities()。但是由于考虑到某些查询构建器（即T(xxx)）可能难以在一个方法内写完，需要多次调用构建最终的查询，此时执行查询的方法和构建查询的方法将没有明显的区分，故而依然保留Execute这个前缀。
- 譬如说
db.Table( "Users" ).Fields( "*" ).ExecuteEntities<User>()。
得益于新的架构设计，Jumony的结果构建器扩展方法写起来非常简单，所以我一口气提供了十几个用于构建不同类型结果的扩展方法。
技术DbUtility拥有理论上性能最好的实体转换器，其原理是根据实体类型直接Emit一个转换器方法出来进行实体转换，而Emit出来的这个方法则巧妙地利用类型字典被缓存。这两项技术都是.NET的不传之秘，较之不使用这两项技术的实现方式性能不在一个数量级。
DbUtility的API将C#的泛型和类型推断运用到了极致，事实上诸如T这样的扩展方法，接受的第一个参数的类型是IDbExecutor，而SqlDbUtiltiy类型恰好实现了这个接口，所以可以调用。也就是说如果哪个数据库的查询器不支持参数化查询（没有实现这个借口），那么就点不出T出来。更神奇的是如果数据库查询器不支持异步查询，那么所有的异步API也会自动消失。
DbUtility的异步API实现贯彻了许多可以异步的地方，如打开数据库连接，执行查询。目前只剩下DataReader.Read方法没有调用异步版本，这将在后面的更新中解决。DbUtility恐怕也是第一个实现异步API的数据库访问帮助器。
Java移植项目在充分利用C#语法特性上简直令人发指，各种莫名其妙不符合.NET命名规则的API搞得各种乌烟瘴气。而DbUtility不仅仅充分利用了泛型、扩展方法一系列特性，更提供了运算符重载，可以非常直观的把参数化查询像拼接字符串一样拼接起来。
在开发DbUtility v3的时候的确考虑过推出一个面向.NET Framework 3.5的版本，但是因为要同时维护两个版本过于费力。且DbUtility并非我的重心，故而作罢。但事实上删除DbUtility内所有的异步API，便可以得到在3.5下编译通过的代码。
优势
DbUtility v3花了很长的时间来构思他的API设计，希望既能兼容之前的形式，保持简洁，流畅的特点，又利于扩展。下了很大的决心才最终敲定db.T( xxx ).ExecuteXXX()这样的形式，这与之前是不兼容的，所以新发布了一个NuGet包，避免原来的项目升级大面积的编译错误。
利用扩展方法实现的API具有可以自行扩展以及整体切换的特点。这一风格是Jumony首创的，DbUtility把这个手法运用的更为娴熟了。
同样花了很长的时间才敲定同时提供T和Template两个一模一样的方法，事实上T是Template的缩写。虽然具备智能提示可以非常便捷的输入Template，但我仍然认为，T这样的缩写，可以最大限度减少代码的行宽，不带来额外的噪声污染。
db.T( xxx )将不会执行查询，必须使用db.T( xxx ).ExecuteNonQuery()一直是整个设计中的一大痛处，因为可能会忘记写.ExecuteNonQuery。但是的确没有办法解决。
DbUtility的结果构建器，即ExecuteXXX方法，原本为了简洁是打算去掉Execute前缀的，例如：db.T( “SELECT * FROM Users” ).ExecuteEntities()原本是打算写成db.T( “SELECT * FROM Users” ).Entities()。但是由于考虑到某些查询构建器（即T(xxx)）可能难以在一个方法内写完，需要多次调用构建最终的查询，此时执行查询的方法和构建查询的方法将没有明显的区分，故而依然保留Execute这个前缀。
- 譬如说
db.Table( "Users" ).Fields( "*" ).ExecuteEntities<User>()。
得益于新的架构设计，Jumony的结果构建器扩展方法写起来非常简单，所以我一口气提供了十几个用于构建不同类型结果的扩展方法。
DbUtility拥有理论上性能最好的实体转换器，其原理是根据实体类型直接Emit一个转换器方法出来进行实体转换，而Emit出来的这个方法则巧妙地利用类型字典被缓存。这两项技术都是.NET的不传之秘，较之不使用这两项技术的实现方式性能不在一个数量级。
DbUtility的API将C#的泛型和类型推断运用到了极致，事实上诸如T这样的扩展方法，接受的第一个参数的类型是IDbExecutor，而SqlDbUtiltiy类型恰好实现了这个接口，所以可以调用。也就是说如果哪个数据库的查询器不支持参数化查询（没有实现这个借口），那么就点不出T出来。更神奇的是如果数据库查询器不支持异步查询，那么所有的异步API也会自动消失。
DbUtility的异步API实现贯彻了许多可以异步的地方，如打开数据库连接，执行查询。目前只剩下DataReader.Read方法没有调用异步版本，这将在后面的更新中解决。DbUtility恐怕也是第一个实现异步API的数据库访问帮助器。
Java移植项目在充分利用C#语法特性上简直令人发指，各种莫名其妙不符合.NET命名规则的API搞得各种乌烟瘴气。而DbUtility不仅仅充分利用了泛型、扩展方法一系列特性，更提供了运算符重载，可以非常直观的把参数化查询像拼接字符串一样拼接起来。
在开发DbUtility v3的时候的确考虑过推出一个面向.NET Framework 3.5的版本，但是因为要同时维护两个版本过于费力。且DbUtility并非我的重心，故而作罢。但事实上删除DbUtility内所有的异步API，便可以得到在3.5下编译通过的代码。
优势
很多人会问我，DbUtility的优势在哪里？
事实上我一点儿都不想讨论这个问题，从根本上来说，DbUtility仅仅只是因为用了太多年非常顺手所以改进了一下让其与时俱进而已。
由于是超轻量级的数据库访问框架，代码量甚至都不过千行，可以说大家都是一样的，半斤八两没有区别。除非哪个不用Emit来做实体转换（这种垃圾应该赶紧扔掉）会造成性能下降。
但是总的来说，DbUtility仍然有一些特有的东西是其他轻量级框架难以企及的：
- 异步数据库查询
- DbUtility v3率先推出了异步数据库查询实现，并将在后面不断完善。
- 可扩展的API
- DbUtility v3采用了和Jumony项目一样的可扩展API设计，任何人任何第三方都可以在不修改现有代码之下对现有API进行扩展。
- 可替换和自定义的API
- 不仅仅是可以扩展现有API，甚至可以把整个API给替换掉。简单来说，如果你喜欢，甚至可以把DbUtility的API给换成Dapper一模一样的，但最终还是以DbUtility的核心在驱动。
- 参数化查询抽象
- 在v3的设计中，增加了抽象的参数化查询对象，参数化查询对象是与数据库无关的，在支持参数化查询的数据库，将会尝试采用参数化查询。而在不支持参数化查询的数据库，则尝试将参数值进行相应处理，以避免注入式问题。
- 结构化查询抽象
- 在将来，DbUtility 还将增加结构化查询抽象，将SQL查询抽象为语法树，通过方法来构建。在执行时再根据实际的数据库转换为相应的语法查询。
- 查询执行器、查询、结果构建器分离架构
- 吸取之前的经验，新的架构可以使得三部分独立的扩展，和谐的统一。
事实上DbUtility是一个面向真正程序员的超轻量数据访问框架，其拥有极大的可扩展性，并且扩展起来极为简便。这是DbUtility相较于其他超轻量数据访问框架的最大优势。
未来
DbUtility 即将到来的功能包括：
- 更丰富的配置项
- 例如不要总是异步打开连接（因为连接池内很可能已经存在连接）
- 查询超时时间
- 更好的异步支持（异步的Read调用）
- 更好的存储过程支持
- 查询日志记录和查询事件追踪（例如执行了哪些查询，执行了多久）。
在未来的版本中将会添加：
- 更多的数据库支持（譬如Excel？！）
- 结构化的 SQL 查询构建工具
- 自定义类型映射（例如XML字段映射到XDocument）
以及更多，，，，
参与
DbUtility是一个开源项目，其足够轻便和简单，所以参与到DbUtility的开发过程中也是非常简单的，您可以通过以下的方式来参与：
- 提交Bug和功能需求，最好附带测试用例
- fork项目，并增加测试用例
- fork项目，并增加新的功能
- 在实际项目中使用他，这样能更好的发现问题。
本文链接：DbUtility v3 背后的故事，转载请注明。
没有评论:
发表评论