goudaner

goudaner 查看完整档案

深圳编辑阜阳科技职业学院  |  市场营销 编辑  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

goudaner 提出了问题 · 2018-06-27

maven无法正常下载jar以及pom文件

maven突然发生异常,无法下载任何镜像下的jar包以及pom文件,奇怪的是不管是在浏览器中直接访问,还是在终端下直接curl链接都是完全正常的。

操作系统是macOS

Darwin xxx-MB0 16.7.0 Darwin Kernel Version 16.7.0: Thu Jan 11 22:59:40 PST 2018; root:xnu-3789.73.8~1/RELEASE_X86_64 x86_64

mvn 版本信息如下:

Apache Maven 3.5.4 (1edded0938998edf8bf061f1ceb3cfdeccf443fe; 2018-06-18T02:33:14+08:00)
Maven home: /Users/dhy/tool/apache-maven-3.5.4
Java version: 1.7.0_80, vendor: Oracle Corporation, runtime: /Library/Java/JavaVirtualMachines/jdk1.7.0_80.jdk/Contents/Home/jre
Default locale: zh_CN, platform encoding: UTF-8
OS name: "mac os x", version: "10.12.6", arch: "x86_64", family: "mac"

mvn clean compile 信息如下:

[INFO] Scanning for projects...
[INFO]
[INFO] ----------------------------< com.xxx:yyy >-----------------------------
[INFO] Building yyy 1.0-SNAPSHOT
[INFO] --------------------------------[ jar ]---------------------------------
Downloading from nexus-aliyun: http://maven.aliyun.com/nexus/content/groups/public/org/apache/maven/plugins/maven-resources-plugin/2.6/maven-resources-plugin-2.6.pom

直接就卡在这个页面,换了官方的数据源依然是一样的。奇怪的是,这个链接无论curl还是在浏览器中访问都是正常的。

关注 3 回答 4

goudaner 关注了标签 · 2017-03-15

zookeeper

Zookeeper 是由 Apache 的一个顶级项目, 主要用来做分布式集群的协调服务.

关注 201

goudaner 关注了标签 · 2017-03-15

分布式

分布式计算是一门计算机科学,它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后把这些部分分配给许多计算机进行处理,最后把这些计算结果综合起来得到最终的结果。

关注 321

goudaner 赞了回答 · 2016-12-23

解决Java 8 peek() 方法的一些疑惑

简单地说就是懒咯 你没有对流进行任何操作peek就不会执行

关注 7 回答 5

goudaner 赞了回答 · 2016-12-08

解决javascript this 指向问题

作为函数调用的this指向书上描述是没有错,但语言设计上一直就有这个bug,作为内嵌定义函数,不管外层函数this是什么,它自己的this在非严格模式下都是指向全局对象,严格模式就是undefined,所以一般在外层函数把this赋值给一个变量让内层函数调用。

PS. 还有一个特例就是方法调用的函数的函数赋值给一个变量来调用的话this会变为指向全局对象,看下代码应该就懂了。

function Foo() {}
Foo.prototype.method = function() {};

function Bar() {}
Bar.prototype = new Foo();

new Bar().method();

method 调用时 this 指向的是 Bar 的实例

关注 10 回答 3

goudaner 赞了回答 · 2016-07-07

解决正则表达式中 ?= 和 ?: 的区别

先说结论,区别在于 ?= 是正向肯定 断言,进行的匹配是不占查询长度的;而 ?: 是非获取 匹配,进行的匹配是占据查询长度的。

题述的正则查询每一个非单词边界,然后对后面的一个或多个连续三组数字+一组非数字进行匹配。对于 1234567 而言,就会匹配到 1 和 2 中间的这个非单词边界,因为后面的 234567$ 满足正向肯定预查的 (\d{3})+(?!\d) 形式;之后会匹配到 4 和 5 中间的非单词边界,因为后面的 567$ 也满足上一形式。所以是正确的。

而你尝试将 + 去掉,使得断言只能匹配到 567$ 这样的形式——注意到你强调了 g 全局查询参数,但是我们要注意到 (?!\d) 的存在,这是一个正向否定断言,表示连续三个数字之后不能存在数字,所以 234 显然是不满足的,因为其后的 5 正是一个数字。假使你去掉了这个否定断言,那这个正则也不能工作——因为断言是 零宽 的,是不占据匹配长度的,查完 1 之后 234 满足,还会继续查 2,2 之后 345 也是满足的。因此结果就会变成 "1,2,3,4,567"

