斜堆

斜堆的介紹

斜堆(Skew heap)也叫自适應堆(self-adjusting heap)，它是左傾堆的一個變種。和左傾堆一樣，它通常也用于實作優先隊列。它的合并操作的時間複雜度也是O(lg n)。

#include<stdio.h>
#include<stdlib.h>
typedef int Type;

typedef struct _SkewNode{
    Type   key;                // 關鍵字(鍵值)
    struct _SkewNode *left;    // 左孩子
    struct _SkewNode *right;   // 右孩子
}SkewNode, *SkewHeap;


/* 
 * 合并"斜堆x"和"斜堆y"
 *
 * 傳回值：
 *     合并得到的樹的根節點
 */
SkewNode* merge_skewheap(SkewHeap x, SkewHeap y)
{
    if(x == NULL)
        return y;
    if(y == NULL)
        return x;

    // 合并x和y時，将x作為合并後的樹的根；
    // 這裡的操作是保證: x的key < y的key
    if(x->key > y->key)
        swap_skewheap_node(x, y);

    // 将x的右孩子和y合并，
    // 合并後直接交換x的左右孩子，而不需要像左傾堆一樣考慮它們的npl。
    SkewNode *tmp = merge_skewheap(x->right, y);
    x->right = x->left;
    x->left  = tmp;

    return x;
}

/* 
 * 合并"斜堆x"和"斜堆y"
 *
 * 傳回值：
 *     合并得到的樹的根節點
 */
SkewNode* merge_skewheap(SkewHeap x, SkewHeap y)
{
    if(x == NULL)
        return y;
    if(y == NULL)
        return x;

    // 合并x和y時，将x作為合并後的樹的根；
    // 這裡的操作是保證: x的key < y的key
    if(x->key > y->key)
        swap_skewheap_node(x, y);

    // 将x的右孩子和y合并，
    // 合并後直接交換x的左右孩子，而不需要像左傾堆一樣考慮它們的npl。
    SkewNode *tmp = merge_skewheap(x->right, y);
    x->right = x->left;
    x->left  = tmp;

    return x;
}

/* 
 * 取出根節點
 *
 * 傳回值：
 *     取出根節點後的新樹的根節點
 */
SkewNode* delete_skewheap(SkewHeap heap)
{
    SkewNode *l = heap->left;
    SkewNode *r = heap->right;

    // 删除根節點
    free(heap);

    return merge_skewheap(l, r); // 傳回左右子樹合并後的新樹
}