斜め積みのJavaの実現

21583 ワード

斜め積みの紹介
スキュースタック(Skew heap)は適応スタック(self-adjusting heap)とも呼ばれ、左傾スタックの変種である.左傾スタックと同様に、優先キューを実現するためにも一般的に使用されます.適応左傾スタックとして,その合成動作の時間的複雑さもO(lg n)である.左傾スタックとの違いは、(01)斜めスタックのノードには「ゼロ距離」という属性がなく、左傾スタックにはあります.(02)斜めスタックのマージ操作と左傾スタックのマージ操作アルゴリズムが異なる.
スロープスタックのマージ操作(01)空のスロープスタックが非空のスロープスタックとマージされた場合、非空のスロープスタックが返されます.(02)2つの斜めスタックが空でない場合、2つのルートノードを比較し、小さなスタックのルートノードを新しいルートノードとする.「小さなスタックのルートノードの右の子」と「大きなスタック」をマージします.(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の2つの斜めスタックを結合し,得られた新しいスタックのルートノードを返す役割を果たす.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)

/** * Java   :    * * @author skywang * @date 2014/03/31 */

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;
        }
    }

    public SkewHeap() {
        mRoot = null;
    }

    /* *     "  " */
    private void preOrder(SkewNode<T> heap) {
        if(heap != null) {
            System.out.print(heap.key+" ");
            preOrder(heap.left);
            preOrder(heap.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    /* *     "  " */
    private void inOrder(SkewNode<T> heap) {
        if(heap != null) {
            inOrder(heap.left);
            System.out.print(heap.key+" ");
            inOrder(heap.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }

    /* *     "  " */
    private void postOrder(SkewNode<T> heap) {
        if(heap != null)
        {
            postOrder(heap.left);
            postOrder(heap.right);
            System.out.print(heap.key+" ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }

    /* *   "  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);
    }

    /* *     (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);
    }

    /* *       * *    ： *             */
    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;
    }

    /* *      */
    private void destroy(SkewNode<T> heap) {
        if (heap==null)
            return ;

        if (heap.left != null)
            destroy(heap.left);
        if (heap.right != null)
            destroy(heap.right);

        heap=null;
    }

    public void clear() {
        destroy(mRoot);
        mRoot = null;
    }

    /* *   "  " * * key --       * direction -- 0，         ; * -1，               ; * 1，               。 */
    private void print(SkewNode<T> heap, T key, int direction) {

        if(heap != null) {

            if(direction==0)    // heap    
                System.out.printf("%2d is root
", heap.key);
            else                // heap     
                System.out.printf("%2d is %2d's %6s child
", heap.key, key, direction==1?"right" : "left");

            print(heap.left, heap.key, -1);
            print(heap.right,heap.key,  1);
        }
    }

    public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, 0);
    }
}

スロープスタックのテストプログラム(SkewHeapTest.java)

/** * Java   :    * * @author skywang * @date 2014/03/31 */

public class SkewHeapTest {

    public static void main(String[] args) {

        int a[]= {10,40,24,30,36,20,12,16};
        int b[]= {17,13,11,15,19,21,23};
        SkewHeap<Integer> ha=new SkewHeap<Integer>();
        SkewHeap<Integer> hb=new SkewHeap<Integer>();

        System.out.printf("==   (ha)     : ");
        for(int i=0; i<a.length; i++) {
            System.out.printf("%d ", a[i]);
            ha.insert(a[i]);
        }
        System.out.printf("
==   (ha)     : 
");
        ha.print();


        System.out.printf("
==   (hb)     : ");
        for(int i=0; i<b.length; i++) {
            System.out.printf("%d ", b[i]);
            hb.insert(b[i]);
        }
        System.out.printf("
==   (hb)     : 
");
        hb.print();

        //  "  hb"   "  ha" 。
        ha.merge(hb);
        System.out.printf("
==   ha hb      : 
");
        ha.print();
    }
}

斜めスタックのJavaテストプログラム
スロープスタックのテストプログラムはすでにその実装ファイル(SkewHeapTest.java)に含まれており、ここではその実行結果のみを示します.

==   (ha)     : 10 40 24 30 36 20 12 16 
==   (ha)     : 
is root
is 10's left child
is 16's left child
is 20's left child
is 30's left child
is 10's right child
is 12's left child
is 24's left child

==   (hb)     : 17 13 11 15 19 21 23 
==   (hb)     : 
is root
is 11's left child
is 13's left child
is 17's left child
is 13's right child
is 11's right child
is 15's left child

==   ha hb      : 
is root
is 10's left child
is 11's left child
is 12's left child
is 15's left child
is 12's right child
is 24's left child
is 11's right child
is 13's left child
is 17's left child
is 13's right child
is 10's right child
is 16's left child
is 20's left child
is 30's left child

斜堆のJavaの実現

Openfire smackパッケージ

JAva基礎知識回顧のjava Socket学習(一)--UDPプロトコルプログラミング