最后你尝试使用了 ?: 这个非获取匹配实际上是占据匹配长度的,当执行了第一次匹配时,实际上就匹配到了行尾,直接将 234567 全替换成了 ,,然后完成了匹配。所以就出现了上面的结果。

关注 8 回答 3

goudaner 赞了回答 · 2016-06-10

解决为什么能获取到父类的泛型?

java的范型是擦除法,就是只是在编译的时候检测类型是否安全,而在运行时这些范型类型已经被擦除,因此运行时使用反射时无法获知范型的类型,比如:

List<String> list = new ArrayList<>();

java在编译的时候会检测所有加入到list里面的都是String类型,编译后的class文件中是不会有范型的信息,所以运行的时候通过反射API是无法得知list的范型是String的。

而范型子类不一样:

class Child extends Parent<String>

java在编译的时候会检测父类的范型信息,因为子类声明了范型的类型并且在子类的代码中会使用到该类型,所以java会在生成的class中记录该子类声明的范型类型,所以只有在这种情况下运行时通过反射API可以取到该范型的类型。

关注 3 回答 2

goudaner 回答了问题 · 2016-06-10

解决到底什么是 hash,有什么作用,hashtable hashmap 又是什么,跟 hash 有很大关系吗?

Hash 一般也可叫做散列,你可以把 Hash 简单的理解为将一个对象通过 hashCode() 方法映射为一个 int 类型的值,其中 hashCode() 是定义在 Object 中的,而 java 中所有的类都继承自 Object。
所以所有的类都有默认的 hashCode() 方法,你可以根据自己的需要去进行重写。


以你说的 HashMap 为例:HashMap 在 JDK 默认的实现是 数组+链表,也就是一个数组,数组中的每一个元素都是一个链表,假设数组为 array,链表为 list。

HashMap 是对 key 做出了散列处理,也就是求出了 key 所对应的一个 int 值。
比如说你声明了一个 HashMap<String, Object> 类型,如果你调用一次 map.put("key", object)。
那么就先调用 "key".hashCode() 得到一个 int,这个 int 就是 "key" 的哈希值,用得到的这个 int 类型的值余上 array 的长度,就得到了这个 object 在 array 中的位置。

但是,在实际的使用中,可能会出现一种情况就是两个不同的对象的哈希值可能是相同的,假设 "key1" 和 "key2" 得到了相同的哈希值,那么这个时候我们调用 map.put("key1", object1) 和 map("key2", object2) 他们通过上面的步骤算出来的哈希值是相同的,也就是他们在 array 中的位置是相同的,这个就叫做 散列冲突

所以这就是为什么 JDK 使用 数组+链表 的实现形式了。我们通过上面的步骤得到一个对象在 array 中的位置,如果他们的哈希值相同,但是他们不是同一个 String,那么我们就将后添加的这个 object 添加到 list 中;如果他们是同一个 String,那么我们就用新的 object 覆盖它在 list 中的上一个 object。

例如,对于 "key1" 和 "key2" 通过散列得到的在 array 中的位置是相同的,那么我们判断 "key1".equals("key2"),如果返回 true,我们使用 object2 覆盖 object1,如果 返回 false,我们将 object2 添加到 list 中。

所以上面调用的结果应该如下,其中 2 是 "key1" 和 "key2" 通过散列的出来的在 array 中的位置:

{
    list0:null,
    list1:null,
    list2:[object1, object2]
}

JDK 使用的这种叫做分离链接法,还有一种叫做平方探测发法。有兴趣的话可以去看看《数据结构与算法分析》这本书,好像在第 5 章。

关注 10 回答 5

goudaner 发布了文章 · 2016-06-08

数据结构与算法学习笔记 - 优先队列、二叉堆、左式堆

6.1 模型

优先队列是允许至少下列两种操作的数据结构:insert 以及 deleteMin(找出、返回并删除优先队列中最小的元素)。

insert 操作等价于 enqueue(入队),而 deleteMin 则是运算 dequeue(出队)在优先队列中的等价操作。

clipboard.png

一些简单的实现

