$Created \ by \ GitSteve1025$

$Web \ Page: $ Data Structure

Splay

Splay 操作规定：每访问一个节点 $x$ 后都要强制将其旋转到根节点。

每次对 $x$ 做一次 splay 步骤， $x$ 到根节点的距离都会更近。

Splay 步骤有三种，具体分为六种情况：

rotate

zig

当 $p$ 是根节点，$x$ 是 $p$ 的左子节点时操作。

zig

zag

当$p$是根节点，$x$是$p$的右子节点时操作。

zag

zig-zig

当 $p$ 不是根节点，$p$ 和 $x$ 都是左子节点时操作。

zig-zig

zag-zag

当$p$不是根节点， $p$ 和 $x$ 都是右子节点时操作。

zag-zag

zig-zag

当 $p$ 不是根节点，$p$ 是左子节点， $x$ 是右子节点时操作。

zig-zag

zag-zig

当 $p$ 不是根节点，$p$ 是右子节点， $x$ 是左子节点时操作。

zag-zig

可以看出 zig 和 zag 互为镜像操作

更详细的教程 Splay

Hash

Hash function

得到 $key$ ，一般是 $X \ mod \ TableSize$ 。

Solve collision

分离链接法 (separate chaining)

将散列到同一个值的所有元素保留的一个链表。

分离链接法

探测法 (probing)

线性探测法

碰撞就往下找（每次走一格），直到找到空位填。 $f(i) = i$

例：将 $(89, 18, 49, 58, 69)$ 放入大小为 $10$ 的表。

线性探测法

平方探测法

碰撞就往下找（每次走平方数格，即 $1, 4, 9, …$ ）。 直到找到空位填。 $f(i) = i^{2}$

例：将 $(89, 18, 49, 58, 69)$ 放入大小为 $10$ 的表。

平方探测法

双散列 (double hashing)

碰撞就往下找（每次走 $hash_2(x)$ 格，即 $hash_{2}(x), 2hash_{2}(x), 3hash_{2}(x), …$ ）。 直到找到空位填。 $f(i) = i \times hash_{2}(x)$

例：将 $(89, 18, 49, 58, 69)$ 放入大小为 $10$ 的表。 $hash_{2}(x) = R - (x \ mod \ R)$ ， $R = 7$

双散列

再散列 (rehashing)

将原来的表散列到新表， 新表一般为旧表两倍大。

Sort

QuickSort

平均 $O(N \ log \ N)$ ，最坏 $O(N^{2})$

算法步骤：

  1. 如果 $|S| \le 1 \quad return$
  2. 取 $S$ 中某一元素 $v$ 当作枢纽元 $(pivot)$
  3. 将 $S$ 划分为两个不相交的集合， $S_{1} = \lbrace x \in S \wedge x < v \rbrace$ ，$S_{2} = \lbrace x \in S \wedge x > v \rbrace$
  4. $return \ quicksort(S_{1}) + \lbrace v \rbrace + quicksort(S_{2})$

三数中值分割法 (Median-of-Three Partitioning)

左端点 $left$ ，右端点 $right$ ，选择的枢纽元 $\lfloor (left + right) / 2 \rfloor$

Cpp Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class T>
void quicksort(vector<T>& items) {
    int n = items.size();
    if (n <= 1) {
        return;
    }
    vector<T> smaller, same, larger;
    int pivot = items[n / 2];
    //int pivot = items[rand() % n]; // 更快
    for (auto x : items) {
        if (x < pivot) {
            smaller.push_back(x);
        }else if (x > pivot) {
            larger.push_back(x);
        }else {
            same.push_back(x);
        }
    }
    quicksort(smaller);
    quicksort(larger);
    move(smaller.begin(), smaller.end(), items.begin());
    move(same.begin(), same.end(), items.begin() + smaller.size());
    move(larger.begin(), larger.end(), items.end() - larger.size());
}

Python Code

1
2
3
4
5
6
7
8
9
def quicksort(items) :
    if len(items) <= 1 :
        return items
    # pivot = items[len(items) // 2]
    pivot = items[random.randint(0, len(items) - 1)] # 更快
    smaller = [x for x in items if x < pivot]
    larger = [x for x in items if x > pivot]
    same = [x for x in items if x == pivot]
    return quicksort(smaller) + same + quicksort(larger)

MergeSort

平均 $O(N \ log \ N)$ ，最坏 $O(N \ log \ N)$

mergesort

Cpp Code

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
template<class T>
void mergesort(vector<T>& items) {
    auto temp = items;
    auto Merge = [&](int left, int right) -> void {
        int middle = (left + right) / 2;
        int fp = left, sp = middle + 1;
        int cp = left;
        while (fp <= middle && sp <= right) {
            if (items[fp] <= items[sp]) {
                temp[cp] = items[fp];
                fp++;
            }else {
                temp[cp] = items[sp];
                sp++;
            }
            cp++;
        }

        while (fp <= middle) {
            temp[cp] = items[fp];
            fp++;
            cp++;
        }

        while (sp <= right) {
            temp[cp] = items[sp];
            sp++;
            cp++;
        }

        for (int i = left; i <= right; i++) {
            items[i] = temp[i];
        }
    };

    auto Mergesort = [&](auto self, int left, int right) -> void {
        if (left == right) {
            return;
        }
        int middle = (left + right) / 2;
        self(self, left, middle);
        self(self, middle + 1, right);
        Merge(left, right);
    };

    Mergesort(Mergesort, 0, items.size() - 1);
}

