비스듬히 쌓다.

하나, 비스듬히 쌓 인 소개
경사 더미 (Skew heap) 는 자가 적응 더미 (self - adjusting heap) 라 고도 부 르 는데 좌경 더미 의 변종 이다.좌경 더미 와 마찬가지 로 우선 대기 열 을 실현 하 는 데 도 사용 된다.자체 적 으로 적응 하 는 좌경 더미 로 서 합병 작업 의 시간 복잡 도 역시 O (lg n) 이다.그것 과 좌경 더미 의 차 이 는: (01) 경사 로 운 노드 는 '0 거리' 라 는 속성 이 없고 왼쪽 경사 로 는 있다.(02) 경사 로 의 합병 작업 과 좌경 로 의 합병 작업 알고리즘 은 다르다.
경사 로 의 합병 작업 (01) 빈 경사 로 가 비 공 경사 로 와 합 쳐 지면 비 공 경사 로 로 돌아 갑 니 다.(02) 만약 에 두 개의 경사 로 가 모두 비어 있 지 않 으 면 두 개의 노드 를 비교 하고 작은 쌓 인 뿌리 노드 를 새로운 뿌리 노드 로 한다.'작은 뿌리 노드 의 오른쪽 아이' 와 '큰 더미' 를 합 친다.(03) 합병 후 새 뿌리 노드 의 왼쪽 아이 와 오른쪽 아 이 를 교환 합 니 다.       (03) 단 계 는 경사 더미 와 좌경 더미 의 합병 작업 차이 의 관건 이다. 좌경 더미 라면 합병 후 좌우 아이의 0 거리 크기 를 비교 하고 오른쪽 아이의 0 거리 > 왼쪽 아이의 0 거리 가 있 으 면 좌우 아 이 를 교환 해 야 한다.마지막 으로 루트 의 0 거 리 를 설정 합 니 다.
 
2. 경사 더미 의 기본 조작
1. 기본 정의

template <class T>
class SkewNode{
    public:
        T key;                //    (  )
        SkewNode *left;        //    
        SkewNode *right;    //    

        SkewNode(T value, SkewNode *l, SkewNode *r):
            key(value), left(l),right(r) {}
};

SkewNode 는 경사 로 에 대응 하 는 노드 클래스 입 니 다.
 

template <class T>
class SkewHeap {
    private:
        SkewNode *mRoot;    //    

    public:
        SkewHeap();
        ~SkewHeap();

        //     "  "
        void preOrder();
        //     "  "
        void inOrder();
        //     "  "
        void postOrder();

         //  other      this 。
        void merge(SkewHeap* other);
        //    (key     )      
        void insert(T key);
        //     (key     )
        void remove();

        //     
        void destroy();

        //     
        void print();
    private:

        //     "  "
        void preOrder(SkewNode* heap) const;
        //     "  "
        void inOrder(SkewNode* heap) const;
        //     "  "
        void postOrder(SkewNode* heap) const;

        //     x   y
        void swapNode(SkewNode *&x, SkewNode *&y);
        //   "  x" "  y"
        SkewNode* merge(SkewNode* &x, SkewNode* &y);

        //     
        void destroy(SkewNode* &heap);

        //     
        void print(SkewNode* heap, T key, int direction);
};

SkewHeap 는 경사 로 된 루트 노드 와 경사 로 된 작업 을 포함 합 니 다.
 
2. 합병

/*
 *   "  x" "  y"
 */
template <class T>
SkewNode* SkewHeap::merge(SkewNode* &x, SkewNode* &y)
{
    if(x == NULL)
        return y;
    if(y == NULL)
        return x;

    //   x y ， x         ；
    //         : x key < y key
    if(x->key > y->key)
        swapNode(x, y);

    //  x     y  ，
    //        x     ，               npl。
    SkewNode *tmp = merge(x->right, y);
    x->right = x->left;
    x->left  = tmp;

    return x;
}

/*
 *  other      this 。
 */
template <class T>
void SkewHeap::merge(SkewHeap* other)
{
    mRoot = merge(mRoot, other->mRoot);
}

merge (x, y) 는 내부 인터페이스 로 x 와 y 두 개의 경사 더 미 를 합병 하고 얻 은 새로운 더 미 를 되 돌려 주 는 역할 을 합 니 다.merge (other) 는 외부 인터페이스 로 other 를 현재 더미 에 통합 하 는 역할 을 합 니 다.
 
3. 추가

/* 
 *      key            
 *
 *     ：
 *     heap       
 *     key         
 *    ：
 *        
 */
template <class T>
void SkewHeap::insert(T key)
{
    SkewNode *node;    //     

    //     
    node = new SkewNode(key, NULL, NULL);
    if (node==NULL)
    {
        cout << "ERROR: create node failed!" << endl;
        return ;
    }

    mRoot = merge(mRoot, node);
}

insert (key) 의 역할 은 새 키 값 이 key 인 노드 로 현재 경사 더미 에 추가 하 는 것 입 니 다.
 
4. 삭제

/* 
 *     
 */
template <class T>
void SkewHeap::remove()
{
    if (mRoot == NULL)
        return NULL;

    SkewNode *l = mRoot->left;
    SkewNode *r = mRoot->right;

    //      
    delete mRoot;
    //           
    mRoot = merge(l, r); 
}

reove () 의 역할 은 경사 로 의 최소 노드 를 삭제 하 는 것 이다.
 
 
본문http://www.cnblogs.com/skywang12345/p/3638524.html#a1
다음으로 전송:https://www.cnblogs.com/msymm/p/9757526.html