Cactus

用户名：Caczhtus

访问量：2984

签　名：

等　　级
排　　名	21480
经　　验	668
参赛次数	3
文章发表	2
年　　龄	19
在职情况	学生
学　　校
专　　业

　　自我简介：

来日犹可追

TA的其他文章

关于打算法类比赛vscode的基本配置
浏览：1267

左偏树总结（可合并的优先队列）
浏览：826

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

左偏树总结（可合并的优先队列）

　　作者: Cactus　　　　发表时间：2019-09-17 10:46:43 浏览：826　|　评论：0　

# 前言
可并堆有多种方法实现，例如斐波那契堆，配对堆等，以下记录左偏树，也称为斜堆。是一种基于非平衡二叉树的数据结构，其在合并堆的时候可以达到$O(log(m+1))$的速度。当然，左偏树还分好几种，如左偏高树左偏重树等。关于左偏，实际上就是让左子树的特征数量不小于右子树，例如左偏高树就是左子树的高度不小于右子树。

----
# 定义
>左偏高树的定义是左子树高度不小于右子树，即$height(lson)>=height(rson)$，关于这个**高度**要区别普通二叉树的定义：
>- 普通二叉树的高度定义是左右子树高度的最大值+1，即$h(cur)=max(h(left),h(right))+1$；
>- 左偏高树的定义则是左右子树中高度最小的那个高度值+1，即$h(cur)=min(h(left),h(right))+1$。显然根据定义，一棵左偏树根节点的高度等于右子树的高度+1。实际上，还有一种数据结构的书引入一种$NPL$的概念，但和王晓东书里介绍的高度异曲同工，只不过那个更便于理解，关于NPL可以去看邓老师的数据结构。
>
>关于左偏高树这样定义的好处是能够让每次合并的时候直接在右侧链上的递归深度只有$log(m+1)$，从而达到高效地合并。

---
# 性质
>1，根节点优先级最高，即根的优先级不小于左右孩子的优先级（**堆性**）
    2，左孩子的高度**不小于**右孩子的高度
    3，**根节点的高度等于右孩子的高度+1**（因为高度的定义是两子树中取最小的一个+1）
    4，若有m个结点，则右侧链的长度不超过**log2^(m+1)**
    5，假设右侧链的长度为s，则树的结点个数不小于2^s-1（证明思路：**以右侧链长度为高的树是一个满二叉树**）
    <font color="red">虽然左偏树地定义是左子树的高度大于等于右子树，但实际上右边的**二叉树高度**有可能比左边大，要区别两者概念</font>
    
 例如，在{1，2，3}形成左偏高树后插入一个{4}形成如下：                               