可以使用简单链表进行不排序的插入,则插入操作为 O(1),但是删除需要遍历链表为 O(N)。
另一种方法是让链表保持排序状态:插入代价高昂 O(N),但删除为 O(1).但是 deleteMin 的操作比插入操作少,前者可能更好。


另外一种方法是使用二叉查找树,它对这两种操作的平均运行时间都为 O(log N)。
但是,由于我们删除的唯一元素是最小元,反复出去左子树的节点会损害树的平衡使得右子树加重,在最坏情况下 deleteMin 将左子树删空。

另外,使用查找树有很多我们数据结构不需要的链。

二叉堆

我们将要使用的数据结构叫做二叉堆(binary heap),它的使用对于优先队列的实现相当普遍,以至于堆(heap)这个词不加修饰的用在优先队列的上下文中时,一般都是指数据结构的这种实现。

二叉堆有两个性质:结构性和堆序性。

结构性质

堆是一棵被完全填满的二叉树,有可能的例外是在底层,底层上的元素从左到右填入。这样的树被称为完全二叉树(complete binary tree)。

clipboard.png

一棵高为 h 的完全二叉树有 2h 到 2h+1 - 1 个节点。它的高度为 Log N,显然它是 O(log N)。

因为二叉堆是满二叉树,所以在高度为 h-1 的树包含
20 + ... + 2h-1 = 2h -1 个元素,
在高度为 h 的层上有 1 至 2h 个元素,所以应该有 2h 至 2h+1 - 1 个元素。

因为完全二叉树这么有规律,所以它可以用一个数组表示而不需要使用链。
clipboard.png

对于数组中任意位置 i 上的元素,其左儿子在位置 2i 上,右儿子在左儿子后的单元 (2i + 1)上。它的父亲则在位置 [i / 2] 上。

堆序性质

让操作快速执行的性质是堆序性质(heap-order property)。由于我们想要快速找出最小元,因此最小的元应该在根上。如果我们考虑任意子树也应该是一个堆,那么任意节点就给应该小于它的所有后裔。

clipboard.png

基本的堆操作

insert(插入)

为了将一个元素 X 插入到堆中,我们在下一个可用位置创建一个空穴,否则该堆将不是完全树。如果 X 可以放在该空穴中而并不破坏对的序,那么插入完成。
否则,我们把空穴的父节点移入该空穴中,这样空穴就朝着根的方向上冒一步。继续该过程直到 X 能够放入空穴中为止。

如下图所示:为了插入 14,我们在堆的下一个可用位置上建立一个空穴,由于将 14 插入空穴破坏了堆序性质,因此将 31 移入该空穴。

clipboard.png
在图中,将元素从做到右执行插入,所以下一个空穴的位置应该在 31 的右节点上
clipboard.png

deleteMin(删除最小元)

当删除一个最小元是,要在根节点建立一个空穴。由于现在少了一个元素,因此堆中最后一个元素 X 必须移动带该堆的某个地方。<u>这是为了满足二叉堆的结构性质 -- 它是一棵完全二叉树,空穴只能在最后一层的最后一个元素之后</u>
因此,我们将空穴的两个儿子中较小者移入空穴这样就把空穴向下推了一层。
重复该步骤直到 X 可以被放入空穴中。

例如,对于下面的例子中,我们先删除元素 13,这将在二叉堆的根节点上建立一个空穴。随后往里面插入数字 31.

clipboard.png

在堆的实现中经常发生的错误是当堆中存在偶数个元素的时候,可能会遇到某个节点只有一个子节点的情况(只会在最下层出现)。

package com.mosby.ch06;

/**
 * @author dhy
 */
public class BinaryHeap <T extends Comparable<? super T>> {
    public BinaryHeap(){
        this(DEFAULT_CAPACITY);
    }
    
    public BinaryHeap(int capacity){
        currentSize = 0;
        array = new Comparable[capacity];
    }
    
