-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
372 lines (282 loc) · 15.6 KB
/
index.html
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
<!DOCTYPE html>
<html lang="en">
<head>
<link rel="stylesheet" href="css/index.css">
<title> Rank Pairing Heap </title>
</head>
<body>
<block>
<h1> Rank Pairing Heap </h1>
<content> Yuxi Luo - CS3393 Algorithms 2 </content>
</block>
<block>
<title> Introduction </title>
<sub-block>
<title> Initiative </title>
<content>
Rank Pairing Heap is intended to achieve same time complexity as Fibonacci Heap, but have a simpler structure to implement.
<br>
<br>
<div class="content-main">
<table>
<tr>
<td> </td>
<td> Insert </td>
<td> Union </td>
<td> Find Min </td>
<td> Decrease Key </td>
<td> Extract Min </td>
</tr>
<tr>
<th> Fibonacci Heap </th>
<td> O(1) </td>
<td> O(1) </td>
<td> O(1) </td>
<td> O(1) amortized </td>
<td> O(log(n)) amortized </td>
</tr>
<tr>
<th> Rank Pairing Heap </th>
<td> O(1) </td>
<td> O(1) </td>
<td> O(1) </td>
<td> O(1) amortized </td>
<td> O(log(n)) amortized </td>
</tr>
</table>
</div>
</content>
</sub-block>
<sub-block>
<title> Basic Structure </title>
<content>
Rank Pairing Heap uses binary Half Tree, which is an alternative representation of Heap. For a node in Half Tree, its left child is the first left child in Heap, and its right child is the next sibling. Since a root in a Heap does not have any sibling, the root in Half Tree only have left child.
<br>
Half Tree has a property that a node is smaller than any nodes in its left spine.
<br>
<br>
<div class="cy" id="cy-heap"></div>
<h5 style="text-align:center;"> Min-Heap </h5>
<div class="cy" id="cy-half"></div>
<h5 style="text-align:center;"> Half-Tree </h5>
<br>
Rank Pairing Heap contains a set of Half Trees which is linked together with a linked list.
<br>
</content>
</sub-block>
<sub-block>
<title> Rank </title>
<content>
Like Fibonacci Heap, Rank Pairing Heap could grow into arbitrary structure. To maintain a reasonable bound on the level of the tree, it introduces a concept of Rank. It is similar to the concept of level.
Here introduces a Type 2 Rule of Rank for each node N (Assume that the left child is L, and the right child is R):
<ul>
<li> If it is a leaf, Rank = 0 </li>
<li> If it is a root, Rank = 1 + Rank(L) </li>
<li> If |Rank(L) - Rank(R)| <= 1: Rank = 1 + Max(Rank(L), Rank(R)) </li>
<li> If |Rank(L) - Rank(R)| > 1: Rank = Max(Rank(L), Rank(R)) </li>
</ul>
Later in Decrease Key operation, all pairs of Half Trees with same Rank will be linked together, so as to reduce the total number of roots.
</content>
</sub-block>
</block>
<block>
<title> Operations </title>
<content>
(Assume that every node has distinct value)
</content>
<sub-block>
<title> Find Min </title>
<content>
Rank Pairing Heap keeps the first root in the root list to be the current minumum value. In the example below, the minimum is marked as black.
</content>
</sub-block>
<sub-block>
<title> Insert </title>
<content>
When inserting a new node, the node itself becomes a new half-tree, and is linked with current root list. If the node contains the current minimum value, it is added to the front of the list.
<br>
<br>
<form id="insert-form" action="" method="GET">
<input name="insert" id="insert" placeholder="a number to be inserted" required>
<input type="submit" value="submit">
</form>
<div class="cy" id="cy-insert"></div>
</content>
</sub-block>
<sub-block>
<title> Union </title>
<content>
To merge two Rank Pairing Heap, simply merge two root list together, and keep the first root to be the minimum value.
</content>
</sub-block>
<sub-block>
<title> Decrease Key </title>
<content>
To decrease key, there are several steps:
<ol>
<li> Find the target node N and its corresponding subtree T(N). Assume the left child is L, and right child is R. Therefore, T(N) = N + T(L) + T(R) </li>
<li> Split T(N) into two parts: one part is N + T(L), which forms a new Half Tree; the other part is T(R) </li>
<li> Move T(R) to original location of N </li>
<li> Insert the newly-formed Half Tree N + T(L) to the root list </li>
<li> Recalculate Ranks if necessary </li>
</ol>
Click "refresh" to update the graph from last operations
<br>
<br>
<form id="decrease-form" action="" method="GET">
<input name="decrease-key" id="decrease-key" placeholder="key to be decreased" required>
<input name="decrease-val" id="decrease-val" placeholder="new value" required>
<input type="submit" value="submit">
</form>
<form id="decrease-refresh" action="" method="GET">
<input type="button" value="refresh">
</form>
<div class="cy" id="cy-decrease"></div>
</content>
</sub-block>
<sub-block>
<title> Extract Min </title>
<content>
To extract min, there are several steps:
<ul>
<li> Delete the root N of the Half Tree that contains min. Root N has a left child L </li>
<li> For the remaining subtree T(L), recursively splice right spine of current subtree, and add those right spines to the root list </li>
<li> Recalculate Ranks if necessary </li>
</ul>
After delete min, one-pass linking is performed to reduce the total number of roots. A bucket of Ranks are created to keep track of pairs of Half Trees with same Rank. Link any pairs of Half Trees if possible, and add linked Half Trees to new root list.
<br>
One minor detail is that the after linking two Half Trees with same Rank, (unlike Fibonacci Heap), the newly-linked Half Tree will not add back to the bucket for future link.
<br>
<br>
Click "refresh" to update the graph from last operations
<br>
<br>
<form id="extract-form" action="" method="GET">
<input type="submit" value="extract min">
</form>
<form id="extract-refresh" action="" method="GET">
<input type="button" value="refresh">
</form>
<div class="cy" id="cy-extract"></div>
</content>
</sub-block>
<sub-block>
<title> All operations </title>
<ul>
<li> Insert
<form id="insert-all" style="display:inline-block;" action="" method="GET">
<input name="insert" id="insert-" placeholder="a number to be inserted" required>
<input type="submit" value="submit">
</form>
</li>
<li> Decrease Key
<form id="decrease-all" style="display:inline-block;" action="" method="GET">
<input name="decrease-key" id="decrease-key-" placeholder="key to be decreased" required>
<input name="decrease-val" id="decrease-val-" placeholder="new value" required>
<input type="submit" value="submit">
</form>
</li>
<li> Extract Min
<form id="extract-all" style="display:inline-block;" action="" method="GET">
<input type="submit" value="extract">
</form>
</li>
</ul>
<div class="cy" id="cy-all"></div>
</sub-block>
</block>
<block>
<title> Amortization </title>
<sub-block>
<title> Potential Function </title>
<content>
The potential function for this analysis consists of two terms: base potential and extra potential, which depend on rank that is calculated by following rules as introduced above:
<br>
<ul>
<li> If it is a leaf, Rank = 0 </li>
<li> If it is a root, Rank = 1 + Rank(L) </li>
<li> If |Rank(L) - Rank(R)| <= 1: Rank = 1 + Max(Rank(L), Rank(R)) </li>
<li> If |Rank(L) - Rank(R)| > 1: Rank = Max(Rank(L), Rank(R)) </li>
</ul>
The paper describes nodes with respect to the rank differences between a node and its two children: based on the rules, there are three types of nodes in Rank Pairing Heap: (1, 1) node, (1, 2) node, and (0, i) node. For example, (1, 1) node means that the node N has two children, for which both of them have rank Rank(N)-1.
<br>
<br>
Base potential for a node is the sum of rank differences of its children - 1. For example, (1, 1) node has a base potential of 1+1-1 = 1, (1, 2) node has a base potential of 1+2-1 = 2, and (0, i) node has a base potential of i-1.
<br>
<br>
Extra potential for a node is defined as 1 for a root, 0 for a (1, 1) node, and 0 for a (1, 2) node or a (0, i) node.
<br>
<br>
Therefore, the total potential for a node is as follows, and for the entire Rank Pairing Heap is the summation of potentials for all nodes:
<ul>
<li> 0: (1, 1) node </li>
<li> 1: root node </li>
<li> 2: (1, 2) node </li>
<li> i-1: (0, i) node </li>
</ul>
<br>
<br>
Some of the following amortization depends on the level of the tree. For a root with Rank = k, the size of the half tree is bounded similarly as Fibonacci Heap, for which k <= O(logn).
</content>
</sub-block>
<sub-block>
<title> Amortized Find Min, Insert, and Union </title>
<content>
This analysis is simple, since those operations takes O(1) constant time, and at most increase the potential by O(1). In total, they still take O(1) time.
</content>
</sub-block>
<sub-block>
<title> Amortized Decrease Key </title>
<content>
Decrease Key is separated into two parts: 1. Decrease the key of the node and perform necessary restructure to place the half tree of the node to the root list. 2. Recalculate the rank.
<br>
The true cost depends on the number of nodes for which their ranks need to be recalculated, which is at most O(log(n)).
<br>
<br>
The first operation should take O(1) time to form a new half tree rooted by the decreased node, and move its original right tree to become the new left child of its parent.
<br>
<br>
The second operation will decrease ranks for the nodes starting from the parent of the decreased node to maintain above rules. Denote the decreased key N as U1, its left child as U0, and let Ui for i = [2, k] be Ui = parent(Ui-1), such that Uk is either the root or the node that does not decrease in rank.
<br>
For each Ui for i = [2, k], the rank differences drop by at most 1, and the base potential drops except for (1, 1) node: (1, 1) => (1, 2); (1, 2) => (1, 1) or (0, 2); (0, i) => (0, i-1). We could show that there are at most 2 (1, 1) nodes along the path of Ui. Suppose Uj is the first (1, 1) node along the path. Rank(Uj) could at most decrease by 1. Suppose Uj' is the second (1, 1) node where j' > j, because Uj'-1's rank drop by 1, Uj' becomes a (1, 2) node, which still satisfies the rules above. Therefore Rank(Uj') = Rank_new(Uj'), and j' = k.
<br>
Therefore, along the path of Ui for i = [2, k], the total potential drops by k - 1 (from the new half-tree of N that is added to the root list) - 3 (since i starts from 2 instead of 0) - 2 (from the two (1, 1) node) = k - 6.
<br>
<br>
In total, the amortized cost for Decrease Key is therefore O(log(n) - log(n) + 6) = O(1).
</content>
</sub-block>
<sub-block>
<title> Amortized Extract Min </title>
<content>
For Extract Min, the true cost depends on the number of half-trees that are merged together, which is at most O(log(n)).
<br>
There are at most O(log(n)) original (1, 1) nodes on the right spine of the half-tree rooted by L(N) to become a new half-tree. Therefore, the total potential increases by at most O(log(n)).
<br>
<br>
In total, the amortized cost for Extract Min is therefore O(log(n) + log(n)) = O(log(n)).
</content>
</sub-block>
</block>
<block>
<title> About </title>
<content>
<ul>
<li> Github Repo: <a target="_blank" href="https://github.com/Skycocoo/Rank-Pairing-Heap/">Rank-Pairing-Heap</a> </li>
<li> Graph Drawing Tool: <a target="_blank" href="http://js.cytoscape.org/">Cytoscape</a> </li>
<li> Original Paper: <a target="_blank" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.153.4644&rep=rep1&type=pdf">Rank-Pairing Heaps by Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan</a> </li>
</ul>
</content>
</block>
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/cytoscape/3.6.0/cytoscape.min.js"></script>
<script src="https://cdn.rawgit.com/cpettitt/dagre/v0.7.4/dist/dagre.min.js"></script>
<script src="https://cdn.rawgit.com/cytoscape/cytoscape.js-dagre/1.5.0/cytoscape-dagre.js"></script>
<!-- only for local testing -->
<!-- <script src="js/ref/jquery.min.js"></script>
<script src="js/ref/cytoscape.min.js"></script>
<script src="js/ref/dagre.min.js"></script>
<script src="js/ref/cytoscape-dagre.js"></script> -->
<script src="js/cytoscape-node-html-label.min.js"></script>
<script src="js/index.js"></script>
</body>