![在这里插入图片描述](https://img-blog.csdnimg.cn/20190917103540969.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbGN1bGF0ZTIz,size_16,color_FFFFFF,t_70)

---
# 实现
## 左偏树结构
关键的两个部分：height使整个结构左偏，less（<运算符重载）运算子赋予结构堆性
```cpp
struct Leftist_Tree {
#define ElemType int

int height; //高度
    ElemType elem; //权值
    Leftist_Tree *lson, *rson; //左右孩子

Leftist_Tree(const ElemType& x, int h):lson(NULL), rson(NULL) {
        elem = x;
        height = h;
    }

bool operator < (const Leftist_Tree& A) const {
        return elem < A.elem;
    }
};
typedef Leftist_Tree LT;
```

---
## 合并
不断地找右侧进行合并，右侧合并完成后调整根结点的左倾性，即比较左右子树的高度，是一个基于后序遍历的算法
```cpp
LT* Merge(LT* &x, LT* &y) {
    if(!x) return y; //如果某一个为空堆就没合并的必要
    if(!y) return x;

if(*x < *y) swap(x, y); //以x的root作为根，显然根的优先级取两者最大的那个
    x->rson = Merge(x->rson, y); //取右侧链进行合并

if(!x->lson) { //发现整个斜堆右倾，左调
        swap(x->lson, x->rson);
        x->height = 1;
    } else { //否则检查一下是否符合左偏树的定义，左调
        if(x->rson->height > x->lson->height) swap(x->lson, x->rson);
        x->height = x->rson->height + 1;
    }
    return x;
}
```

---
## 堆操作
**由于左偏高树能做到高效地合并，所以堆操作都基于合并操作完成**
- 插入，可以构造一个单节点的堆与原堆合并
- 删除，删除掉根节点，剩余左右子堆合并
- 查询，直接返回根节点的elem

---
## 完整代码
```cpp
#include <bits/stdc++.h>
using namespace std;

struct Leftist_Tree {
#define ElemType int
    int height; //高度
    ElemType elem; //权值
    Leftist_Tree *lson, *rson; //左右孩子

Leftist_Tree(const ElemType& x, int h):lson(NULL), rson(NULL) {
        elem = x;
        height = h;
    }

bool operator < (const Leftist_Tree& A) const {
        return elem < A.elem;
    }
};
typedef Leftist_Tree LT;

LT* Merge(LT* &x, LT* &y) {
    if(!x) return y; //如果某一个为空堆就没合并的必要
    if(!y) return x;

if(*x < *y) swap(x, y); //以x的root作为根，显然根的优先级取两者最大的那个
    x->rson = Merge(x->rson, y); //取右侧链进行合并

bool isEmpty(LT* &x) { //判左偏树是否为空
    if(!x) return true;
    return false;
}

bool getTop(LT* &x, ElemType& val) { //得到优先级最高的根
    if(isEmpty(x)) return false;
    val = x->elem;
    return true;
}

bool pop(LT* &x) { //删除优先级最高的根
    if(isEmpty(x)) return false;
    LT* l = x->lson;
    LT* r = x->rson;
    delete x;
    x = Merge(l, r); //先断掉根在合并两个子堆
    return true;
}

bool push(LT* &x, int val) { //入堆
    LT* y = new LT(val, 1);
    if(!y) return false;
    x = Merge(x, y);
    return true;
}

bool heapify(ElemType T[], int n, LT* &x) { //建堆 O(n*Σ(i/2^i)) = O(n)
    queue<LT*> q; while(!q.empty()) q.pop();
    LT *a = NULL, *b = NULL;
    for(int i=0; i<n; i++) q.push(new LT(T[i], 1)); //队列中加入n个高度为1的斜堆
    for(int i=1; i<n; i++) { //合并n-1次 方法和哈夫曼树合并类似 取两个 压一个
        a = q.front(); q.pop();
        b = q.front(); q.pop();
        a = Merge(a, b);
        q.push(a);
    }
    while(!q.empty()) q.pop();
    x = a;
    return true;
}

int main() {
    LT *root = NULL, *t;
    ElemType val;
    int arr[10]={10,9,8,7,6,5,4,3,2,1};

heapify(arr, 10, root);

for(int i=0; i<10; i++) cout << arr[i] <<' ' ; cout << endl;
    
    if( getTop(root, val) == true)
        cout << "val = " << val << '\n';

if( pop(root) == true)
        if( getTop(root, val) == true)
            cout << "val = " << val << '\n';

if( push(root, 4) == true)
        if( getTop(root, val) == true)
            cout << "val = " << val << '\n';

heapify(arr, 10, t);

root = Merge(root, t);

while(getTop(root, val)) {
        cout << val << ' ';
        pop(root);
    }
    cout << '\n';

return 0;
}
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Cactus

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

母牛的故事（C语言代码）

左偏树总结（可合并的优先队列）

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

买不到的数目（C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

核桃的数量（C语言代码）

关于float，double变量的几点说明

输入输出格式练习（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

字符串的修改（C语言代码）

简单的a+b （C语言代码）

Cactus

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

简单的a+b （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

母牛的故事 （C语言代码）

左偏树总结（可合并的优先队列）

评论区

精彩推荐

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

买不到的数目 （C++代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

核桃的数量 （C语言代码）

关于float，double变量的几点说明

输入输出格式练习 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

字符串的修改 （C语言代码）

简单的a+b （C语言代码）

母牛的故事（C语言代码）

母牛的故事（C语言代码）

　　评论区

买不到的数目（C++代码）

核桃的数量（C语言代码）

输入输出格式练习（C语言代码）

字符串的修改（C语言代码）