    /**
     * 向堆插入一个元素<br><br>
     * 
     * <blockquote>
     * 
     * 在这里我们的代码使用了一个小技巧:我们现在的目的是要将当前堆中的空穴(初始为数组中最后一个元素之后)
     * 移动到一个满足将 X 插入该空穴后不影响堆的性质的位置。<br><br>
     * 
     * 如果我们每次都将当前空穴的位置和它的父元素交换,那么对于一个元素上滤 d 层,
     * 那么由于交换而执行的赋值次数就是 3d。<br><br>
     * 
     * 而这里,我们每次只是在满足条件时将父节点的值赋给了这个空穴而没有将空穴的值上滤。<br>
     * 这样上滤 d 层将只需要 d 次对空穴的赋值和一次最后将 X 插入的赋值。总共 d+1 次赋值。
     * 
     * </blockquote>
     * 
     * @param x
     */
    public void insert(T x){
        //因为堆内部的数组实现的第一个元素是空
        if(currentSize == array.length - 1){
            enlargeArray(array.length * 2 + 1);
        }
        
        //当前空穴的位置在最后一个元素的后一位,同时插入空穴之后 currentSize 增加一。等同于下面的代码
        //int hole = currentSize + 1;
        //currentSize++;
        int hole = ++currentSize;
        for(; hole > 1 && x.compareTo((T) array[hole / 2]) < 0; hole /= 2){
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }
    
    public T findMin(){
        if(isEmpty()){
            return null;
        }
        return (T) array[1];
    }
    
    public T deleteMin(){
        if(isEmpty()){
            throw new RuntimeException("Under flow");
        }
        
        T minItem = findMin();
        
        array[1] = array[currentSize--];
        percolateDown(1);
        
        return minItem;
    }
    
    public boolean isEmpty(){
        return currentSize == 0;
    }
    
    public void makeEmpty(){
        currentSize = 0;
    }
    
    private static final int DEFAULT_CAPACITY = 100;
    
    private int currentSize;//当前堆中元素个数
    private Comparable<? super T>[] array;//堆内部的以数组的形式存放
    
    /**
     * 对空穴进行下滤
     * @param hole
     */
    private void percolateDown(int hole){
        //这里 child 的初值不会影响程序的正确性,但是 eclipse 的编译器有 bug, int child; 是无法通过编译的
        //在 IDEA 下可以直接 int child;
        int child = hole * 2;
        Comparable<? super T> tmp = array[hole];
       
        /**
         * 这里注意一点,hole * 2 <= currentSize,因为数组的第一个元素为空<br>
         * 数组中的实际元素应该是 array[i] - array[currentSize]
         */
        for(; hole * 2 <= currentSize; hole = child){
            child = hole * 2;
            /**
             * 在下滤的过程中,我们每次将当前节点的两个子节点中较小的那个子节点跟空穴交换<br>
             * 
             * 但是这必须要考虑一个问题,在最下层的时候,可能会有某个节点只有一个子节点<br>
             * 
             * 而在非最下层则不会有这个问题,因为二叉堆是一个完全二叉树。<br>
             * 
             * 而根据二叉堆的插入性质(从左往右插入),那么只有一个元素的节点,这个元素的子节点肯定
             * 就是二叉堆的最后一个节点。此时 hole == currentSize.
             */
            if(child != currentSize && array[child + 1].compareTo((T) array[child]) < 0){
                child++;
            }
            if(array[child].compareTo((T) tmp) < 0){
                array[hole] = array[child];
            }else{
                break;
            }
        }
        array[hole] = tmp;
    }
    
    /**
     * 如果提供了通过数组初始化二叉堆的方式,那么在传入一个数组后调用该方法即可得到一个二叉堆。
     */
    private void buildHeap(){
        for(int i = currentSize / 2; i > 0; i--){
            percolateDown(i);
        }
    }
    public void enlargeArray(int newSize){
        Comparable[] newArray = new Comparable[newSize];
        for(int i = 1; i <= currentSize; i++){
            newArray[i] = array[i];
        }
        array = newArray;
    }
    public int size(){
        return currentSize;
    }
}

左式堆

设计一种堆结构像二叉堆那样有效的支持合并操作(即以 O(N) 时间处理一个 merge)而且只使用一个数组似乎很困难。原因在于,合并似乎需要把一个数组拷贝到另外一个数组中去。

<u>正因为如此,所有支持有效合并的高级数据结构都需要使用链式数据结构</u>

左式堆 (leftist heap)像二叉堆一样具有结构性和有序性。左式堆也是二叉树,左式堆和二叉堆的唯一区别是:左式堆不是理想平衡(perfectly balanced),而实际上趋向于非常不平衡。

左式堆性质

我们把任意节点 X 的零路径长(null path length) npl(X) 定义为从 X 到一个不具有两个儿子的节点的最短路径长。因此,具有 0 个或一个儿子的节点的 npl 为 0,而 npl(null) = -1。

clipboard.png

任意节点的零路径长比它的所有儿子节点的零路径长的最小值大1.这个结论也适用于少于两个儿子的节点,因为 null 的零路径长是 -1.

左式堆的性质是:对于堆中的每一个节点 X,左儿子的零路径长大于等于右儿子的零路径长。
实际上,对于左式堆的任意一个节点只能有三种情况,有两个子节点、没有子节点、仅有一个节点且该节点为左子节点。
也就是说,如果存在任意一个节点只有右节点,那么这个堆一定不是左式堆。但是,如果一个节点每个节点都满足上面的条件,它不一定是左式堆,还需要满足零路径长的条件。

显然,在上路中,左图是一棵左式堆;而右图则不是,因为右图的根节点的左子节点的左子节点的零路径长 == 0,而根节点的左子节点的右子节点的零路径长 == 1.

这个性质使得它不是一棵理想平衡树,因为它显然偏重于使树向左增加深度。

因为左式堆趋向于加深左路径,所以右路径应该短。事实上,沿左式堆的右路径是该堆中的最短路径。否则,就会存在某个节点 X 的左儿子的最短路径长小于右儿子的最短路径长。

