左偏堆 | Kyons'Blog 


 




左偏堆

发表于 | 分类于 | | 阅读次数:

一.序

强烈安利<数据结构与算法分析-c语言描述>这本书!!!
更好的讲解可阅读该书.或者看这位大佬的博客%%

二.用处

这个左式堆啊~直接当作可以合并的二叉堆来理解,这是再最好不过的了,其他和堆没啥区别.

三.基本概念

零路径长（$null\ pathength$）
$Npl(X)$：
结点$X$到一个没有两个儿子的结点的最短路径的长度。
这里我们定义没有两个儿子的结点的$Npl(x)=1$；$Npl(NULL) = 0$。

左堆和堆一样，也具有结构性质和堆序性质。左堆的结构性质是指：对于堆中的每一个结点$X$，它的左儿子的零路径长要不小于其右儿子的零路径长。
堆序信息与堆的一样，即：最小的结点应该是根节点，鉴于我们希望子树也是堆，那么每个子树的根节点也应该是最小的
这一性质必然会导致左堆是一个极其不平衡的树。
书上原话

四.合并

每次合并都从右子树开始合并.这图我也看不大懂,大致理解就好了.反正代码写出来,感觉和图的方法没大关系
1

五.代码实现

(一).结构

1
2
3
4
5
typedef struct heap* nd;
struct heap {
    int d, npl;
    nd lson, rson;
}*root;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
### (二).合并
```cpp
nd merge(nd p, nd ip)
{
    if (p == NULL)
        return ip;
    if (ip == NULL)
        return p;
    if (ip->d > p->d)        //堆,小根<,大根>
        swap(p, ip);
    if (p->lson == NULL)
        p->lson = ip;
    else {
        p->rson = merge(p->rson, ip);
        if (p->lson->npl < p->rson->npl)    //保证性质不变
            swap(p->lson, p->rson);
        p->npl = p->rson->npl + 1;    //合并后,根节点的npl距离取右儿子的距离+1
    }
    return p;
}

(三).插入

插入这个命令,可以理解为,一个单个数的堆,与大堆合并.
即把要插入的数当作一个堆,与要插入的堆合并即可.

1
2
3
4
5
6
7
8
9
10
11
nd insert(nd p, int x)
{
    nd ip = (nd)malloc(sizeof(struct heap));
    if (ip == NULL) {
        cout << "error insert" << endl;
        exit(65530);
    }
    ip->lson = ip->rson = NULL;
    ip->npl = 0, ip->d = x;
    return p = merge(p, ip);
}

(四).删除

删除堆首的值,可以理解为,将堆根节点的左右儿子分成两个堆,然后再合并成一个新的堆.

1
2
3
4
5
6
7
8
9
10
nd pop(nd p)
{
    if (p == NULL) {
        cout << "error pop" << endl;
        exit(65530);
    }
    nd lp = p->lson, rp = p->rson;
    free(p);
    return merge(lp, rp);
}

(五).样例代码

指针实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#ifndef NULL
#define NULL 0;
#endif
using namespace std;

typedef struct heap* nd;
struct heap {
    int d, npl;
    nd lson, rson;
}*root;
void close(nd p)
{
    if (p == NULL)
        return;
    close(p->lson),close(p->rson);
    delete(p);
}
nd merge(nd p, nd ip)
{
    if (p == NULL)
        return ip;
    if (ip == NULL)
        return p;
    if (ip->d > p->d)        //堆的小根<,大根>
        swap(p, ip);
    if (p->lson == NULL)
        p->lson = ip;
    else {
        p->rson = merge(p->rson, ip);
        if (p->lson->npl < p->rson->npl)
            swap(p->lson, p->rson);
        p->npl = p->rson->npl + 1;
    }
    return p;
}
nd pop(nd p)
{
    if (p == NULL) {
        cout << "error pop" << endl;
        exit(65530);
    }
    nd lp = p->lson, rp = p->rson;
    free(p);
    return merge(lp, rp);
}
nd insert(nd p, int x)
{
    nd ip = (nd)malloc(sizeof(struct heap));
    if (ip == NULL) {
        cout << "error insert" << endl;
        exit(65530);
    }
    ip->lson = ip->rson = NULL;
    ip->npl = 0, ip->d = x;
    return p = merge(p, ip);
}
数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#define MAXN 150010
#define lson(x) S[x].Son[0]
#define rson(x) S[x].Son[1]
struct Tree {
    int dis, val, Son[2], fa;
} S[MAXN];

inline int Merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (S[x].val > S[y].val || (S[x].val == S[y].val && x > y))
        swap(x, y);
    rson(x) = Merge(rson(x), y);
    if (S[lson(x)].dis < S[rson(x)].dis)
        swap(lson(x), rson(x));
    S[lson(x)].fa = S[rson(x)].fa = S[x].fa = x;
    S[x].dis = S[rson(x)].dis + 1;
    return x;
}
inline int ffa(int x)
{
    return S[x].fa == x ? x : S[x].fa = ffa(S[x].fa);
}
inline void Pop(int x)
{
    S[x].val = -1;
    S[lson(x)].fa = lson(x), S[rson(x)].fa = rson(x);
    S[x].fa = Merge(lson(x), rson(x));
}

int main()
{
    int n,m;
    cin >> n >> m;
    S[0].dis = -1;
    for (int i = 1; i <= n; ++i){
        S[i].fa = i;
        scanf("%d", &S[i].val);
    }
    for (int i = 1; i <= m; ++i) {
        int t,x,y;
        cin>>t;
        if (t == 1) {
            cin>>x>>y;
            if (S[x].val == -1 || S[y].val == -1)
                continue;
            int fx = ffa(x), fy = ffa(y);
            if (fx != fy)
                S[fx].fa = S[fy].fa = Merge(fx, fy);
        } else {
            cin>>x;
            if (S[x].val == -1)
                printf("-1\n");
            else
                printf("%d\n", S[ffa(x)].val), Pop(ffa(x));
        }
    }
    return 0;
}

例题

(hdu 1512) Monkey King

http://acm.hdu.edu.cn/showproblem.php?pid=1512

Problem Description

Once in a forest, there lived $N$ aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can’t avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.
Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, $10$ will be reduced to $5$ and $5$ will be reduced to $2$).
And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

Input

There are several test cases, and each case consists of two parts.
First part: The first line contains an integer $N$($N\leq100000$), which indicates the number of monkeys. And then $N$ lines follows. There is one number on each line, indicating the strongness value of ith monkey($\leq32768$).
Second part: The first line contains an integer $M$($M\leq100000$), which indicates there are $M$ conflicts happened. And then $M$ lines follows, each line of which contains two integers $x$ and $y$, indicating that there is a conflict between the $X_{th}$ monkey and $Y_{th}$.

Output

For each of the conflict, output $-1$ if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.
Sample Input
5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
Sample Output
8
5
5
-1
10
Author
JIANG, Yanyan
Source
ZOJ 3rd Anniversary Contest
Recommend
linle

解析

一开始有$n$只孤独的猴子，然后他们要打$m$次架，每次打架呢，都会拉上自己朋友最牛叉的出来跟别人打，打完之后战斗力就会减半，每次打完架就会成为朋友（正所谓不打不相识o(∩_∩)o）。问每次打完架之后那俩猴子最牛叉的朋友战斗力还有多少，若朋友打架就输出$-1$.

并查集+可并堆
每次猴子和猴子打架做朋友,就并在一起.
每次要打架就查一下是不是在一起的朋友,不是就打架,是就输出$-1$.

在经历了无数次$re$和$mle$后,我把$close$函数删了==,遗留的指针遗留就遗留吧.就$ac$了…….$wtf$
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <algorithm>
#include<cstring>
#include <cstdio>
#ifndef NULL
#define NULL 0;
#endif
using namespace std;

typedef struct heap* nd;
struct heap {
    int d, npl;
    nd lson, rson;
}*root;
struct vec {
    int d,fa;
    nd p;
    vec() {
        d = 0, p = NULL;
    }
}a[101000];
void close(nd p)
{
    if (p == NULL)
        return;
    close(p->lson);
    close(p->rson);
    delete(p);
}
nd merge(nd p, nd ip)
{
    if (p == NULL)
        return ip;
    if (ip == NULL)
        return p;
    if (ip->d > p->d)        //堆的小根<,大根>
        swap(p, ip);
    if (p->lson == NULL)
        p->lson = ip;
    else {
        p->rson = merge(p->rson, ip);
        if (p->lson->npl < p->rson->npl)
            swap(p->lson, p->rson);
        p->npl = p->rson->npl + 1;
    }
    return p;
}
nd pop(nd p)
{
    if (p == NULL) {
        cout << "error pop" << endl;
        exit(65530);
    }
    nd lp = p->lson, rp = p->rson;
    free(p);
    return merge(lp, rp);
}
nd insert(nd p, int x)
{
    nd ip = (nd)malloc(sizeof(struct heap));
    if (ip == NULL) {
        cout << "error insert" << endl;
        exit(65530);
    }
    ip->lson = ip->rson = NULL;
    ip->npl = 0, ip->d = x;
    return p = merge(p, ip);
}
int top(nd p)
{
    return p->d;
}
int ffa(int x)
{
    if (x == a[x].fa)
        return x;
    return a[x].fa=ffa(a[x].fa);
}
int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c<'0' || c>'9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int main()
{
    int n, m;
    while (~scanf("%d",&n)) {
        for (int i = 1; i <= n; i++) {
            a[i].d=read();
            a[i].fa = i;
            a[i].p = insert(a[i].p, a[i].d);
        }
        m=read();
        for (int i = 1; i <= m; i++) {
            int x, y, fx, fy;
            x=read(),y=read();
            fx = ffa(x), fy = ffa(y);
            if (fx != fy) {
                a[fy].fa = fx;
                int num1 = top(a[fx].p) / 2, num2 = top(a[fy].p) / 2;
                a[fx].p = pop(a[fx].p);
                a[fy].p = pop(a[fy].p);
                a[fx].p = a[fy].p = merge(a[fx].p, a[fy].p);
                a[fx].p = a[fy].p = insert(a[fx].p, num1);
                a[fx].p = a[fy].p = insert(a[fx].p, num2);
                cout << top(a[fx].p) << endl;
            }
            else
                cout << -1 << endl;
        }
        for (int i = 1; i <= n; i++) 
            a[i].p = NULL;
    }
    return 0;
}







 




 


 


 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载