HeapSort

平均 $O(N \ log \ N)$ ，最坏 $O(N \ log \ N)$

首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；

以此类推，在第 $n - 1$ 次操作后，整个数组就完成了排序。

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
template<class T>
void heapsort(vector<T>& items) {
    auto movedown = [&](int start, int end) -> void {
        int parent = start;
        int child = parent * 2 + 1;
        while (child <= end) {
            if (child <= end - 1 && items[child] < items[child + 1]) {
                child++;
            }

            if (items[child] > items[parent]) {
                swap(items[child], items[parent]);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    };

    for (int i = items.size() / 2 - 1; i >= 0; i--) {
        movedown(i, items.size() - 1);
    }

    for (int i = items.size() - 1; i > 0; i--) {
        swap(items[0], items[i]);
        movedown(0, i - 1);
    }
}

Huffman

把字符出现的频率当权值，放入小根堆， 每次取出两个最小值，合成新的节点，其权值等于被合并二者值相加。放入堆中，重复操作，直到堆中只剩一个元素。

例； $A, B, C, D$ 出现频率分别为 $35, 25, 15, 15, 10$ 形成的树。（一般取父节点到左子树为 0）

Huffman Coding

Cpp Code

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//Huffman Tree's Node
struct HuffmanTreeNode
{
	char character;// character 
	int frequency;// frequency of char character
	HuffmanTreeNode* left;//left Node
	HuffmanTreeNode* right;//right Node
	HuffmanTreeNode()
	{
		character = 0;
		frequency = 0;
		left = 0;
		right = 0;
	}

	HuffmanTreeNode(char _character, int _frequency)//Init Node with character and frequency
	{
		character = _character;
		frequency = _frequency;
		left = 0;
		right = 0;
	}

	HuffmanTreeNode(HuffmanTreeNode* _left, HuffmanTreeNode* _right)//Init Node with left and right
	{
		character = 0;
		frequency = _left->frequency + _right->frequency;
		left = _left;
		right = _right;
	}

	HuffmanTreeNode(char _character, int _frequency, HuffmanTreeNode* _left, HuffmanTreeNode* _right)//Init Node with character, frequency, left and right
	{
		character = _character;
		frequency = _frequency;
		left = _left;
		right = _right;
	}
};

struct less//HuffmanTreeNode* compare with frequency  less compare
{
	bool operator()(HuffmanTreeNode*& left_node, HuffmanTreeNode*& right_node) const
	{
		return left_node->frequency < right_node->frequency;
	}
};

struct greater//HuffmanTreeNode* compare with frequency  greater compare
{
	bool operator()(HuffmanTreeNode*& left_node, HuffmanTreeNode*& right_node) const
	{
		return left_node->frequency > right_node->frequency;
	}
};

//HuffmanTree
class HuffmanTree
{
public:
	HuffmanTree()
	{
		root = 0;
	}

	HuffmanTree(std::string filepath);

	std::vector<std::pair<char, std::string>> getcode() const;

private:
	void Encode(HuffmanTreeNode* node, std::string code = "");

private:
	HuffmanTreeNode* root;
	std::vector<std::pair<char, std::string>> Huffman_Encode;
};

HuffmanTree::HuffmanTree(std::string filepath)
{
	root = 0;
	std::fstream fin(filepath, std::ios::in);
	if (!fin)//open failed
	{
		std::cerr << "filepath: " << filepath << " is wrong" << std::endl;
		return;
	}

	std::string data;
	std::map<char, int> cnt;
	while (fin >> data)//read data
	{
		for (auto& x : data)//foreach data and calculate the frequency of character
		{
			cnt[x] += 1;
		}
	}

	std::priority_queue<HuffmanTreeNode*, std::vector<HuffmanTreeNode*>, greater> q;//use priority_queue to build tree
	for (auto& [character, frequency] : cnt)
	{
		HuffmanTreeNode* node = new HuffmanTreeNode(character, frequency);
		q.push(node);
	}

	while (!q.empty())//build HuffmanTree
	{
		if (q.size() > 1)//keep building tree
		{
			auto left_node = q.top();
			q.pop();
			auto right_node = q.top();
			q.pop();
			auto node = new HuffmanTreeNode(left_node, right_node);
			q.push(node);
		}
		else // find root
		{
			root = q.top();
			q.pop();
		}
	}

	if (root != 0)//Encode
	{
		Encode(root);
	}
}

std::vector<std::pair<char, std::string>> HuffmanTree::getcode() const
{
	return Huffman_Encode;
}

void HuffmanTree::Encode(HuffmanTreeNode* node, std::string code)
{
	if (node->left)//not leaf
	{
		Encode(node->left, code + "0");//left encode to 0
		Encode(node->right, code + "1");//right encode to 1
	}
	else//leaf
	{
		Huffman_Encode.push_back({ node->character, code });//get encode
	}
}

DSU

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

  • 合并（Union）：合并两个元素所属集合（合并对应的树）
  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

Cpp Code

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
struct DSU {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};