            node
        /          \
     node         `node`
    /    \        /    \
 node   node   `null`   node

例如,对于上面这个树,对于标记的 node 节点是不符合左式堆的,因为它的左子节点的零路径长是 -1,而右子节点的零路径长是 0.

左式堆的基本操作

左式堆的基本操作是合并。注意,插入只是合并的特殊性情况。

clipboard.png

                      3                      |                               6                      |
                /          \                 |                         /          \                 |
              10            8                |                       12            7                |
            /    \        /                  |                     /    \        /   \              |
          21      14    17                   |                   18      24    37     18            |
                /      /                     |                         /                            |
              23     26                      |                       33                             |

合并具有大的 root 的堆与具有较小的 root 的堆的右节点


函数栈最上层
                                             |                               6                      |
                                             |                         /          \                 |
                            8                |                       12            7                |
                          /                  |                     /    \        /   \              |
                        17                   |                   18      24    37     18            |
                       /                     |                         /                            |
                     26                      |                       33                             |
函数栈的底层,该层等待上层函数的返回
                      3                      |
                /                            |
              10                             |
            /    \                           |
          21      14                         |
                /                            |
              23                             |

递归的去进行 merge 操作


函数栈最上层
                            8                |                                     7                |
                          /                  |                                   /   \              |
                        17                   |                                 37     18            |
                       /                     |                                                      |
                     26                      |                                                      |
函数栈第二层
                                             |                               6                      |
                                             |                         /                            |
                                             |                       12                             |
                                             |                     /    \                           |
                                             |                   18      24                         |
                                             |                         /                            |
                                             |                       33                             |
函数栈的底层,该层等待上层函数的返回
                      3                      |
                /                            |
              10                             |
            /    \                           |
          21      14                         |
                /                            |
              23                             |

继续进行递归 merge


函数栈最上层
                            8                |                                                      |
                          /                  |                                                      |
                        17                   |                                        18            |
                       /                     |                                                      |
                     26                      |                                                      |
函数栈第二层
                                             |                                     7                |
                                             |                                   /                  |
                                             |                                 37                   |
                                             |                                                      |
                                             |                                                      |
函数栈第三层
                                             |                               6                      |
                                             |                         /                            |
                                             |                       12                             |
                                             |                     /    \                           |
                                             |                   18      24                         |
                                             |                         /                            |
                                             |                       33                             |
函数栈的底层,该层等待上层函数的返回
                      3                      |
                /                            |
              10                             |
            /    \                           |
          21      14                         |
                /                            |
              23                             |

继续进行递归 merge


函数栈最上层,这个时候函数栈开始退出
                      null                   |                                        18            |
函数栈最二层
                            8                |                                                      |
                          /                  |                                                      |
                        17                   |                                                      |
                       /                     |                                                      |
                     26                      |                                                      |
函数栈第三层
                                             |                                     7                |
                                             |                                   /                  |
                                             |                                 37                   |
                                             |                                                      |
                                             |                                                      |
函数栈第四层
                                             |                               6                      |
                                             |                         /                            |
                                             |                       12                             |
                                             |                     /    \                           |
                                             |                   18      24                         |
                                             |                         /                            |
                                             |                       33                             |
函数栈的底层,该层等待上层函数的返回
                      3                      |
                /                            |
              10                             |
            /    \                           |
          21      14                         |
                /                            |
              23                             |

函数栈开始退出


函数栈最上层,上层函数退出,同时必须更新 root 节点的 npl
                            8                |                                                      |
                          /   \              |                                                      |
                        17    18             |                                                      |
                       /                     |                                                      |
                     26                      |                                                      |
函数栈第二层
                                             |                                     7                |
                                             |                                   /                  |
                                             |                                 37                   |
                                             |                                                      |
                                             |                                                      |
函数栈第三层
                                             |                               6                      |
                                             |                         /                            |
                                             |                       12                             |
                                             |                     /    \                           |
                                             |                   18      24                         |
                                             |                         /                            |
                                             |                       33                             |
函数栈的底层,该层等待上层函数的返回
                      3                      |
                /                            |
              10                             |
            /    \                           |
          21      14                         |
                /                            |
              23                             |

函数栈继续退出,同时如果root左子树的零路径长小于右子树的零路径长则必须翻转两个子树


函数栈最上层,上层函数退出,同时必须更新 root 节点的 npl
                         7
                       /   \
                    8       37               |                                                      |
                  /   \                      |                                                      |
                17    18                     |                                                      |
               /                             |                                                      |
             26                              |                                                      |
函数栈第二层
                                             |                               6                      |
                                             |                         /                            |
                                             |                       12                             |
                                             |                     /    \                           |
                                             |                   18      24                         |
                                             |                         /                            |
                                             |                       33                             |
函数栈的底层,该层等待上层函数的返回
                      3                      |
                /                            |
              10                             |
            /    \                           |
          21      14                         |
                /                            |
              23                             |

最后得到的结果为 图 6-24 所示。

递归的退出条件是

