斜堆、、、

参考  斜堆 - 云+社区 - 腾讯云

斜堆的介绍

斜堆(Skew heap)也叫自适应堆(self-adjusting heap)，它是左倾堆的一个变种。和左倾堆一样，它通常也用于实现优先队列。它的合并操作的时间复杂度也是O(log n)。

相比于左倾堆，斜堆的节点没有"零距离"这个属性。除此之外，它们斜堆的合并操作也不同。斜堆的合并操作算法如下：
(01) 如果一个空斜堆与一个非空斜堆合并，返回非空斜堆。
(02) 如果两个斜堆都非空，那么比较两个根节点，取较小堆的根节点为新的根节点。将"较小堆的根节点的右孩子"和"较大堆"进行合并。
(03) 合并后，交换新堆根节点的左孩子和右孩子。
        第(03)步是斜堆和左倾堆的合并操作差别的关键所在，如果是左倾堆，则合并后要比较左右孩子的零距离大小，若右孩子的零距离 > 左孩子的零距离，则交换左右孩子；最后，在设置根的零距离。

很多都是和左倾堆很相似的！

#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); // 返回左右子树合并后的新树
    }