斜堆的介紹
斜堆(Skew heap)也叫自适應堆(self-adjusting heap),它是左傾堆的一個變種。和左傾堆一樣,它通常也用于實作優先隊列。它的合并操作的時間複雜度也是O(log 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); // 傳回左右子樹合并後的新樹
}