  1. 被 merge 的两个左式堆中任意一个为 null,则返回另一个;

  2. 两个左式堆中那么具有较小 root 节点的左子节点为 null 时,将具有较大 root 的节点作为具有较小 root 的节点的左子节点,并返回具有较小 root 的几点。这里隐含了一个信息:当一个左式堆的左子节点为 null 时,它的右子节点必定为 null。因为如果右子节点不为 null,那么它就不满足左式堆的条件了。

如果这两个堆中有一个为空,那么我们可以返回另外一个堆。
否则合并他们:

  1. 首先,我们递归的将具有大的 root 的堆与具有小的 root的堆的右子堆合并。我们在递归算法中需要保证递归得到的这棵树是左式堆。

为什么这里是合并较大 root 的堆和较小 root 的堆的右子堆呢?
因为,我们合并出来的这个堆需要做为原来那个堆的右子堆,而根据左式堆的性质,一个节点所有的子节点都必须大于该节点。

clipboard.png

图 6-23 得到的不是左式堆。左式的性质在根处被破坏。
在我们步骤 1. 中得到的新的子树是左式堆,而右子树本身就是左式堆,所以这棵树是不是满足左式堆,只要左子树的零路径长大于新的右子树的零路径长即可。
如果不满足,我们只需要将左子树和右子树的节点交换并更新零路径长就可以了。

clipboard.png

package com.mosby.ch06;

/**
 * 左式堆:与普通二叉堆区别在于,左式堆不是一个完全二叉树,并且左式堆不是一个理想平衡二叉树。
 */
public class LeftistHeap <E extends Comparable<? super E>> {
    public LeftistHeap(){
        root = null;
    }

    /**
     * 公有的 merge 方法将 anotherLeftistHeap 合并到控制堆中。
     * 随后 anotherLeftistHeap 变成了空的。
     * 在第一趟,我们通过合并两个堆的右路径建立一棵新的树。为此,以排序的方式安排 H<sub>1</sub> 和 H<sub>2</sub>
     * 右路径上的节点,保持他们各自的左儿子不变。
     * 第二趟构成堆,儿子的交换工作在左式堆性质被破坏的那些节点上进行。
     * <br>
     * @param anotherLeftistHeap 被合并的左式树
     */
    public void merge(LeftistHeap<E> anotherLeftistHeap){
        if(this == null){
            return ;
        }
        root = merge(root, this.root);
        anotherLeftistHeap.root = null;
    }

