-
Notifications
You must be signed in to change notification settings - Fork 0
/
data-structures-and-algorithms-1.html
3740 lines (3153 loc) · 868 KB
/
data-structures-and-algorithms-1.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
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html SYSTEM "about:legacy-compat">
<html lang="en-US" data-preset="contrast" data-primary-color="#6860F6" data-link-color="#307FFF" data-resizable-sidebar="true" data-sidebar-width="260"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><meta charset="UTF-8"><meta name="built-on" content="2024-12-10T15:14:05.5745668"><title>Part Ⅰ | Computer Science Study Notes</title><script type="application/json" id="virtual-toc-data">[{"id":"2-linked-lists","level":0,"title":"2 Linked Lists","anchor":"#2-linked-lists"},{"id":"2-1-singly-linked-lists","level":1,"title":"2.1 Singly Linked Lists","anchor":"#2-1-singly-linked-lists"},{"id":"2-2-doubly-linked-lists-deques","level":1,"title":"2.2 Doubly Linked Lists \u0026 Deques","anchor":"#2-2-doubly-linked-lists-deques"},{"id":"3-union-find","level":0,"title":"3 Union-Find","anchor":"#3-union-find"},{"id":"3-1-quick-find-eager-approach","level":1,"title":"3.1 Quick Find (Eager Approach)","anchor":"#3-1-quick-find-eager-approach"},{"id":"3-2-quick-union-lazy-approach","level":1,"title":"3.2 Quick Union (Lazy Approach)","anchor":"#3-2-quick-union-lazy-approach"},{"id":"3-3-quick-union-improvements","level":1,"title":"3.3 Quick Union Improvements","anchor":"#3-3-quick-union-improvements"},{"id":"4-bags-queues-and-stacks","level":0,"title":"4 Bags, Queues and Stacks","anchor":"#4-bags-queues-and-stacks"},{"id":"4-1-stacks","level":1,"title":"4.1 Stacks","anchor":"#4-1-stacks"},{"id":"4-1-1-built-in-stacks","level":2,"title":"4.1.1 Built-In Stacks","anchor":"#4-1-1-built-in-stacks"},{"id":"4-1-2-linked-list-implementation","level":2,"title":"4.1.2 Linked-List Implementation","anchor":"#4-1-2-linked-list-implementation"},{"id":"4-1-3-resizing-array-implementation","level":2,"title":"4.1.3 Resizing-Array Implementation","anchor":"#4-1-3-resizing-array-implementation"},{"id":"4-2-queues","level":1,"title":"4.2 Queues","anchor":"#4-2-queues"},{"id":"4-2-1-built-in-queues","level":2,"title":"4.2.1 Built-in Queues","anchor":"#4-2-1-built-in-queues"},{"id":"4-2-2-queue-implementation","level":2,"title":"4.2.2 Queue Implementation","anchor":"#4-2-2-queue-implementation"},{"id":"4-3-generics","level":1,"title":"4.3 Generics","anchor":"#4-3-generics"},{"id":"4-4-iterators","level":1,"title":"4.4 Iterators","anchor":"#4-4-iterators"},{"id":"4-5-bag-princeton","level":1,"title":"4.5 Bag (Princeton)","anchor":"#4-5-bag-princeton"},{"id":"5-elementary-sorts","level":0,"title":"5 Elementary Sorts","anchor":"#5-elementary-sorts"},{"id":"selection-sort","level":1,"title":"5.1 Selection Sort","anchor":"#selection-sort"},{"id":"insertion-sort","level":1,"title":"5.2 Insertion Sort","anchor":"#insertion-sort"},{"id":"shell-sort","level":1,"title":"5.3 Shell Sort","anchor":"#shell-sort"},{"id":"5-4-shuffling","level":1,"title":"5.4 Shuffling","anchor":"#5-4-shuffling"},{"id":"convex-hull","level":1,"title":"5.5 Convex Hull","anchor":"#convex-hull"},{"id":"mergesort","level":0,"title":"6. Mergesort","anchor":"#mergesort"},{"id":"6-1-mergesort","level":1,"title":"6.1 Mergesort","anchor":"#6-1-mergesort"},{"id":"6-2-bottom-up-mergesort","level":1,"title":"6.2 Bottom-Up Mergesort","anchor":"#6-2-bottom-up-mergesort"},{"id":"6-3-computational-complexity","level":1,"title":"6.3 Computational Complexity","anchor":"#6-3-computational-complexity"},{"id":"6-4-stability","level":1,"title":"6.4 Stability","anchor":"#6-4-stability"},{"id":"quicksort","level":0,"title":"7 Quicksort","anchor":"#quicksort"},{"id":"7-1-quicksort","level":1,"title":"7.1 Quicksort","anchor":"#7-1-quicksort"},{"id":"7-2-selection","level":1,"title":"7.2 Selection","anchor":"#7-2-selection"},{"id":"3-way-partitioning","level":1,"title":"7.3 Duplicate Keys","anchor":"#3-way-partitioning"},{"id":"8-priority-queues","level":0,"title":"8 Priority Queues","anchor":"#8-priority-queues"},{"id":"8-1-api-and-elementary-implementations","level":1,"title":"8.1 API and Elementary Implementations","anchor":"#8-1-api-and-elementary-implementations"},{"id":"8-2-binary-heap","level":1,"title":"8.2 Binary Heap","anchor":"#8-2-binary-heap"},{"id":"8-1-1-concepts-properties","level":2,"title":"8.1.1 Concepts \u0026 Properties","anchor":"#8-1-1-concepts-properties"},{"id":"8-1-2-binary-heap-implementation-of-priority-queues","level":2,"title":"8.1.2 Binary-Heap Implementation of Priority Queues","anchor":"#8-1-2-binary-heap-implementation-of-priority-queues"},{"id":"8-3-indexed-priority-queue","level":1,"title":"8.3 Indexed Priority Queue","anchor":"#8-3-indexed-priority-queue"},{"id":"heapsort","level":1,"title":"8.4 Heapsort","anchor":"#heapsort"}]</script><script type="application/json" id="topic-shortcuts"></script><link href="https://resources.jetbrains.com/writerside/apidoc/6.10.0-b518/app.css" rel="stylesheet"><link href="static/custom.css" rel="stylesheet"><link rel="icon" type="image/png" sizes="16x16" href="Computer-Science-Study-Notes/photo.png"><meta name="image" content=""><!-- Open Graph --><meta property="og:title" content="Part Ⅰ | Computer Science Study Notes"><meta property="og:description" content=""><meta property="og:image" content=""><meta property="og:site_name" content="Computer Science Study Notes Help"><meta property="og:type" content="website"><meta property="og:locale" content="en_US"><meta property="og:url" content="writerside-documentation/data-structures-and-algorithms-1.html"><!-- End Open Graph --><!-- Twitter Card --><meta name="twitter:card" content="summary_large_image"><meta name="twitter:site" content=""><meta name="twitter:title" content="Part Ⅰ | Computer Science Study Notes"><meta name="twitter:description" content=""><meta name="twitter:creator" content=""><meta name="twitter:image:src" content=""><!-- End Twitter Card --><!-- Schema.org WebPage --><script type="application/ld+json">{
"@context": "http://schema.org",
"@type": "WebPage",
"@id": "writerside-documentation/data-structures-and-algorithms-1.html#webpage",
"url": "writerside-documentation/data-structures-and-algorithms-1.html",
"name": "Part Ⅰ | Computer Science Study Notes",
"description": "",
"image": "",
"inLanguage":"en-US"
}</script><!-- End Schema.org --><!-- Schema.org WebSite --><script type="application/ld+json">{
"@type": "WebSite",
"@id": "writerside-documentation/#website",
"url": "writerside-documentation/",
"name": "Computer Science Study Notes Help"
}</script><!-- End Schema.org --></head><body data-id="Data-Structures-and-Algorithms-1" data-main-title="Part Ⅰ" data-article-props="{"seeAlsoStyle":"links"}" data-template="article" data-breadcrumbs="Data-Structures-and-Algorithms.topic|Data Structures and Algorithms"><div class="wrapper"><main class="panel _main"><header class="panel__header"><div class="container"><h3>Computer Science Study Notes Help</h3><div class="panel-trigger"></div></div></header><section class="panel__content"><div class="container"><article class="article" data-shortcut-switcher="inactive"><h1 data-toc="Data-Structures-and-Algorithms-1" data-label-id="finish" id="Data-Structures-and-Algorithms-1.topic">Part Ⅰ</h1><section class="chapter"><h2 id="2-linked-lists" data-toc="2-linked-lists">2 Linked Lists</h2><p id="-9quly7_12">The sentinel reference always points to a sentinel node.</p><p id="-9quly7_13">Sentinel code make it easier to reason about code, and also give you specific goals to strive for in making sure your code works.</p><figure id="-9quly7_14"><img alt="Sentinel Node" src="Computer-Science-Study-Notes/d2-1-1.png" title="Sentinel Node" width="1200" height="284"></figure><section class="chapter"><h3 id="2-1-singly-linked-lists" data-toc="2-1-singly-linked-lists">2.1 Singly Linked Lists</h3><p id="-9quly7_17">The first item (if it exists) is at <code class="code" id="-9quly7_20">sentinel.next</code>.</p><p id="-9quly7_18">No need to check for special cases since sentinel node is never null!</p><div class="tabs" id="-9quly7_19" data-anchors="[-9quly7_21,-9quly7_22,-9quly7_23]"><div class="tabs__content" data-gtm="tab" id="-9quly7_21" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="import java.util.Iterator;">
import java.util.Iterator;
public class SLList implements Iterable<Integer> {
public static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
private final IntNode sentinel;
private int size;
public SLList() {
sentinel = new IntNode(63, null);
size = 0;
}
public SLList(int x) {
sentinel = new IntNode(63, null);
sentinel.next = new IntNode(x, null);
size = 1;
}
public void addFirst(int x) {
sentinel.next = new IntNode(x, sentinel.next);
size += 1;
}
public void addLast(int x) {
size += 1;
IntNode p = sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
public int size() {
return size;
}
public Iterator<Integer> iterator() {
return new SLListIterator();
}
private class SLListIterator implements Iterator<Integer> {
private IntNode p;
public SLListIterator() {
p = sentinel.next;
}
public boolean hasNext() {
return p != null;
}
public Integer next() {
int returnItem = p.item;
p = p.next;
return returnItem;
}
}
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_22" data-title="C++"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="#include <iostream>">
#include <iostream>
template <typename T>
class SLList {
public:
class IntNode {
public:
T item;
IntNode* next;
IntNode(T i, IntNode* n) {
item = i;
next = n;
}
};
private:
IntNode* sentinel;
int size;
public:
SLList() {
sentinel = new IntNode(63, nullptr);
size = 0;
}
explicit SLList(T x) {
sentinel = new IntNode(63, nullptr);
sentinel->next = new IntNode(x, nullptr);
size = 1;
}
void addFirst(T x) {
sentinel->next = new IntNode(x, sentinel->next);
size += 1;
}
void addLast(T x) {
size += 1;
IntNode* p = sentinel;
while (p->next != nullptr) {
p = p->next;
}
p->next = new IntNode(x, nullptr);
}
[[nodiscard]] int size_() const {
return size;
}
class iterator {
private:
IntNode* current;
public:
explicit iterator(IntNode* start) : current(start) {}
T& operator*() { return current->item; }
iterator& operator++() { current = current->next; return *this; }
bool operator!=(const iterator& other) const { return current != other.current; }
};
iterator begin() { return iterator(sentinel->next); }
iterator end() { return iterator(nullptr); }
};
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_23" data-title="Python"><div class="code-collapse" data-lang="python" data-title="Python" data-is-expanded="false" data-synopsis="class SLList:">
class SLList:
class IntNode:
def __init__(self, i, n):
self.item = i
self.next = n
def __init__(self, x=None):
self.sentinel = self.IntNode(None, None)
self.size = 0
if x is not None: # If x is provided, add it as the first element
self.sentinel.next = self.IntNode(x, None)
self.size = 1
def addFirst(self, x):
self.sentinel.next = self.IntNode(x, self.sentinel.next)
self.size += 1
def addLast(self, x):
p = self.sentinel
while p.next is not None:
p = p.next
p.next = self.IntNode(x, None)
self.size += 1
def __len__(self):
return self.size
def __iter__(self):
p = self.sentinel.next
while p is not None:
yield p.item
p = p.next
</div></div></div></section><section class="chapter"><h3 id="2-2-doubly-linked-lists-deques" data-toc="2-2-doubly-linked-lists-deques">2.2 Doubly Linked Lists & Deques</h3><aside class="prompt" data-type="tip" data-title="" id="-9quly7_27"><p id="-9quly7_34">Doubly linked lists and deques share many similarities.</p></aside><aside class="prompt" data-type="note" data-title="" id="-9quly7_28"><p id="-9quly7_35">This is the use of built-in doubly linked lists.</p></aside><div class="tabs" id="-9quly7_29" data-anchors="[-9quly7_36,-9quly7_37,-9quly7_38]"><div class="tabs__content" data-gtm="tab" id="-9quly7_36" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="import java.util.LinkedList;">
import java.util.LinkedList;
public class DLList {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.addLast("C");
linkedList.addFirst("D");
linkedList.add(2, "E");
System.out.println("Linked list : " + linkedList);
}
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_37" data-title="C++"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="#include <list>">
#include <list>
#include <iostream>
int main() {
std::list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
for(auto i : myList) {
std::cout << i << " ";
}
return 0;
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_38" data-title="Python (Deque)"><div class="code-collapse" data-lang="python" data-title="Python" data-is-expanded="false" data-synopsis="from collections import deque">
from collections import deque
# Initialize a deque
my_deque = deque([1, 2, 3])
# Append to the right
my_deque.append(4)
print("Deque after appending 4:", my_deque) # Output: deque([1, 2, 3, 4])
# Append to the left
my_deque.appendleft(0)
print("Deque after appending 0 to the left:", my_deque) # Output: deque([0, 1, 2, 3, 4])
# Pop from the right
popped_right = my_deque.pop()
print("Popped element from the right:", popped_right) # Output: 4
print("Deque after popping from the right:", my_deque) # Output: deque([0, 1, 2, 3])
# Pop from the left
popped_left = my_deque.popleft()
print("Popped element from the left:", popped_left) # Output: 0
print("Deque after popping from the left:", my_deque) # Output: deque([1, 2, 3])
# Rotate the deque (positive value rotates to the right)
my_deque.rotate(2)
print("Deque after rotating 2 positions to the right:", my_deque) # Output: deque([2, 3, 1])
# Rotate the deque (negative value rotates to the left)
my_deque.rotate(-1)
print("Deque after rotating 1 position to the left:", my_deque) # Output: deque([3, 1, 2])
# You can also use deque as a fixed-size queue with maxlen
limited_deque = deque(maxlen=3)
limited_deque.extend([1, 2, 3, 4]) # Oldest element (1) will be automatically removed
print("Limited deque:", limited_deque) # Output: deque([2, 3, 4], maxlen=3)
</div></div></div><aside class="prompt" data-type="note" data-title="" id="-9quly7_30"><p id="-9quly7_42">This is the implementation of doubly linked lists and linked list implementation of deques.</p></aside><div class="tabs" id="-9quly7_31" data-anchors="[-9quly7_43,-9quly7_44,-9quly7_45]"><div class="tabs__content" data-gtm="tab" id="-9quly7_43" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="import java.util.ArrayList;">
import java.util.ArrayList;
public class LinkedList<T> {
private class Node {
public T item;
public Node prev;
public Node next;
public Node(T i, Node p, Node n) {
item = i;
prev = p;
next = n;
}
}
private final Node sentinel;
private int size;
public LinkedList() {
sentinel = new Node(null, null, null);
sentinel.prev = sentinel;
sentinel.next = sentinel;
size = 0;
}
public void addFirst(T x) {
Node newNode = new Node(x, sentinel, sentinel.next);
sentinel.next.prev = newNode;
sentinel.next = newNode;
size++;
}
public void addLast(T x) {
Node newNode = new Node(x, sentinel.prev, sentinel);
sentinel.prev.next = newNode;
sentinel.prev = newNode;
size++;
}
public ArrayList<T> toList() {
ArrayList<T> returnList = new ArrayList<>();
Node p = sentinel.next;
while (p != sentinel) {
returnList.add(p.item);
p = p.next;
}
return returnList;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public T removeFirst() {
if (isEmpty()) {
return null;
}
Node first = sentinel.next;
sentinel.next = first.next;
first.next.prev = sentinel;
size--;
return first.item;
}
public T removeLast() {
if (isEmpty()) {
return null;
}
Node last = sentinel.prev;
sentinel.prev = last.prev;
last.prev.next = sentinel;
size--;
return last.item;
}
public T get(int index) {
if (index < 0 || index >= size) {
return null;
}
Node p = sentinel.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.item;
}
public T getRecursive(int index) {
if (index < 0 || index >= size) {
return null;
}
return getRecursiveHelper(sentinel.next, index);
}
private T getRecursiveHelper(Node p, int index) {
if (index == 0) {
return p.item;
}
return getRecursiveHelper(p.next, index - 1);
}
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_44" data-title="C++"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="#include <vector>">
#include <vector>
template <typename T>
class LinkedList {
private:
struct Node {
T item;
Node* prev;
Node* next;
Node(T i, Node* p, Node* n) : item(i), prev(p), next(n) {}
};
Node* sentinel;
int size;
public:
LinkedList() : size(0) {
sentinel = new Node(T(), nullptr, nullptr);
sentinel->prev = sentinel;
sentinel->next = sentinel;
}
~LinkedList() {
Node* current = sentinel->next;
while (current != sentinel) {
Node* next = current->next;
delete current;
current = next;
}
delete sentinel;
}
void addFirst(T x) {
Node* newNode = new Node(x, sentinel, sentinel->next);
sentinel->next->prev = newNode;
sentinel->next = newNode;
size++;
}
void addLast(T x) {
Node* newNode = new Node(x, sentinel->prev, sentinel);
sentinel->prev->next = newNode;
sentinel->prev = newNode;
size++;
}
std::vector<T> toList() {
std::vector<T> returnList;
Node* p = sentinel->next;
while (p != sentinel) {
returnList.push_back(p->item);
p = p->next;
}
return returnList;
}
[[nodiscard]] bool isEmpty() const {
return size == 0;
}
[[nodiscard]] int size_() const {
return size;
}
T removeFirst() {
if (isEmpty()) {
return T();
}
Node* first = sentinel->next;
sentinel->next = first->next;
first->next->prev = sentinel;
size--;
T item = first->item;
delete first;
return item;
}
T removeLast() {
if (isEmpty()) {
return T();
}
Node* last = sentinel->prev;
sentinel->prev = last->prev;
last->prev->next = sentinel;
size--;
T item = last->item;
delete last;
return item;
}
T get(const int index) {
if (index < 0 || index >= size) {
return T();
}
Node* p = sentinel->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->item;
}
T getRecursive(const int index) {
if (index < 0 || index >= size) {
return T();
}
return getRecursiveHelper(sentinel->next, index);
}
private:
T getRecursiveHelper(Node* p, const int index) {
if (index == 0) {
return p->item;
}
return getRecursiveHelper(p->next, index - 1);
}
};
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_45" data-title="Python"><div class="code-collapse" data-lang="python" data-title="Python" data-is-expanded="false" data-synopsis="class Node:">
class Node:
def __init__(self, item, prev, next):
self.item = item
self.prev = prev
self.next = next
class LinkedList:
def __init__(self):
self.sentinel = Node(None, None, None)
self.sentinel.prev = self.sentinel
self.sentinel.next = self.sentinel
self.size = 0
def addFirst(self, x):
newNode = Node(x, self.sentinel, self.sentinel.next)
self.sentinel.next.prev = newNode
self.sentinel.next = newNode
self.size += 1
def addLast(self, x):
newNode = Node(x, self.sentinel.prev, self.sentinel)
self.sentinel.prev.next = newNode
self.sentinel.prev = newNode
self.size += 1
def toList(self):
returnList = []
p = self.sentinel.next
while p != self.sentinel:
returnList.append(p.item)
p = p.next
return returnList
def isEmpty(self):
return self.size == 0
def size_(self):
return self.size
def removeFirst(self):
if self.isEmpty():
return None
first = self.sentinel.next
self.sentinel.next = first.next
first.next.prev = self.sentinel
self.size -= 1
return first.item
def removeLast(self):
if self.isEmpty():
return None
last = self.sentinel.prev
self.sentinel.prev = last.prev
last.prev.next = self.sentinel
self.size -= 1
return last.item
def get(self, index):
if index < 0 or index >= self.size:
return None
p = self.sentinel.next
for i in range(index):
p = p.next
return p.item
def getRecursive(self, index):
if index < 0 or index >= self.size:
return None
return self._getRecursiveHelper(self.sentinel.next, index)
def _getRecursiveHelper(self, p, index):
if index == 0:
return p.item
return self._getRecursiveHelper(p.next, index - 1)
</div></div></div><aside class="prompt" data-type="note" data-title="" id="-9quly7_32"><p id="-9quly7_49">This is the resizing array implementation of deque.</p></aside><div class="tabs" id="-9quly7_33" data-anchors="[-9quly7_50,-9quly7_51,-9quly7_52]"><div class="tabs__content" data-gtm="tab" id="-9quly7_50" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="import java.util.List;">
import java.util.List;
import java.util.ArrayList;
import java.lang.Math;
public class ArrayDeque<T> {
private T[] items;
private int size;
private int nextFirst;
private int nextLast;
public ArrayDeque() {
items = (T[]) new Object[8];
size = 0;
nextFirst = 0;
nextLast = 1;
}
public void addFirst(T x) {
checkAndResize();
items[nextFirst] = x;
nextFirst = Math.floorMod(nextFirst - 1, items.length);
size += 1;
}
public void addLast(T x) {
checkAndResize();
items[nextLast] = x;
nextLast = Math.floorMod(nextLast + 1, items.length);
size += 1;
}
public List<T> toList() {
List<T> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
list.add(get(i));
}
return list;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public T removeFirst() {
if (isEmpty()) {
return null;
}
nextFirst = Math.floorMod(nextFirst + 1, items.length);
T item = items[nextFirst];
items[nextFirst] = null;
size -= 1;
checkAndResize();
return item;
}
public T removeLast() {
if (isEmpty()) {
return null;
}
nextLast = Math.floorMod(nextLast - 1, items.length);
T item = items[nextLast];
items[nextLast] = null;
size -= 1;
checkAndResize();
return item;
}
private void resize(int capacity) {
T[] a = (T[]) new Object[capacity];
for (int i = 0; i < size; i++) {
a[i] = get(i);
}
items = a;
nextFirst = capacity - 1;
nextLast = size;
}
private void checkAndResize() {
if (size == items.length) {
resize(size * 2);
} else if (items.length >= 16 && size < items.length / 4) {
resize(items.length / 2);
}
}
public T get(int index) {
if (index >= size || index < 0) {
return null;
}
return items[Math.floorMod(nextFirst + 1 + index, items.length)];
}
public T getRecursive(int index) {
throw new UnsupportedOperationException("No need to implement getRecursive for proj 1b");
}
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_51" data-title="C++"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="#include <vector>">
#include <vector>
template <typename T>
class ArrayDeque {
private:
T* items;
int size;
int nextFirst;
int nextLast;
int capacity;
void resize(const int newCapacity) {
T* a = new T[newCapacity];
for (int i = 0; i < size; i++) {
a[i] = get(i);
}
delete[] items;
items = a;
capacity = newCapacity;
nextFirst = capacity - 1;
nextLast = size;
}
void checkAndResize() {
if (size == capacity) {
resize(capacity * 2);
} else if (capacity >= 16 && size < capacity / 4) {
resize(capacity / 2);
}
}
public:
ArrayDeque(): size(0), nextFirst(0), nextLast(1), capacity(8) {
items = new T[capacity];
}
~ArrayDeque() {
delete[] items;
}
void addFirst(T x) {
checkAndResize();
items[nextFirst] = x;
nextFirst = (nextFirst - 1 + capacity) % capacity;
size += 1;
}
void addLast(T x) {
checkAndResize();
items[nextLast] = x;
nextLast = (nextLast + 1) % capacity;
size += 1;
}
std::vector<T> toList() {
std::vector<T> list;
for (int i = 0; i < size; i++) {
list.push_back(get(i));
}
return list;
}
[[nodiscard]] bool isEmpty() const {
return size == 0;
}
[[nodiscard]] int size_() const {
return size;
}
T removeFirst() {
if (isEmpty()) {
return T();
}
nextFirst = (nextFirst + 1) % capacity;
T item = items[nextFirst];
size -= 1;
checkAndResize();
return item;
}
T removeLast() {
if (isEmpty()) {
return T();
}
nextLast = (nextLast - 1 + capacity) % capacity;
T item = items[nextLast];
size -= 1;
checkAndResize();
return item;
}
T get(const int index) {
if (index >= size || index < 0) {
return T();
}
return items[(nextFirst + 1 + index) % capacity];
}
};
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_52" data-title="Python"><div class="code-collapse" data-lang="python" data-title="Python" data-is-expanded="false" data-synopsis="class ArrayDeque:">
class ArrayDeque:
def __init__(self):
self.capacity = 8
self.items = [None] * self.capacity
self.size = 0
self.nextFirst = 0
self.nextLast = 1
def addFirst(self, x):
self.checkAndResize()
self.items[self.nextFirst] = x
self.nextFirst = (self.nextFirst - 1 + self.capacity) % self.capacity
self.size += 1
def addLast(self, x):
self.checkAndResize()
self.items[self.nextLast] = x
self.nextLast = (self.nextLast + 1) % self.capacity
self.size += 1
def toList(self):
return [self.get(i) for i in range(self.size)]
def isEmpty(self):
return self.size == 0
def size_(self):
return self.size
def removeFirst(self):
if self.isEmpty():
return None
self.nextFirst = (self.nextFirst + 1) % self.capacity
item = self.items[self.nextFirst]
self.items[self.nextFirst] = None
self.size -= 1
self.checkAndResize()
return item
def removeLast(self):
if self.isEmpty():
return None
self.nextLast = (self.nextLast - 1 + self.capacity) % self.capacity
item = self.items[self.nextLast]
self.items[self.nextLast] = None
self.size -= 1
self.checkAndResize()
return item
def resize(self, newCapacity):
a = [None] * newCapacity
for i in range(self.size):
self.get(i)
self.items = a
self.capacity = newCapacity
self.nextFirst = newCapacity - 1
self.nextLast = self.size
def checkAndResize(self):
if self.size == self.capacity:
self.resize(self.capacity * 2)
elif self.capacity >= 16 and self.size < self.capacity // 4:
self.resize(self.capacity // 2)
def get(self, index):
if index >= self.size or index < 0:
return None
return self.items[(self.nextFirst + 1 + index) % self.capacity]
</div></div></div></section></section><section class="chapter"><h2 id="3-union-find" data-toc="3-union-find">3 Union-Find</h2><section class="chapter"><h3 id="3-1-quick-find-eager-approach" data-toc="3-1-quick-find-eager-approach">3.1 Quick Find (Eager Approach)</h3><ul class="list _bullet" id="-9quly7_59"><li class="list__item" id="-9quly7_61"><p id="-9quly7_64"><code class="code" id="-9quly7_65">parent[i]</code> is the root of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.025ex;" xmlns="http://www.w3.org/2000/svg" width="0.781ex" height="1.52ex" role="img" focusable="false" viewBox="0 -661 345 672"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D456" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path></g></g></g></svg></mjx-container>, <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container> and <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.041ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 460 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45E" d="M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z"></path></g></g></g></svg></mjx-container> are connected if and only if they have the same <code class="code" id="-9quly7_69">parent[i]</code>.</p></li><li class="list__item" id="-9quly7_62"><p id="-9quly7_70"><span id="-9quly7_71"><font style="color:#ff00ff">Find:</font></span> Check if <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container> and <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.041ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 460 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45E" d="M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z"></path></g></g></g></svg></mjx-container> have the same <code class="code" id="-9quly7_74">parent[i]</code>.</p></li><li class="list__item" id="-9quly7_63"><p id="-9quly7_75"><span id="-9quly7_76"><font style="color:#ff00ff">Union:</font></span> To merge components containing <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container> and <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.041ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 460 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45E" d="M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z"></path></g></g></g></svg></mjx-container>, change all entries whose id equals <code class="code" id="-9quly7_79">parent[p]</code> to <code class="code" id="-9quly7_80">parent[q]</code>.</p></li></ul><aside class="prompt" data-type="tip" data-title="" id="-9quly7_60"><p id="-9quly7_81"><span id="-9quly7_83"><font style="color:#8a2be2">Defect</font></span></p><ul class="list _bullet" id="-9quly7_82"><li class="list__item" id="-9quly7_84"><p id="-9quly7_86">Union too expensive (<mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: 0;" xmlns="http://www.w3.org/2000/svg" width="2.009ex" height="1.545ex" role="img" focusable="false" viewBox="0 -683 888 683"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D441" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></g></g></g></svg></mjx-container> array accesses).</p></li><li class="list__item" id="-9quly7_85"><p id="-9quly7_88">Trees are flat, but too expensive to keep them flat.</p></li></ul></aside></section><section class="chapter"><h3 id="3-2-quick-union-lazy-approach" data-toc="3-2-quick-union-lazy-approach">3.2 Quick Union (Lazy Approach)</h3><ul class="list _bullet" id="-9quly7_89"><li class="list__item" id="-9quly7_91"><p id="-9quly7_94">parent[i] is the parent of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.025ex;" xmlns="http://www.w3.org/2000/svg" width="0.781ex" height="1.52ex" role="img" focusable="false" viewBox="0 -661 345 672"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D456" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path></g></g></g></svg></mjx-container>, root of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.025ex;" xmlns="http://www.w3.org/2000/svg" width="0.781ex" height="1.52ex" role="img" focusable="false" viewBox="0 -661 345 672"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D456" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path></g></g></g></svg></mjx-container> is parent[parent[...[i]]] (keep going until it doesn't change).</p></li><li class="list__item" id="-9quly7_92"><p id="-9quly7_97"><span id="-9quly7_98"><font style="color:#ff00ff">Find:</font></span> Check if <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container> and <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.041ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 460 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45E" d="M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z"></path></g></g></g></svg></mjx-container> have the same root.</p></li><li class="list__item" id="-9quly7_93"><p id="-9quly7_101"><span id="-9quly7_102"><font style="color:#ff00ff">Union:</font></span> To merge components containing <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container> and <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.041ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 460 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45E" d="M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z"></path></g></g></g></svg></mjx-container>, set the parent of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container> 's root to the parent of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.041ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 460 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45E" d="M33 157Q33 258 109 349T280 441Q340 441 372 389Q373 390 377 395T388 406T404 418Q438 442 450 442Q454 442 457 439T460 434Q460 425 391 149Q320 -135 320 -139Q320 -147 365 -148H390Q396 -156 396 -157T393 -175Q389 -188 383 -194H370Q339 -192 262 -192Q234 -192 211 -192T174 -192T157 -193Q143 -193 143 -185Q143 -182 145 -170Q149 -154 152 -151T172 -148Q220 -148 230 -141Q238 -136 258 -53T279 32Q279 33 272 29Q224 -10 172 -10Q117 -10 75 30T33 157ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z"></path></g></g></g></svg></mjx-container> 's root.</p></li></ul><aside class="prompt" data-type="note" data-title="" id="-9quly7_90"><p id="-9quly7_107"><span id="-9quly7_109"><font style="color:#8a2be2">Defect</font></span></p><ul class="list _bullet" id="-9quly7_108"><li class="list__item" id="-9quly7_110"><p id="-9quly7_112">Trees can get tall.</p></li><li class="list__item" id="-9quly7_111"><p id="-9quly7_113">Find too expensive (could be <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: 0;" xmlns="http://www.w3.org/2000/svg" width="2.009ex" height="1.545ex" role="img" focusable="false" viewBox="0 -683 888 683"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D441" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></g></g></g></svg></mjx-container> array accesses).</p></li></ul></aside></section><section class="chapter"><h3 id="3-3-quick-union-improvements" data-toc="3-3-quick-union-improvements">3.3 Quick Union Improvements</h3><p id="-9quly7_115">Two Improvements: Weighting and Path Compression (WQUPC).</p><section class="procedure-steps"><h3 id="-9quly7_116" data-toc="-9quly7_116">Weighted quick-union</h3><ul class="list _bullet"><li class="list__item" id="-9quly7_120"><p id="-9quly7_123">Modify quick-union to avoid tall trees.</p></li><li class="list__item" id="-9quly7_121"><p id="-9quly7_124">Keep track of size of each tree (number of objects).</p></li><li class="list__item" id="-9quly7_122"><p id="-9quly7_125">Balance by linking root of smaller tree to root of larger tree.</p></li></ul></section><section class="procedure-steps"><h3 id="-9quly7_117" data-toc="-9quly7_117">Path compression</h3><ul class="list _bullet"><li class="list__item" id="-9quly7_126"><p id="-9quly7_127">Just after computing the root of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.439ex;" xmlns="http://www.w3.org/2000/svg" width="1.138ex" height="1.439ex" role="img" focusable="false" viewBox="0 -442 503 636"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D45D" d="M23 287Q24 290 25 295T30 317T40 348T55 381T75 411T101 433T134 442Q209 442 230 378L240 387Q302 442 358 442Q423 442 460 395T497 281Q497 173 421 82T249 -10Q227 -10 210 -4Q199 1 187 11T168 28L161 36Q160 35 139 -51T118 -138Q118 -144 126 -145T163 -148H188Q194 -155 194 -157T191 -175Q188 -187 185 -190T172 -194Q170 -194 161 -194T127 -193T65 -192Q-5 -192 -24 -194H-32Q-39 -187 -39 -183Q-37 -156 -26 -148H-6Q28 -147 33 -136Q36 -130 94 103T155 350Q156 355 156 364Q156 405 131 405Q109 405 94 377T71 316T59 280Q57 278 43 278H29Q23 284 23 287ZM178 102Q200 26 252 26Q282 26 310 49T356 107Q374 141 392 215T411 325V331Q411 405 350 405Q339 405 328 402T306 393T286 380T269 365T254 350T243 336T235 326L232 322Q232 321 229 308T218 264T204 212Q178 106 178 102Z"></path></g></g></g></svg></mjx-container>, set the parent of each examined node to point to that root.</p></li></ul></section><ul class="list _bullet" id="-9quly7_118"><li class="list__item" id="-9quly7_129"><p id="-9quly7_133"><code class="code" id="-9quly7_134">rank[i]</code> is the size of the tree rooted at <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.025ex;" xmlns="http://www.w3.org/2000/svg" width="0.781ex" height="1.52ex" role="img" focusable="false" viewBox="0 -661 345 672"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D456" d="M184 600Q184 624 203 642T247 661Q265 661 277 649T290 619Q290 596 270 577T226 557Q211 557 198 567T184 600ZM21 287Q21 295 30 318T54 369T98 420T158 442Q197 442 223 419T250 357Q250 340 236 301T196 196T154 83Q149 61 149 51Q149 26 166 26Q175 26 185 29T208 43T235 78T260 137Q263 149 265 151T282 153Q302 153 302 143Q302 135 293 112T268 61T223 11T161 -11Q129 -11 102 10T74 74Q74 91 79 106T122 220Q160 321 166 341T173 380Q173 404 156 404H154Q124 404 99 371T61 287Q60 286 59 284T58 281T56 279T53 278T49 278T41 278H27Q21 284 21 287Z"></path></g></g></g></svg></mjx-container>.</p></li><li class="list__item" id="-9quly7_130"><p id="-9quly7_136">Property: Starting from an empty data structure, any sequence of <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: 0;" xmlns="http://www.w3.org/2000/svg" width="2.378ex" height="1.545ex" role="img" focusable="false" viewBox="0 -683 1051 683"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D440" d="M289 629Q289 635 232 637Q208 637 201 638T194 648Q194 649 196 659Q197 662 198 666T199 671T201 676T203 679T207 681T212 683T220 683T232 684Q238 684 262 684T307 683Q386 683 398 683T414 678Q415 674 451 396L487 117L510 154Q534 190 574 254T662 394Q837 673 839 675Q840 676 842 678T846 681L852 683H948Q965 683 988 683T1017 684Q1051 684 1051 673Q1051 668 1048 656T1045 643Q1041 637 1008 637Q968 636 957 634T939 623Q936 618 867 340T797 59Q797 55 798 54T805 50T822 48T855 46H886Q892 37 892 35Q892 19 885 5Q880 0 869 0Q864 0 828 1T736 2Q675 2 644 2T609 1Q592 1 592 11Q592 13 594 25Q598 41 602 43T625 46Q652 46 685 49Q699 52 704 61Q706 65 742 207T813 490T848 631L654 322Q458 10 453 5Q451 4 449 3Q444 0 433 0Q418 0 415 7Q413 11 374 317L335 624L267 354Q200 88 200 79Q206 46 272 46H282Q288 41 289 37T286 19Q282 3 278 1Q274 0 267 0Q265 0 255 0T221 1T157 2Q127 2 95 1T58 0Q43 0 39 2T35 11Q35 13 38 25T43 40Q45 46 65 46Q135 46 154 86Q158 92 223 354T289 629Z"></path></g></g></g></svg></mjx-container> union-find operations on <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: 0;" xmlns="http://www.w3.org/2000/svg" width="2.009ex" height="1.545ex" role="img" focusable="false" viewBox="0 -683 888 683"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mi"><path data-c="1D441" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></g></g></g></svg></mjx-container> objects makes <mjx-container class="MathJax" jax="SVG"><svg style="vertical-align: -0.566ex;" xmlns="http://www.w3.org/2000/svg" width="18.18ex" height="2.262ex" role="img" focusable="false" viewBox="0 -750 8035.7 1000"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mo"><path data-c="2264" d="M674 636Q682 636 688 630T694 615T687 601Q686 600 417 472L151 346L399 228Q687 92 691 87Q694 81 694 76Q694 58 676 56H670L382 192Q92 329 90 331Q83 336 83 348Q84 359 96 365Q104 369 382 500T665 634Q669 636 674 636ZM84 -118Q84 -108 99 -98H678Q694 -104 694 -118Q694 -130 679 -138H98Q84 -131 84 -118Z"></path></g><g data-mml-node="mi" transform="translate(1055.8,0)"><path data-c="1D450" d="M34 159Q34 268 120 355T306 442Q362 442 394 418T427 355Q427 326 408 306T360 285Q341 285 330 295T319 325T330 359T352 380T366 386H367Q367 388 361 392T340 400T306 404Q276 404 249 390Q228 381 206 359Q162 315 142 235T121 119Q121 73 147 50Q169 26 205 26H209Q321 26 394 111Q403 121 406 121Q410 121 419 112T429 98T420 83T391 55T346 25T282 0T202 -11Q127 -11 81 37T34 159Z"></path></g><g data-mml-node="mo" transform="translate(1488.8,0)"><path data-c="28" d="M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z"></path></g><g data-mml-node="mi" transform="translate(1877.8,0)"><path data-c="1D441" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></g><g data-mml-node="mo" transform="translate(2988,0)"><path data-c="2B" d="M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z"></path></g><g data-mml-node="mi" transform="translate(3988.2,0)"><path data-c="1D440" d="M289 629Q289 635 232 637Q208 637 201 638T194 648Q194 649 196 659Q197 662 198 666T199 671T201 676T203 679T207 681T212 683T220 683T232 684Q238 684 262 684T307 683Q386 683 398 683T414 678Q415 674 451 396L487 117L510 154Q534 190 574 254T662 394Q837 673 839 675Q840 676 842 678T846 681L852 683H948Q965 683 988 683T1017 684Q1051 684 1051 673Q1051 668 1048 656T1045 643Q1041 637 1008 637Q968 636 957 634T939 623Q936 618 867 340T797 59Q797 55 798 54T805 50T822 48T855 46H886Q892 37 892 35Q892 19 885 5Q880 0 869 0Q864 0 828 1T736 2Q675 2 644 2T609 1Q592 1 592 11Q592 13 594 25Q598 41 602 43T625 46Q652 46 685 49Q699 52 704 61Q706 65 742 207T813 490T848 631L654 322Q458 10 453 5Q451 4 449 3Q444 0 433 0Q418 0 415 7Q413 11 374 317L335 624L267 354Q200 88 200 79Q206 46 272 46H282Q288 41 289 37T286 19Q282 3 278 1Q274 0 267 0Q265 0 255 0T221 1T157 2Q127 2 95 1T58 0Q43 0 39 2T35 11Q35 13 38 25T43 40Q45 46 65 46Q135 46 154 86Q158 92 223 354T289 629Z"></path></g><g data-mml-node="mi" transform="translate(5039.2,0)"><path data-c="1D459" d="M117 59Q117 26 142 26Q179 26 205 131Q211 151 215 152Q217 153 225 153H229Q238 153 241 153T246 151T248 144Q247 138 245 128T234 90T214 43T183 6T137 -11Q101 -11 70 11T38 85Q38 97 39 102L104 360Q167 615 167 623Q167 626 166 628T162 632T157 634T149 635T141 636T132 637T122 637Q112 637 109 637T101 638T95 641T94 647Q94 649 96 661Q101 680 107 682T179 688Q194 689 213 690T243 693T254 694Q266 694 266 686Q266 675 193 386T118 83Q118 81 118 75T117 65V59Z"></path></g><g data-mml-node="mi" transform="translate(5337.2,0)"><path data-c="1D454" d="M311 43Q296 30 267 15T206 0Q143 0 105 45T66 160Q66 265 143 353T314 442Q361 442 401 394L404 398Q406 401 409 404T418 412T431 419T447 422Q461 422 470 413T480 394Q480 379 423 152T363 -80Q345 -134 286 -169T151 -205Q10 -205 10 -137Q10 -111 28 -91T74 -71Q89 -71 102 -80T116 -111Q116 -121 114 -130T107 -144T99 -154T92 -162L90 -164H91Q101 -167 151 -167Q189 -167 211 -155Q234 -144 254 -122T282 -75Q288 -56 298 -13Q311 35 311 43ZM384 328L380 339Q377 350 375 354T369 368T359 382T346 393T328 402T306 405Q262 405 221 352Q191 313 171 233T151 117Q151 38 213 38Q269 38 323 108L331 118L384 328Z"></path></g><g data-mml-node="mo" transform="translate(6036.4,0)"><path data-c="2217" d="M229 286Q216 420 216 436Q216 454 240 464Q241 464 245 464T251 465Q263 464 273 456T283 436Q283 419 277 356T270 286L328 328Q384 369 389 372T399 375Q412 375 423 365T435 338Q435 325 425 315Q420 312 357 282T289 250L355 219L425 184Q434 175 434 161Q434 146 425 136T401 125Q393 125 383 131T328 171L270 213Q283 79 283 63Q283 53 276 44T250 35Q231 35 224 44T216 63Q216 80 222 143T229 213L171 171Q115 130 110 127Q106 124 100 124Q87 124 76 134T64 161Q64 166 64 169T67 175T72 181T81 188T94 195T113 204T138 215T170 230T210 250L74 315Q65 324 65 338Q65 353 74 363T98 374Q106 374 116 368T171 328L229 286Z"></path></g><g data-mml-node="mi" transform="translate(6758.7,0)"><path data-c="1D441" d="M234 637Q231 637 226 637Q201 637 196 638T191 649Q191 676 202 682Q204 683 299 683Q376 683 387 683T401 677Q612 181 616 168L670 381Q723 592 723 606Q723 633 659 637Q635 637 635 648Q635 650 637 660Q641 676 643 679T653 683Q656 683 684 682T767 680Q817 680 843 681T873 682Q888 682 888 672Q888 650 880 642Q878 637 858 637Q787 633 769 597L620 7Q618 0 599 0Q585 0 582 2Q579 5 453 305L326 604L261 344Q196 88 196 79Q201 46 268 46H278Q284 41 284 38T282 19Q278 6 272 0H259Q228 2 151 2Q123 2 100 2T63 2T46 1Q31 1 31 10Q31 14 34 26T39 40Q41 46 62 46Q130 49 150 85Q154 91 221 362L289 634Q287 635 234 637Z"></path></g><g data-mml-node="mo" transform="translate(7646.7,0)"><path data-c="29" d="M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z"></path></g></g></g></svg></mjx-container> array accesses.</p></li><li class="list__item" id="-9quly7_131"><p id="-9quly7_140">In theory, WQUPC is not linear; in practice, it is.</p></li><li class="list__item" id="-9quly7_132"><p id="-9quly7_141">Application: Percoloation, games, dynamic connectivity, least common ancestor, Kruskal's minimum spanning tree algorithm, etc.</p></li></ul><div class="tabs" id="-9quly7_119" data-anchors="[-9quly7_142,-9quly7_143,-9quly7_144,-9quly7_145]"><div class="tabs__content" data-gtm="tab" id="-9quly7_142" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="public class UnionFind {">
public class UnionFind {
private final int[] parent;
private final byte[] rank;
private int count;
public UnionFind(int n) {
if (n < 0) throw new IllegalArgumentException();
count = n;
parent = new int[n];
rank = new byte[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
}
}
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_143" data-title="C++ (UnionFind.h)"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="#ifndef UNIONFIND_H">
#ifndef UNIONFIND_H
#define UNIONFIND_H
#include <vector>
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> rank;
int count;
public:
explicit UnionFind(int n);
int find(int p);
[[nodiscard]] int countComponents() const;
bool connected(int p, int q);
void unionSets(int p, int q);
private:
void validate(int p) const;
};
#endif // UNIONFIND_H
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_144" data-title="C++ (UnionFind.cpp)"><div class="code-collapse" data-lang="cpp" data-title="C++" data-is-expanded="false" data-synopsis="#include <stdexcept>">
#include <stdexcept>
#include <string>
#include "UnionFind.h"
UnionFind::UnionFind(const int n) {
if (n < 0) throw std::invalid_argument("n must be non-negative");
count = n;
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int UnionFind::find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]]; // Path compression
p = parent[p];
}
return p;
}
int UnionFind::countComponents() const {
return count;
}
bool UnionFind::connected(int p, int q) {
return find(p) == find(q);
}
void UnionFind::unionSets(int p, int q) {
const int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else if (rank[rootP] > rank[rootQ]) {
parent[rootQ] = rootP;
} else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
void UnionFind::validate(const int p) const {
int n = static_cast<int>(parent.size());
if (p < 0 || p >= n) {
throw std::invalid_argument("index " + std::to_string(p) + " is not between 0 and " +
std::to_string(n - 1));
}
}
</div></div><div class="tabs__content" data-gtm="tab" id="-9quly7_145" data-title="Python"><div class="code-collapse" data-lang="python" data-title="Python" data-is-expanded="false" data-synopsis="class UnionFind:">
class UnionFind:
def __init__(self, n):
if n < 0:
raise ValueError("n must be non-negative")
self.count = n
self.parent = list(range(n))
self.rank = [0] * n
def find(self, p):
self.validate(p)
while p != self.parent[p]:
self.parent[p] = self.parent[self.parent[p]]
p = self.parent[p]
return p
def count_components(self):
return self.count
def connected(self, p, q):
return self.find(p) == self.find(q)
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
if self.rank[root_p] < self.rank[root_q]:
self.parent[root_p] = root_q
elif self.rank[root_p] > self.rank[root_q]:
self.parent[root_q] = root_p
else:
self.parent[root_q] = root_p
self.rank[root_p] += 1
self.count -= 1
def validate(self, p):
n = len(self.parent)
if p < 0 or p >= n:
raise ValueError(f"index {p} is not between 0 and {n - 1}")
</div></div></div></section></section><section class="chapter"><h2 id="4-bags-queues-and-stacks" data-toc="4-bags-queues-and-stacks">4 Bags, Queues and Stacks</h2><ul class="list _bullet" id="-9quly7_150"><li class="list__item" id="-9quly7_156"><p id="-9quly7_158"><span id="-9quly7_159"><font style="color:#ff00ff">Stack:</font></span> Examine the item most recently added (LIFO: last in first out).</p></li><li class="list__item" id="-9quly7_157"><p id="-9quly7_160"><span id="-9quly7_161"><font style="color:#ff00ff">Queue:</font></span> Examine the item least recently added (FIFO: first in first out).</p></li></ul><section class="chapter"><h3 id="4-1-stacks" data-toc="4-1-stacks">4.1 Stacks</h3><p id="-9quly7_162"><span id="-9quly7_170"><font style="color:#8a2be2">Defintions</font></span></p><ul class="list _bullet" id="-9quly7_163"><li class="list__item" id="-9quly7_171"><p id="-9quly7_174"><span id="-9quly7_175"><font style="color:#ff8c00">Client:</font></span> program using operations defined in interface.</p></li><li class="list__item" id="-9quly7_172"><p id="-9quly7_176"><span id="-9quly7_177"><font style="color:#ff8c00">Implementation:</font></span> actual code implementing operations.</p></li><li class="list__item" id="-9quly7_173"><p id="-9quly7_178"><span id="-9quly7_179"><font style="color:#ff8c00">Interface:</font></span> description of data types, basic operations.</p></li></ul><p id="-9quly7_164">Separate interface from implementation!</p><p id="-9quly7_165"><span id="-9quly7_180"><font style="color:#8a2be2">Benefits</font></span>:</p><ul class="list _bullet" id="-9quly7_166"><li class="list__item" id="-9quly7_181"><p id="-9quly7_185"><span id="-9quly7_186"><font style="color:#ff00ff">Clients can't know details of implementation</font></span> => client has many implementation from which to choose.</p></li><li class="list__item" id="-9quly7_182"><p id="-9quly7_187"><span id="-9quly7_188"><font style="color:#ff00ff">Implementation can't know details of client needs</font></span> => many clients can re-use the same implementation.</p></li><li class="list__item" id="-9quly7_183"><p id="-9quly7_189"><span id="-9quly7_190"><font style="color:#ff00ff">Design:</font></span> creates modular, reusable libraries.</p></li><li class="list__item" id="-9quly7_184"><p id="-9quly7_191"><span id="-9quly7_192"><font style="color:#ff00ff">Performance:</font></span> use optimized implementation where it matters.</p></li></ul><section class="chapter"><h4 id="4-1-1-built-in-stacks" data-toc="4-1-1-built-in-stacks">4.1.1 Built-In Stacks</h4><div class="tabs" id="-9quly7_193" data-anchors="[-9quly7_194,-9quly7_195,-9quly7_196]"><div class="tabs__content" data-gtm="tab" id="-9quly7_194" data-title="Java"><div class="code-collapse" data-lang="java" data-title="Java" data-is-expanded="false" data-synopsis="import java.util.Stack;">
import java.util.Stack;
public class StackExample {