• 斜堆(三)之 Java的实现


    概要

    前面分别通过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. 基本定义

    public class SkewHeap<T extends Comparable<T>> {
    
        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 = this.mRoot.key;
        SkewNode<T> l = this.mRoot.left;
        SkewNode<T> r = this.mRoot.right;
    
        this.mRoot = null;          // 删除根节点
        this.mRoot = merge(l, r);   // 合并左右子树
    
        return key;
    }

    remove()的作用是删除斜堆的最小节点。

    注意关于斜堆的"前序遍历"、"中序遍历"、"后序遍历"、"打印"、"销毁"等接口就不再单独介绍了。后文的源码中有给出它们的实现代码,Please RTFSC(Read The Fucking Source Code)!

    斜堆的Java实现(完整源码)

    斜堆的实现文件(SkewHeap.java)

      1 /**
      2  * Java 语言: 斜堆
      3  *
      4  * @author skywang
      5  * @date 2014/03/31
      6  */
      7 
      8 public class SkewHeap<T extends Comparable<T>> {
      9 
     10     private SkewNode<T> mRoot;    // 根结点
     11 
     12     private class SkewNode<T extends Comparable<T>> {
     13         T key;                // 关键字(键值)
     14         SkewNode<T> left;    // 左孩子
     15         SkewNode<T> right;    // 右孩子
     16 
     17         public SkewNode(T key, SkewNode<T> left, SkewNode<T> right) {
     18             this.key = key;
     19             this.left = left;
     20             this.right = right;
     21         }
     22 
     23         public String toString() {
     24             return "key:"+key;
     25         }
     26     }
     27 
     28     public SkewHeap() {
     29         mRoot = null;
     30     }
     31 
     32     /*
     33      * 前序遍历"斜堆"
     34      */
     35     private void preOrder(SkewNode<T> heap) {
     36         if(heap != null) {
     37             System.out.print(heap.key+" ");
     38             preOrder(heap.left);
     39             preOrder(heap.right);
     40         }
     41     }
     42 
     43     public void preOrder() {
     44         preOrder(mRoot);
     45     }
     46 
     47     /*
     48      * 中序遍历"斜堆"
     49      */
     50     private void inOrder(SkewNode<T> heap) {
     51         if(heap != null) {
     52             inOrder(heap.left);
     53             System.out.print(heap.key+" ");
     54             inOrder(heap.right);
     55         }
     56     }
     57 
     58     public void inOrder() {
     59         inOrder(mRoot);
     60     }
     61 
     62     /*
     63      * 后序遍历"斜堆"
     64      */
     65     private void postOrder(SkewNode<T> heap) {
     66         if(heap != null)
     67         {
     68             postOrder(heap.left);
     69             postOrder(heap.right);
     70             System.out.print(heap.key+" ");
     71         }
     72     }
     73 
     74     public void postOrder() {
     75         postOrder(mRoot);
     76     }
     77 
     78     /*
     79      * 合并"斜堆x"和"斜堆y"
     80      */
     81     private SkewNode<T> merge(SkewNode<T> x, SkewNode<T> y) {
     82         if(x == null) return y;
     83         if(y == null) return x;
     84 
     85         // 合并x和y时,将x作为合并后的树的根;
     86         // 这里的操作是保证: x的key < y的key
     87         if(x.key.compareTo(y.key) > 0) {
     88             SkewNode<T> tmp = x;
     89             x = y;
     90             y = tmp;
     91         }
     92 
     93         // 将x的右孩子和y合并,
     94         // 合并后直接交换x的左右孩子,而不需要像左倾堆一样考虑它们的npl。
     95         SkewNode<T> tmp = merge(x.right, y);
     96         x.right = x.left;
     97         x.left = tmp;
     98 
     99         return x;
    100     }
    101 
    102     public void merge(SkewHeap<T> other) {
    103         this.mRoot = merge(this.mRoot, other.mRoot);
    104     }
    105 
    106     /* 
    107      * 新建结点(key),并将其插入到斜堆中
    108      *
    109      * 参数说明:
    110      *     key 插入结点的键值
    111      */
    112     public void insert(T key) {
    113         SkewNode<T> node = new SkewNode<T>(key,null,null);
    114 
    115         // 如果新建结点失败,则返回。
    116         if (node != null)
    117             this.mRoot = merge(this.mRoot, node);
    118     }
    119 
    120     /* 
    121      * 删除根结点
    122      * 
    123      * 返回值:
    124      *     返回被删除的节点的键值
    125      */
    126     public T remove() {
    127         if (this.mRoot == null)
    128             return null;
    129 
    130         T key = this.mRoot.key;
    131         SkewNode<T> l = this.mRoot.left;
    132         SkewNode<T> r = this.mRoot.right;
    133 
    134         this.mRoot = null;          // 删除根节点
    135         this.mRoot = merge(l, r);   // 合并左右子树
    136 
    137         return key;
    138     }
    139 
    140     /*
    141      * 销毁斜堆
    142      */
    143     private void destroy(SkewNode<T> heap) {
    144         if (heap==null)
    145             return ;
    146 
    147         if (heap.left != null)
    148             destroy(heap.left);
    149         if (heap.right != null)
    150             destroy(heap.right);
    151 
    152         heap=null;
    153     }
    154 
    155     public void clear() {
    156         destroy(mRoot);
    157         mRoot = null;
    158     }
    159 
    160     /*
    161      * 打印"斜堆"
    162      *
    163      * key        -- 节点的键值 
    164      * direction  --  0,表示该节点是根节点;
    165      *               -1,表示该节点是它的父结点的左孩子;
    166      *                1,表示该节点是它的父结点的右孩子。
    167      */
    168     private void print(SkewNode<T> heap, T key, int direction) {
    169 
    170         if(heap != null) {
    171 
    172             if(direction==0)    // heap是根节点
    173                 System.out.printf("%2d is root
    ", heap.key);
    174             else                // heap是分支节点
    175                 System.out.printf("%2d is %2d's %6s child
    ", heap.key, key, direction==1?"right" : "left");
    176 
    177             print(heap.left, heap.key, -1);
    178             print(heap.right,heap.key,  1);
    179         }
    180     }
    181 
    182     public void print() {
    183         if (mRoot != null)
    184             print(mRoot, mRoot.key, 0);
    185     }
    186 }
    View Code

    斜堆的测试程序(SkewHeapTest.java)

     1 /**
     2  * Java 语言: 斜堆
     3  *
     4  * @author skywang
     5  * @date 2014/03/31
     6  */
     7 
     8 public class SkewHeapTest {
     9 
    10     public static void main(String[] args) {
    11 
    12         int a[]= {10,40,24,30,36,20,12,16};
    13         int b[]= {17,13,11,15,19,21,23};
    14         SkewHeap<Integer> ha=new SkewHeap<Integer>();
    15         SkewHeap<Integer> hb=new SkewHeap<Integer>();
    16 
    17         System.out.printf("== 斜堆(ha)中依次添加: ");
    18         for(int i=0; i<a.length; i++) {
    19             System.out.printf("%d ", a[i]);
    20             ha.insert(a[i]);
    21         }
    22         System.out.printf("
    == 斜堆(ha)的详细信息: 
    ");
    23         ha.print();
    24 
    25 
    26         System.out.printf("
    == 斜堆(hb)中依次添加: ");
    27         for(int i=0; i<b.length; i++) {
    28             System.out.printf("%d ", b[i]);
    29             hb.insert(b[i]);
    30         }
    31         System.out.printf("
    == 斜堆(hb)的详细信息: 
    ");
    32         hb.print();
    33 
    34         // 将"斜堆hb"合并到"斜堆ha"中。
    35         ha.merge(hb);
    36         System.out.printf("
    == 合并ha和hb后的详细信息: 
    ");
    37         ha.print();
    38     }
    39 }
    View Code

    斜堆的Java测试程序

    斜堆的测试程序已经包含在它的实现文件(SkewHeapTest.java)中了,这里仅给出它的运行结果:

    == 斜堆(ha)中依次添加: 10 40 24 30 36 20 12 16 
    == 斜堆(ha)的详细信息: 
    10 is root
    16 is 10's   left child
    20 is 16's   left child
    30 is 20's   left child
    40 is 30's   left child
    12 is 10's  right child
    24 is 12's   left child
    36 is 24's   left child
    
    == 斜堆(hb)中依次添加: 17 13 11 15 19 21 23 
    == 斜堆(hb)的详细信息: 
    11 is root
    13 is 11's   left child
    17 is 13's   left child
    23 is 17's   left child
    19 is 13's  right child
    15 is 11's  right child
    21 is 15's   left child
    
    == 合并ha和hb后的详细信息: 
    10 is root
    11 is 10's   left child
    12 is 11's   left child
    15 is 12's   left child
    21 is 15's   left child
    24 is 12's  right child
    36 is 24's   left child
    13 is 11's  right child
    17 is 13's   left child
    23 is 17's   left child
    19 is 13's  right child
    16 is 10's  right child
    20 is 16's   left child
    30 is 20's   left child
    40 is 30's   left child
  • 相关阅读:
    Zboot权限后台管理系统开源啦
    java中的强引用,软引用,弱引用,虚引用
    基于Hexo搭建个人博客
    拾遗Timer定时器
    手把手教你使用jmeter接口测试
    Vue 常见的面试题
    vue脚手架环境搭建
    vue过滤器
    基础面试题总结1
    Promise 库 lie.js 源码解读
  • 原文地址:https://www.cnblogs.com/skywang12345/p/3638552.html
一二三 - 开发者的网上家园