    /**
     * 向左式树中插入新的元素
     * <br>
     * @param x
     */
    public void insert(E x){
        root = merge(new Node<>(x), root);
    }

    /**
     * 寻找左式堆中最小的元素
     * <br>
     * @return 左式堆最小元素
     */
    public E findMin(){
        if(isEmpty()){
            return null;
        }
        return root.theElement;
    }

    /**
     * 删除左式堆中最小元素,并返回该元素
     * <br>
     * @return 被删除的元素
     */
    public E deleteMin(){
        if(isEmpty()){
            return null;
        }
        E minItem = root.theElement;
        root = merge(root.left, root.right);

        return minItem;
    }

    /**
     * 返回左式堆是否为空
     * <br>
     * @return
     */
    public boolean isEmpty(){
        return root == null;
    }

    /**
     * 将左式堆设置为空堆
     */
    public void makeEmpty(){
        root = null;
    }

    /**
     * 内部类用于表示左式堆的节点,相对于普通的二叉树多了 npl(null path length)用于记录空路径长
     * <br>
     * @param <E> 节点中的存储的对象
     */
    private static class Node<E>{
        Node(E theElement){
            this(theElement, null, null);
        }
        Node(E theElement, Node<E> left, Node<E> right){
            this.theElement = theElement;
            this.left = left;
            this.right = right;
            npl = 0;
        }

        E theElement;
        Node<E> left;
        Node<E> right;
        int npl;
    }

    private Node<E> root;

    /**
     * merge 方法被用于消除一些特殊情形并保证 H<sub>1</sub> 有较小的根。
     * <br>
     * @param h1
     * @param h2
     * @return
     */
    private Node<E> merge(Node<E> h1, Node<E> h2){
        if(h1 == null){
            return h2;
        }
        if(h2 == null){
            return h1;
        }
        if(h1.theElement.compareTo(h2.theElement) < 0){
            return merge1(h1, h2);
        }else{
            return merge1(h2, h1);
        }
    }

