-
Notifications
You must be signed in to change notification settings - Fork 4
/
index.html
1827 lines (1717 loc) · 68 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
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>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<!-- Bootstrap CSS -->
<link
href="https://cdn.jsdelivr.net/npm/[email protected]/dist/css/bootstrap.min.css"
rel="stylesheet"
integrity="sha384-1BmE4kWBq78iYhFldvKuhfTAU6auU8tT94WrHftjDbrCEXSU1oBoqyl2QvZ6jIW3"
crossorigin="anonymous"
/>
<link
rel="stylesheet"
href="https://cdn.jsdelivr.net/npm/[email protected]/font/bootstrap-icons.css"
/>
<!-- Dracula Theme for Highlight.js -->
<link rel="stylesheet" href="dracula.css" />
<!-- Custom Styles -->
<style>
#main-doc {
padding-left: 16px;
padding-right: 16px;
}
/* Bootstrap `lg` size = 992px */
@media (min-width: 992px) {
#main-doc {
padding-left: 450px;
padding-right: 50px;
}
}
</style>
<title>JavaScript Algorithms and Data Structures</title>
</head>
<body>
<button
type="button"
class="d-inline-block d-lg-none btn btn-secondary position-fixed mt-3 ms-3"
data-bs-toggle="offcanvas"
data-bs-target="#navbar"
aria-controls="navbar"
>
<i class="bi bi-list"></i>
</button>
<nav
id="navbar"
class="offcanvas offcanvas-start"
data-bs-scroll="true"
data-bs-backdrop="false"
tabindex="-1"
aria-labelledby="navbarLabel"
>
<button
type="button"
class="d-inline-block d-lg-none btn-close text-reset position-fixed mt-3 ms-3"
data-bs-dismiss="offcanvas"
aria-label="Close"
></button>
<header class="offcanvas-header mt-4 mt-lg-0">
<a href="#">
<h2 class="offcanvas-title" id="navbarLabel">
JavaScript Algorithms and Data Structures
</h2>
</a>
</header>
<hr />
<ol class="offcanvas-body list-group list-group-numbered">
<li class="list-group-item d-flex align-items-baseline">
<a href="#Problem_Solving_Patterns" class="nav-link">
Problem Solving Patterns
</a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Recursion" class="nav-link"> Recursion </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Searching_Algorithms" class="nav-link">
Searching Algorithms
</a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Sorting_Algorithms" class="nav-link">
Sorting Algorithms
</a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Linked_Lists" class="nav-link"> Linked Lists </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Stacks_and_Queues" class="nav-link"> Stacks and Queues </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Binary_Search_Trees" class="nav-link">
Binary Search Trees
</a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Binary_Heaps" class="nav-link"> Binary Heaps </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Hash_Tables" class="nav-link"> Hash Tables </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Graphs" class="nav-link"> Graphs </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Dynamic_Programming" class="nav-link">
Dynamic Programming
</a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Tries" class="nav-link"> Tries </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#2D_Arrays" class="nav-link"> 2D Arrays </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#Extras" class="nav-link"> Extras </a>
</li>
<li class="list-group-item d-flex align-items-baseline">
<a href="#References" class="nav-link"> References </a>
</li>
</ol>
</nav>
<main id="main-doc" class="container-fluid pt-5">
<section>
<header>
<h1>JavaScript Algorithms and Data Structures</h1>
</header>
<p class="mt-3">
These project is a collection of my notes while taking the
<a
href="https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/"
target="_blank"
rel="noopener noreferrer"
>
JavaScript Algorithms and Data Structures Masterclass
</a>
Udemy course.
</p>
</section>
<section id="Problem_Solving_Patterns" class="main-section">
<header>
<h2>Problem Solving Patterns</h2>
</header>
<em>
<ul>
<li>
<a href="Problem Solving Patterns/index.html">
Live Demo (WIP)
</a>
</li>
<li>
<a href="Problem Solving Patterns/Exercises/index.html">
More Challenge Exercises (WIP)
</a>
</li>
</ul>
</em>
<p class="mt-3">
Almost everything we do in programming requires some kind of
algorithm. Different problems, conditions, and/or requirements can
make some algorithms more effective than others. Having some
understanding of common problem solving patterns can help us see
opportunities for more effectively solving problems and knowing which
data structure and/or algorithm are best suited for the job.
</p>
<p>Here are some common problem solving patterns:</p>
<ol>
<li>
<strong>Frequency Counter</strong> - Some problems often require
keeping track of the frequency of values in some collection of data
(e.g. Arrays). Instead of using nested loops to count how many times
a specific value occurs, the Frequency Counter pattern makes use of
objects or sets to increment the frequency of specific values while
passing through the collection only once.
</li>
<li>
<strong>Multiple Pointers</strong> - This pattern is especially
useful when a collection of data is structured in predictable ways
(e.g. when an array of numbers is already sorted). The Multiple
Pointers pattern takes advantage of the predictable structure of the
collection to more effectively iterate through the items by (as the
name implies) creating multiple pointers at different positions,
then moving to different positions through the collection (i.e.
start/middle/end) until a certain condition is fulfilled or all
items in the collection are visited.
</li>
<li>
<strong>Sliding Window</strong> - Some types of problems may involve
keeping track of a subset of data in a collection of items. The
Sliding Window pattern is an effective way to keep track and/or
manipulate subsets of data in a collection, by creating a "window"
of a certain size (that may or may not get smaller or larger
depending on certain conditions) using multiple pointers, then
moving the "window" by moving the start and end pointers across the
collection.
</li>
<li>
<strong>Divide and Conquer</strong> - This is another pattern that
is especially useful for collections that have a predictable
structure. Depending on the required conditions, one can
tremendously reduce the time needed to iterate through the
collection if the predictable structure of the items allows you to
ignore unnecessary parts of the collection if they don't fulfill a
certain condition.
</li>
</ol>
</section>
<section id="Recursion" class="main-section">
<header>
<h2>Recursion</h2>
</header>
<em>
<ul>
<li>
<a href="Recursion/index.html"> Live Demo (WIP) </a>
</li>
<li>
<a href="Recursion/Recursion/index.html">
Recursion Challenge Exercises Demo (WIP)
</a>
</li>
</ul>
</em>
<p class="mt-3">
<strong>Recursion</strong> is a method of solving a computational
problem where the solution depends on solutions to smaller instances
of the same problem. In programming, this means using functions that
call themselves from within their own code. The approach can be
applied to many types of problems, and recursion is one of the central
ideas of computer science. Indeed, we're going to see recursion being
used in several of the data structures and algorithms we'll be
exploring later.
</p>
<h4>Example: Fibonacci</h4>
<p>
Write a recursive function called <code>fib</code> which accepts a
number and returns the nth number in the
<a
href="https://en.wikipedia.org/wiki/Fibonacci_number"
target="_blank"
rel="noopener noreferrer"
>
Fibonacci sequence</a
>. Recall that the Fibonacci sequence is the sequence of whole numbers
1, 1, 2, 3, 5, 8, ... which starts with 1 and 1, and where every
number thereafter is equal to the sum of the previous two numbers.
</p>
<pre>
<code class="language-js">function fib(num){
if(num <= 2) return 1;
return fib(num - 1) + fib(num - 2);
}</code>
</pre>
<h4>🔥 Hotshot One-liner</h4>
<p class="mt-3">
With a clever use of some modern ES6+ JavaScript syntax, we can
simplify the solution into just one line:
</p>
<pre>
<code class="language-js">const fib = num => num <= 2 ? 1 : fib(num - 1) + fib(num - 2);</code>
</pre>
<h4>🔥🔥🔥 wtf even is this 🔥🔥🔥</h4>
<pre>
<code class="language-js">const fib = num => num > 2 ? fib(--num) + fib(--num) : 1;</code>
</pre>
</section>
<section id="Searching_Algorithms" class="main-section">
<header>
<h2>Searching Algorithms</h2>
</header>
<em>
<a href="Searching Algorithms/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
Some problems may involve finding a specific value (or values) within
a given collection of data (e.g. Arrays, strings, etc.) The simplest
way to search for a specific value is to look at
<em>every single item in the collection</em> and check if it is the
item we want.
</p>
<p>
JavaScript has built-in methods for searching through such
collections. For example, here are some useful array search methods:
</p>
<ul>
<li>
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf"
target="_blank"
rel="noopener noreferrer"
>
<code>indexOf()</code>
</a>
</li>
<li>
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/includes"
target="_blank"
rel="noopener noreferrer"
>
<code>includes()</code>
</a>
</li>
<li>
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/find"
target="_blank"
rel="noopener noreferrer"
>
<code>find()</code>
</a>
</li>
<li>
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/findIndex"
target="_blank"
rel="noopener noreferrer"
>
<code>findIndex()</code>
</a>
</li>
</ul>
<p>
For many everyday use-cases, these built-in search methods can do
their job well enough. However, for more complex problems, we may need
to look at other, potentially more effective ways to search through a
given collection.
</p>
<p>
Let's look at some ways to search through a collection of elements:
</p>
<ol>
<li>
<strong>Linear Search</strong> - This is the simplest way to search
for an item. Linear Search iterates over the collection from start
to end, checking every single item to see if they are what we are
looking for.
</li>
<li>
<strong>Binary Search</strong> - Using the Divide and Conquer
pattern, Binary Search takes advantage of a predictably structured
collection. For example, when an array of integers is sorted in
ascending order, we can safely ignore previous items if the number
we're looking for is greater than the current item (or ignore all
next items if the current item is less than what we're looking for).
With Binary Search, we can start at the middle of the collection,
and safely ignore one half of the remaining items depending on the
condition, then repeat the same process for the remaining items
until we find the item or we run out of items to check.
</li>
</ol>
<p>There are also more clever ways to search through strings:</p>
<ol>
<li>
<strong>Naive String Search</strong> - Similar to Linear Search,
Naive String Search simply iterates from start to end of the string
to check if a given pattern is found.
</li>
<li>
<strong>Knuth-Morris-Pratt (KMP) String Search</strong> - searches
for occurrences of a "word" <code>W</code> within a main "text
string" <code>S</code> by employing the observation that when a
mismatch occurs, the word itself embodies sufficient information to
determine where the next match could begin, thus bypassing
re-examination of previously matched characters.
</li>
</ol>
</section>
<section id="Sorting_Algorithms" class="main-section">
<header>
<h2>Sorting Algorithms</h2>
</header>
<em>
<a href="Sorting Algorithms/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
Sorting is the process of rearranging iems in a collection such that
the items are in some predictable order. There are many ways to sort a
collection of items, for example:
</p>
<ul>
<li>Sorting numbers from smallest to largest (or vice versa)</li>
<li>Sorting strings in alphabetical order</li>
<li>Sorting dates in chronoligical order</li>
</ul>
<p>Here are some basic Sorting Algorithms:</p>
<ol>
<li>
<strong>Bubble Sort</strong> - Sometimes referred to as sinking
sort, Bubble Sort is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in wrong
order. It works by having the largest values "bubble" up to the top
(or smaller values to the bottom). This simple algorithm performs
poorly in real world use and is used primarily as an educational
tool to introduce the concept of a sorting algorithm.
</li>
<li>
<strong>Selection Sort</strong> - Sorts an array by repeatedly
finding the smallest element (considering ascending order) from the
unsorted part and putting it at the beginning. The algorithm divides
the input list into two parts: a sorted sublist of items which is
built up from left to right at the front (left) of the list and a
sublist of the remaining unsorted items that occupy the rest of the
list.
</li>
<li>
<strong>Insertion Sort</strong> - A simple sorting algorithm that
builds the final sorted array (or list) one item at a time. Much
like Selection Sort, Insertion Sort also divides the input list into
two parts (unsorted and sorted sublists). At each iteration,
insertion sort removes one element from the unsorted input data,
finds the location it belongs within the sorted list, and inserts it
there. It repeats until no unsorted input elements remain. Insertion
Sort also works similar to the way people sort playing cards in
their hands.
</li>
</ol>
<p>
With the power of recursion, one can also use clever tricks to more
efficiently sort a collection of items:
</p>
<ol>
<li>
<strong>Merge Sort</strong> - A divide and conquer algorithm that
was invented by John von Neumann in 1945. It takes advantage of the
fact that arrays of size 1 or 0 are always sorted. Merge Sort
divides the input array into two halves, calls itself for the two
halves until the array is divided into subarrays of size 1 or 0, and
then merges the two sorted halves until one full sorted array
remains. A <code>merge()</code> helper function is useful for
repeatedly merging the split subarrays.
</li>
<li>
<p>
<strong>Quicksort</strong> - A commonly used sorting algorithm
developed by British computer scientist Tony Hoare in 1959 and
published in 1961. It is a Divide and Conquer algorithm that picks
an element as pivot and partitions the given array around the
picked pivot.
</p>
<p>
There are many different versions of Quicksort that pick pivot in
different ways:
</p>
<ul>
<li>Always pick first element as pivot.</li>
<li>Pick median as pivot. (ideal)</li>
<li>Always pick last element as pivot.</li>
<li>Pick a random element as pivot.</li>
</ul>
<p>
Quicksort partitions the other elements into two sub-arrays,
according to whether they are less than or greater than the pivot.
For this reason, it is sometimes called
<em>partition-exchange sort</em>. The sub-arrays are then sorted
recursively. This can be done in-place, requiring small additional
amounts of memory to perform the sorting.
</p>
</li>
</ol>
<p>
There are also some niche sorting algorithms that may be more
efficient for dealing with specific types of items:
</p>
<ol>
<li>
<strong>Radix Sort</strong> - A non-comparative sorting algorithm.
Unlike the previous sorting algorithms, it avoids comparison by
creating and distributing elements into buckets according to their
radix. For elements with more than one significant digit, this
bucketing process is repeated for each digit, while preserving the
ordering of the prior step, until all digits have been considered.
For this reason, Radix Sort has also been called
<em>Bucket Sort</em> and <em>Digital Sort</em>. Radix Sort is
especially useful for sorting integers and short strings.
</li>
</ol>
<p>More Sorting Algorithms</p>
<ol>
<li>
<strong>Heapsort</strong> - To be discussed later in the
<a href="#Binary_Heaps">Binary Heaps</a> section
</li>
</ol>
</section>
<section id="Linked_Lists" class="main-section">
<header>
<h2>Linked Lists</h2>
</header>
<em>
<a href="Linked Lists/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
A <strong>linked list</strong> is a linear collection of data elements
whose order is not given by their physical placement in memory.
Instead, each element points to the next. It is a data structure
consisting of a collection of nodes which together represent a
sequence. In its most basic form, each node contains: data, and a
reference (in other words, a link) to the next node in the sequence.
This structure allows for efficient insertion or removal of elements
from any position in the sequence during iteration. More complex
variants add additional links, allowing more efficient insertion or
removal of nodes at arbitrary positions.
</p>
<h3>Types of Linked Lists</h3>
<ul>
<li>
<p>
<strong>Singly Linked List</strong> - In a Singly Linked List,
each node only contains a data field and a 'next' field, which
points to the next node in line of nodes.
<img
class="img-fluid"
src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/6d/Singly-linked-list.svg/1280px-Singly-linked-list.svg.png"
alt="A singly linked list whose nodes contain two fields: an integer value and a link to the next node"
/>
</p>
</li>
<li>
<p>
<strong>Doubly Linked List</strong> - In a Doubly Linked List,
each node contains a data field, a 'next' field, which points to
the next node in line of nodes, and a 'prev' field, which points
to the previous node in line of nodes.
</p>
<img
class="img-fluid"
src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/1280px-Doubly-linked-list.svg.png"
alt="A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node"
/>
</li>
</ul>
</section>
<section id="Stacks_and_Queues" class="main-section">
<header>
<h2>Stacks and Queues</h2>
</header>
<em>
<a href="Stacks and Queues/index.html"> Live Demo (WIP) </a>
</em>
<h3 class="mt-3">Stacks</h3>
<p>
A <strong>Stack</strong> is an abstract data type that serves as a
collection of elements, with two main principal operations:
</p>
<ul>
<li>
<code>push()</code>, which adds an element to the collection, and
</li>
<li>
<code>pop()</code>, which removes the most recently added element
that was not yet removed.
</li>
</ul>
<img
class="img-fluid"
src="https://upload.wikimedia.org/wikipedia/commons/b/b4/Lifo_stack.png"
alt="Simple representation of a stack runtime with push and pop operations."
/>
<p>
Considered as a linear data structure, or more abstractly a sequential
collection, the <code>push()</code> and <code>pop()</code> operations
occur only at one end of the structure, referred to as the top of the
stack. The order in which elements come off a stack gives rise to its
alternative name, <strong>LIFO (last in, first out)</strong>. The name
"stack" for this type of structure comes from the analogy to a set of
physical items stacked on top of each other.
</p>
<p>
In JavaScript,
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array"
target="_blank"
rel="noopener noreferrer"
>
Arrays</a
>
already have the <code>push()</code> and <code>pop()</code> methods
that are essential for implementing stacks, so you can just use those
methods as-is, and you can easily create a new stack by simply
creating a new Array and treating it as a Stack.
</p>
<h3>Queues</h3>
<p>
A <strong>Queue</strong> is a collection of entities that are
maintained in a sequence and can be modified by the addition of
entities at one end of the sequence and the removal of entities from
the other end of the sequence. By convention, the end of the sequence
at which elements are added is called the back, tail, or rear of the
queue, and the end at which elements are removed is called the head or
front of the queue.
</p>
<p>Similar to Stacks, Queues also have two main operations:</p>
<ul>
<li>
The operation of adding an element to the rear of the queue is known
as <code>enqueue()</code>, and
</li>
<li>
The operation of removing an element from the front is known as
<code>dequeue()</code>.
</li>
</ul>
<img
class="img-fluid"
src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/1280px-Data_Queue.svg.png"
alt="Representation of a FIFO (first in, first out) queue"
/>
<p>
A Queue is also called a
<strong>first-in-first-out (FIFO)</strong> data structure. In a FIFO
data structure, the first element added to the queue will be the first
one to be removed. This is equivalent to the requirement that once a
new element is added, all elements that were added before have to be
removed before the new element can be removed. This is analogous to
the words used when people line up to wait for goods or services.
</p>
<p>
In JavaScript, Arrays already have the <code>push()</code> and
<code>shift()</code> methods that are analogous to the
<code>enqueue()</code> and <code>dequeue()</code> methods essential
for implementing queues, so you can just use those methods as-is, and
you can easily create a new queue by simply creating a new Array and
treating it as a Queue.
</p>
</section>
<section id="Binary_Search_Trees" class="main-section">
<header>
<h2>Binary Search Trees</h2>
</header>
<em>
<a href="Binary Search Trees/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
A <strong>Binary Search Tree (BST)</strong> is a type of
<em>Binary Tree</em>, whose internal nodes each store a value, and
each has two distinguished sub-trees, commonly denoted left and right.
A BST additionally satisfies the binary search property: The value in
each node is greater than or equal to any value stored in the left
sub-tree, and less than or equal to any value stored in the right
sub-tree.
</p>
<h3>Example</h3>
<pre>
<code class="language-js">const bst = new BinarySearchTree();
bst
.insert(50)
.insert(30)
.insert(20)
.insert(40)
.insert(70)
.insert(60)
.insert(80);</code>
</pre>
<p>This represents the following Binary Search Tree:</p>
<pre class="mermaid">
graph TD
50 --> 30
50 --> 70
30 --> 20
30 --> 40
70 --> 60
70 --> 80
</pre>
<h3>Traversal/Searching Binary Search Trees</h3>
<p>
Binary Search Trees (and Binary Trees in general) can be traversed by
visiting each node. There are two common ways for traversal:
</p>
<ul>
<li>
<p class="my-0">
<strong>Breadth-First Search (BFS)</strong> - BFS starts at the
tree root and explores all nodes at the present depth prior to
moving on to the nodes at the next depth level. Extra memory,
usually a queue, is needed to keep track of the child nodes that
were encountered but not yet explored.
</p>
<pre class="my-0">
<code class="language-js">bst.breadthFirstSearch() // should return [50, 30, 70, 20, 40, 60, 80]</code>
</pre>
</li>
<li>
<p>
<strong>Depth First Search (DFS)</strong> - DFS starts at the root
node and explores as far as possible along each branch before
backtracking.
</p>
<p>
In the case of Binary Trees, DFS can be ordered in one of three
ways:
</p>
<ul>
<li>
<p class="my-0">
<strong>Pre-Order Traversal</strong> - Accesses/visits the
current node first, and then traversing the left and right
sub-trees respectively. Pre-Order Traversal is topologically
sorted, because a parent node is processed before any of its
child nodes is done.
</p>
<pre class="my-0">
<code class="language-js">bst.DFSPreOrder() // should return [50, 30, 20, 40, 70, 60, 80]</code>
</pre>
</li>
<li>
<p class="my-0">
<strong>In-Order Traversal </strong> - Traverses the left
sub-tree first, then accesses the current node before finally
traversing the right sub-tree. For Binary Search Trees,
In-Order Traversal retrieves the values in ascending sorted
order.
</p>
<pre class="my-0">
<code class="language-js">bst.DFSInOrder() // should return [20, 30, 40, 50, 60, 70, 80]</code>
</pre>
</li>
<li>
<p class="my-0">
<strong>Post-Order Traversal</strong> - Traverses the left and
right sub-trees first before finally accessing the current
node.
</p>
<pre class="my-0">
<code class="language-js">bst.DFSPostOrder() // should return [20, 40, 30, 60, 80, 70, 50]</code>
</pre>
</li>
</ul>
</li>
</ul>
</section>
<section id="Binary_Heaps" class="main-section">
<header>
<h2>Binary Heaps</h2>
</header>
<em>
<a href="Binary Heaps/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
A <strong>Binary Heap</strong> is a heap data structure that takes the
form of a binary tree. Binary heaps are a common way of implementing
priority queues. The Binary Heap was introduced by J. W. J. Williams
in 1964, as a data structure for Heapsort.
</p>
<p>
A Binary Heap is defined as a Binary Tree with two additional
constraints:
</p>
<ul>
<li>
<strong>Shape property</strong>: A Binary Heap is a complete Binary
Tree; that is, all levels of the tree, except possibly the last one
(deepest) are fully filled, and, if the last level of the tree is
not complete, the nodes of that level are filled from left to right.
</li>
<li>
<strong>Heap property</strong>: The value stored in each node is
either greater than or equal to (max-heap) or less than or equal to
(min-heap) the values in the node's children, according to some
total order.
</li>
</ul>
<h3>Example</h3>
<p>Imagine a Binary Heap with the ff. elements:</p>
<pre>
<code class="language-js">heap
.insert(41)
.insert(39)
.insert(33)
.insert(18)
.insert(27)
.insert(12)
.insert(55);</code>
</pre>
<p>As a Max Heap, the heap will be structured as follows:</p>
<pre class="mermaid">
graph TD
55 --> 39
55 --> 41
39 --> 18
39 --> 27
41 --> 12
41 --> 33
</pre>
<p>As a Min Heap, the heap will be structured as follows:</p>
<pre class="mermaid">
graph TD
12 --> 27
12 --> 18
27 --> 41
27 --> 33
18 --> 39
18 --> 55
</pre>
<h3>Heapsort</h3>
<p>
<em>Heapsort</em> is a comparison-based sorting algorithm. Heapsort
can be thought of as an improved selection sort: like selection sort,
heapsort divides its input into a sorted and an unsorted region, and
it iteratively shrinks the unsorted region by extracting the largest
element from it and inserting it into the sorted region. Unlike
selection sort, heapsort does not waste time with a linear-time scan
of the unsorted region; rather, heap sort maintains the unsorted
region in a heap data structure to more quickly find the largest
element in each step.
</p>
<img
src="https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif"
alt="An animation of Heapsort in action"
/>
<p>
The Heapsort algorithm involves preparing the list by first turning it
into a max heap. The algorithm then repeatedly swaps the first value
of the list with the last value, decreasing the range of values
considered in the heap operation by one, and sifting the new first
value into its position in the heap. This repeats until the range of
considered values is one value in length.
</p>
</section>
<section id="Hash_Tables" class="main-section">
<header>
<h2>Hash Tables</h2>
</header>
<em>
<a href="Hash Tables/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
A Hash Table is a data structure that implements an associative array
abstract data type, a structure that can map keys to values. A hash
table uses a hash function to compute an index, also called a hash
code, into an array of buckets or slots, from which the desired value
can be found. During lookup, the key is hashed and the resulting hash
indicates where the corresponding value is stored.
</p>
<p>
Ideally, the hash function will assign each key to a unique bucket,
but most hash table designs employ an imperfect hash function, which
might cause hash collisions where the hash function generates the same
index for more than one key. Such collisions are typically
accommodated in some way.
</p>
<p>
In a well-dimensioned hash table, the average cost (number of
instructions) for each lookup is independent of the number of elements
stored in the table. Many hash table designs also allow arbitrary
insertions and deletions of key–value pairs, at (amortized) constant
average cost per operation.
</p>
<img
class="img-fluid"
src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg/1280px-Hash_table_3_1_1_0_1_0_0_SP.svg.png"
alt="Example of a Hash Table: A small phone book represented as a hash table"
/>
<p>
Hash tables already exist by default in JavaScript in the form of
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object"
target="_blank"
rel="noopener noreferrer"
>
Objects
</a>
or
<a
href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map"
target="_blank"
rel="noopener noreferrer"
>
Maps </a
>. However, we can also try
<a href="Hash Tables/index.html">
implementing our own Hash Table from scratch </a
>!
</p>
</section>
<section id="Graphs" class="main-section">
<header>
<h2>Graphs</h2>
</header>
<em>
<a href="Graphs/index.html"> Live Demo (WIP) </a>
</em>
<p class="mt-3">
A <strong>Graph</strong> is an abstract data type that is meant to
implement the undirected graph and directed graph concepts from the
field of graph theory within mathematics.
</p>
<p>
A graph data structure consists of a finite (and possibly mutable) set
of <em>vertices</em> (also called nodes or points), together with a
set of pairs connecting these vertices called <em>edges</em> (also
called links or lines).
</p>
<p>
Graphs are used to solve many real-life problems. Graphs are used to
represent networks. The networks may include paths in a city or
telephone network or circuit network. Graphs are also used in social
networks where each person is represented with a vertex(or node). Each
node is a structure and contains information like person id, name,
gender, locale etc.
</p>
<h3>Representing a Graph</h3>
<p>A graph can be represented in three ways:</p>
<ul>
<li>
<strong>Adjacency List</strong> - Vertices are stored as records or
objects, and every vertex stores a list of adjacent vertices. This
data structure allows the storage of additional data on the
vertices. Additional data can be stored if edges are also stored as
objects, in which case each vertex stores its incident edges and
each edge stores its incident vertices.
</li>
<li>
<strong>Adjacency Matrix</strong> - A two-dimensional matrix, in
which the rows represent source vertices and columns represent
destination vertices. Data on edges and vertices must be stored
externally. Only the cost for one edge can be stored between each
pair of vertices.
</li>
<li>
<strong>Incidence Matrix</strong> - A two-dimensional matrix, in
which the rows represent the vertices and columns represent the
edges. The entries indicate the incidence relation between the
vertex at a row and edge at a column.
</li>
</ul>
<h3>Example</h3>
<pre>
<code class="language-js">const g = new Graph();
g.addVertex("A")