    /**
     * merge1 执行实际的合并操作,并且在 merge1 的调用中,h<sub>1</sub> 小于 h<sub>2</sub>
     * <br>
     * @param h1
     * @param h2
     * @return
     */
    private Node<E> merge1(Node<E> h1, Node<E> h2){
        //根据左式堆的性质,如果 h1.left == null,那么 h1.right == null 也成立
        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<E> t){
        Node<E> tmp = t.left;
        t.right = t.left;
        t.left = tmp;
    }
}
查看原文

赞 0 收藏 6 评论 0

goudaner 赞了文章 · 2016-05-05

Python数据结构与算法设计总结篇

Python数据结构与算法设计总结篇 http://hujiaweibujidao.github.io/python/

1.Python数据结构篇

数据结构篇主要是阅读Problem Solving with Python时写下的阅读记录,当然,也结合了部分算法导论中的内容,此外还有不少wikipedia上的内容,所以内容比较多,可能有点杂乱。这部分主要是介绍了如何使用Python实现常用的一些数据结构,例如堆栈、队列、二叉树等等,也有Python内置的数据结构性能的分析,同时还包括了搜索和排序(在算法设计篇中会有更加详细的介绍)的简单总结。每篇文章都有实现代码,内容比较多,简单算法一般是大致介绍下思想及算法流程,复杂的算法会给出各种图示和代码实现详细介绍。这一部分是下面算法设计篇的前篇,如果数据结构还不错的可以直接看算法设计篇,遇到问题可以回来看数据结构篇中的某个具体内容充电一下,嘿嘿。

(1)搜索 简述顺序查找和二分查找,详述Hash查找(hash函数的设计以及如何避免冲突)

(2)排序 简述各种排序算法的思想以及它的图示和实现

(3)数据结构 简述Python内置数据结构的性能分析和实现常用的数据结构:栈、队列和二叉堆

(4)树总结 简述二叉树,详述二叉搜索树和AVL树的思想和实现

2.Python算法设计篇

算法设计篇主要是阅读Python Algorithms: Mastering Basic Algorithms in the Python Language[点击链接可进入Springer下载原书电子版]之后写下的读书总结,原书大部分内容结合了经典书籍算法导论,内容更加细致深入,主要是介绍了各种常用的算法设计思想,以及如何使用Python高效巧妙地实现这些算法,这里有别于前面的数据结构篇,部分算法例如排序就不会详细介绍它的实现细节,而是侧重于它内在的算法思想。这部分使用了一些与数据结构有关的第三方模块,因为这篇的重点是算法的思想以及实现,所以并没有去重新实现每个数据结构,但是在介绍算法的同时会分析Python内置数据结构以及第三方数据结构模块的优缺点,也就意味着该篇比前面都要难不少,但是我想我的介绍应该还算简单明了,嘿嘿,除此之外,里面还有很多关于python开发的内容,精彩不容错过!

这里每篇文章都有实现代码,但是代码我一般都不会分析,更多地是分析算法思想,所以内容都比较多,即便如此也没有包括原书对应章节的所有内容,因为内容实在太丰富了,所以我只是选择经典的算法实例来介绍算法核心思想,除此之外,还有不少内容是原书没有的,部分是来自算法导论,部分是来自我自己的感悟,嘻嘻。该篇对于大神们来说是小菜,请一笑而过,对于菜鸟们来说可能有点难啃,所以最适合的是和我水平差不多的,对各个算法都有所了解但是理解还不算深刻的半桶水的程序猿,嘿嘿。

本篇的顺序按照原书Python Algorithms: Mastering Basic Algorithms in the Python Language的章节来安排的(章节标题部分相同部分不同哟),为了节省时间以及保持原著的原滋原味,部分内容(一般是比较难以翻译和理解的内容)直接摘自原著英文内容。

1.你也许觉得很多内容你都知道嘛,没有看的必要,其实如果是我的话我也会这么想,但是如果只是归纳一个算法有哪些步骤,那这个总结也就没有意义了,我觉得这个总结的亮点在于想办法说清楚一个算法是怎么想出来的,有哪些需要注意的,如何进行优化的等等。

2.你也许还会说算法导论不是既权威又全面么,基本上每个算法都还有详细的证明呢,读算法导论岂不更好些,当然,你如果想读算法导论我不拦着你,读完了感觉自己整个人都不好了别怪小弟没有提醒你哟,嘻嘻嘻,左一个性质右一个定理实在不适合算法科普的啦,没有几个人能够坚持读完的。

3.如果你细读本系列的话我保证你会有不少收获的,需要看算法导论哪个部分的地方我会给出提示的,嘿嘿。温馨提示,精彩内容从第4节开始哟,么么哒 O(∩_∩)O~

(1)Python Algorithms - C1 Introduction

本节主要是对原书中的内容做些简单介绍,说明算法的重要性以及各章节的内容概要。

(2)Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

(3)Python Algorithms - C3 Counting 101

原书主要介绍了一些基础数学,例如排列组合以及递归循环等,但是本节只重点介绍计算算法的运行时间的三种方法

(4)Python Algorithms - C4 Induction and Recursion and Reduction

本节主要介绍算法设计的三个核心知识:Induction(推导)、Recursion(递归)和Reduction(规约),这是原书的重点和难点部分

(5)Python Algorithms - C5 Traversal

本节主要介绍图的遍历算法BFS和DFS,以及对拓扑排序的另一种解法和寻找图的(强)连通分量的算法

(6)Python Algorithms - C6 Divide and Combine and Conquer

本节主要介绍分治法策略,提到了树形问题的平衡性以及基于分治策略的排序算法

(7)Python Algorithms - C7 Greedy

本节主要通过几个例子来介绍贪心策略,主要包括背包问题、哈夫曼编码和最小生成树

(8)Python Algorithms - C8 Dynamic Programming

本节主要结合一些经典的动规问题介绍动态规划的备忘录法和迭代法这两种实现方式,并对这两种方式进行对比

(9)Python Algorithms - C9 Graphs

本节主要介绍图算法中的各种最短路径算法,从不同的角度揭示它们的内核以及它们的异同

欢迎访问,有任何问题可以在我博客留言哟!

查看原文

赞 15 收藏 106 评论 2

认证与成就

  • 获得 27 次点赞
  • 获得 53 枚徽章 获得 3 枚金徽章, 获得 19 枚银徽章, 获得 31 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2015-07-06
个人主页被 862 人浏览