Comprehensive Guide to Core Data Structures and Algorithms

In these first few videos, I want to lay the foundation of some core concepts you will need throughout these video tutorials. Let's get started with the basics. So what is a data structure? one definition that I really like is a data structure is a way of organizing

data so that it can be used efficiently. And that's all data structure really is it is a way of organizing data in some fashion so that later on it can be accessed, queried, or perhaps even updated quickly and easily. So why data structures? Why are they important?

Well, they are essential ingredients in creating fast and powerful algorithms. Another good reason might be that they help us manage and organize our data in a very natural way. And this last point, is more of my own making. And it's that it makes code cleaner and easier

to understand. As a side note, one of the major distinctions that I have noticed from bad mediocre to excellent programmers is that the ones who really excel are the ones who fundamentally understand how and when to use the appropriate data structure for the task

they're trying to finish. data structures can make the difference between having an okay product and an outstanding one. It's no wonder that every computer science undergraduate student is required to take a course in data structures. It is strange that before we even

begin talking about data structures that we need to talk about the abstraction of data structures. What I'm talking about is the concept of an abstract data type. What is an abstracted type and how does it differ from a data structure? Well, the answer is

that an abstract data type is an abstraction of a data structure, which provides only the interface to which that data structure must adhere to. The interface does not give any specific details on how

a specific data structure should be implemented, or in what programming language. One particular example I like to give is to suppose that your abstract data type is for a mode of transportation to get from point A to point B. Well, as we both know, there are many modes of transportation

to get from one place to another. So which one do you choose? some specific modes of transportation might be walking or biking, perhaps even taking a train and so on, these specific modes of transportation would be analogous to the data structures themselves.

We want to get from one place to another through some mode of transportation, that was our abstract data type. How did we do that? Exactly? Well, that is the data structure. Here are some examples of abstract data types on the left, and some possible underlying implementation

on the right hand side. As you can see, a list can be implemented in two ways. You can have a dynamic array or a linked list. They both provide ways of adding, removing and indexing elements in the list. Next, we have a queue and the map abstract data types, which

themselves can be implemented in a variety of ways. Notice that under the implementation for a queue, I put a stack based queue because yes, you can have a queue, which is implemented using only stacks. This may not be the most efficient way of implementing a queue. But

it does work and it is possible. The point here is that the abstract data type only defines how a data structure should behave, and what methods it should have, but not the details surrounding how those methods are implemented. Alright, now that we were done with abstract

data types, we need to have a quick look at the wild world of computational complexity, to understand the performance that our data structures are providing. So as programmers, we often find ourselves asking the same two questions over and over and over again. That

is, how much time does this algorithm need to finish and also how much space Does this algorithm need for my computation. So, if your program takes a lifetime of the universe to finish, then it's no good. Similarly, if your program runs in constant time, but requires

a space equal to the sum of all the bytes of all the files on the internet, internet, your algorithm is also useless. So just standardize a way of talking about how much time and how much space is required for an algorithm to run. theoretical computer scientists have

invented big O notation, amongst other things like big theta, big omega, and so on. But we're interested in Big O because it tells us about the worst case. Big O notation only cares about the worst case. So if your algorithm sorts numbers, imagine the input is the worst

possible arrangement of numbers for your particular sorting algorithm. Or, as a concrete example, suppose you have an unordered list of unique numbers, and you're searching for the number seven, or the position where seven occurs in your list. And the worst case isn't one

seven, that is at the beginning. Or in the middle of the list, it's one seven is the very last element of the list. for that particular example, the time complexity would be linear with respect to the number of elements in the size view list. Because you have to traverse

every single element until you find seven. The same concept applies to space, you can just consider the worst possible amount of space your algorithm is going to need for that particular input. There's also the fact that big O really only cares about what happens

when your input becomes arbitrarily large. We're not interested in what happens when the input is small. For this reason, you'll see that we ignore things like constants and multiplicative factors. So in our big O notation, you'll often see these coming up. Again, again,

again. So to clarify one thing, when I say n, n is usually always want to be the input size coming into your algorithm, there's always going to be some limitation of size n. So constant time referred to as

a one wrapped around a big O. If your algorithm case in logarithmic amount of time to finish, we say that's big O of a log event. If it's linear, then we just say n, if it takes like quadratic time or cubic time, then we say that's n raised to that power, it's exponential.

Usually, this is going to be something like two to the n three, the N, N number be greater than one to the n. And then we also have n factorial. But we also have things in between these like square root of n log log of n, n to the fifth and so on. Actually, almost

any mathematical expression containing n can be wrapped around a big O. And is big O notation valid. Now, we want to talk about some properties of Big O. So to reiterate what we just saw in the last two slides, Big O only really cares about what happens when input becomes

really big. So we're not interested when n is small, only what happens when n goes to infinity. So this is how and why we get the first two properties. The first that we can simply remove constant values added to our big O notation. Because

if you're adding a constant to infinity, well, let's just infinity, or if you're multiplying a constant by infinity, yeah, that's still infinity. So we can ignore constants. But of course, this is all theoretical. In the real world. If your constant is of size, 2

billion, probably, that's going to have a substantial impact on the running time of your algorithm. However, let us look at a function f, which I've defined over some input size. And if

f of n is seven log of n cubed plus 15 n squared plus two n q plus eight. Well, big O of f of n is just n cubed, because n cubed is the biggest, most dominant term in This function. All right, now let's

look at some concrete examples of how big O is used. So both of the following run in constant time with respect to the input size, and because they don't depend on n at all.

So on the left, when we're just adding or doing some mathematical formula, yes, that's constant time. And on the right, okay, we're doing a loop, but the loop itself doesn't depend on n. So it runs also in a constant amount of time. So as our input size gets

arbitrarily large, well, that loop is still going to run in the same amount of time regardless. Now let's look at a linear example. So both the following actually run in linear time with respect to the input size, and because we do a constant amount of work,

and times. So on the left, we're incrementing, the counter AI by one each time. So f of n is and, and clearly, when we wrap this in a big go get a big O of n. On the right, a little bit more

complicated, we're not incrementing by one, we're incrementing by three, so we're going to finish that loop three times faster. So f of n is n over three. So our second example is two algorithms that run in quadratic time. So the first one seems obvious, we do n work

at times. So n times as big O of n squared. But observe the second one, I changed the zero with an eye. So pause the video and try to figure out maybe why that's big O of n squared. Okay, let's go over the solution. So first, just focus on the second loop. The

first loop isn't as important. So since I go from zero to n, the amount of looping done is going to be directly related to what AI is, and remember is changing from the outer loop. So if we fix AI to be zero, we do n work. We fix it one, we do n minus one work.

If we fix it, too, we do n minus two work and excetera. So the question then becomes what is n plus n minus one plus n minus two plus n minus three and so on? Well, this is a well known identity, and turns out to be n times n plus one divided by two. So if we

wrap this in a big O, we split our equation, we can see that this is big O of n squared. Now let's look at perhaps a more complicated example. Earlier, you may have wondering, how do we ever get these log Eurythmics or linear rhythmic time complexities? So here's

a classic algorithm of doing a binary search, which yields actually a logarithmic time complexity. So what this algorithm does is it starts by making two pointers, one at the very start in one at the very end of the array, then it selects a midpoint between two and checks

if the value we're looking for was found at the midpoint, and then has either found it or not, if it has found it, it stops. Otherwise, it discards one half of the array, and adjusts either the high or the low pointer. remark that even in the worst case, we're still discarding

half of the array, each iteration. So very, very quickly, we're going to run out of a range check. So if you do the math, the worst case is you will do exactly log base two of N iterations, meaning that the binary search will runs in logarithmic time. Very cool algorithm,

a very powerful algorithm. Here's a slightly different example worth going over. So first, notice that there is an outer loop with a counter I that does and work, then notice that there are two inner loops, one that does three n work another one that does, too, one

work. So the rule we use to determine the complexity of this algorithm is to multiply loops on different levels and add those that aren't the same, generally speaking. So, so using the rule above, we can see that it takes n work to do the outer loop, multiply by three

n plus two n for both inner loop Which gives us five n squared, which is big O of n squared. All right, so this next one looks very similar, but it's actually quite different. So on the outer loop with AI, we have AI going from zero to three n. So there's three n work done

on the outside. But we have to multiply that but what's going on on the inside, so the inside j goes from 10, to 50. So that does 40 loops exactly every loop. So that's a constant for

the amount of work. Plus however, the second loop, so j is less than and cubed, but j is J equals j plus two, so it's accelerated a little, so we're going to finish that loop a little faster. So we're gonna get on the inside 14, plus n cubed divided by two, but

we have to multiply that by three n. So we wrap that in a big O. So big O of f of n, is going to give us big of enter the force, because And the fourth is the dominant term in our function, f of n. For some other classic examples of Big O. So if we have to find all

the subsets of a set, that takes an exponential amount of time, because there are two the N subsets, finding all permutations of a string takes big O of n factorial. Another classic one is merge sort. So we have n times log in for your merge sort. And if we have to

iterate over all the cells of an array of size n by n, we have big O of n m. Time. All right, let's talk about arrays, probably the most used data structure. This is part one of two in the array videos. The reason the array is used so much is because it forms

a fundamental building block for all other data structures. So we end up seeing everywhere. with arrays and pointers alone, I'm pretty sure we can construct just about any data structure. So an outline for today's video. First, we're going to begin by having a discussion

about arrays and answer some fundamental questions such as what where and how are arrays used? Next, I will explain the basic structure of an array and the common operations we are able to perform on them. Lastly, we will go over some complexity complexity analysis and

look at some source code on how to construct a dynamic array using only static arrays, discussion and examples. So what is a static array? So static array is a fixed length container containing elements, which are indexable, usually on the range of zero, inclusive to

n minus one also inclusive. So a follow up question is what is meant by being indexable? So answer this is this means that each slot or index in the array can be referenced with a number. Furthermore, I would like to add that static arrays are given as contiguous

chunks of memory. Meaning that your chunk of memory doesn't look like a piece of Swiss cheese with a bunch of holes and gaps. It's continuous, all the addresses are adjacent in your static array. Okay, so when and where is a static array used? Well, they're used

everywhere, absolutely everywhere. It's hard to make a program that doesn't use them. In fact, here are a few places you may or may not know that do use arrays. So of course, the first simple example is to temporarily store objects most common use of arrays that

you're probably familiar with. Next is that we use arrays as buffers to store information from an input or an output stream. Suppose you have a really large file, for instance, that you need to process but that file is so big, it doesn't fit in all in memory. So

we use a buffer to read small chunks of the file into The buffer or the array, one at a time. And so eventually we're able to read the entire file. I also like to use arrays as lookup tables because of their indexing property. So this is a really easy way to

retrieve data from the lookup table if you know where everything is at supposed to be and at what offset. Next, we also use arrays as a workaround in a programming language that only allows one return value.

So the hack we use then is to return a pointer or a reference to an array, which then contains all the return values that we want. This last example is a bit more advanced, but arrays are heavily used the programming technique called dynamic programming, with tabulation

to cache already computed subproblems. So a classic example of this might be the knapsack problem, or the coin change problem. All right, I'm talking about some complexity. So the access time for static array and a dynamic array is constant because of a property that

arrays are indexable. Searching, however, it can take up to the linear time because we potentially have to traverse all the elements in the array in the worst case, such as if the element you're looking for does not exist. Inserting appending. And deletion from a static

array doesn't really make sense. The static array is a fixed size container, it cannot grow larger or smaller. When inserting with a dynamic array, this operation can cost up linear time, because you potentially have to shift all the elements to the right, and

recopy all the elements into the new static array. This is assuming we're implementing a dynamic array using static arrays. However, appending though, is constant, Doesn't that seem a little strange? Well, when we append elements to a dynamic array, we have to resize

the internal static array containing all those elements. But this happens so rarely, that appending becomes constant time. deletions are linear, for the same reasons that insertions are linear, you have to shift all of the elements over and re potentially recopy everything

into your static array. Okay, so we have a static array A I've defined at the top. So a contains the values 4412 minus 517 6039 100. Currently, all the elements are distinct, but this is not a requirement of an array. Also remark that the very first element 44

has index position zero in the array, not one. This confuses many, many intro computer science students, you have no idea. The confusing part is that most, if not all, mathematics is one base to work computer science is one. Now, if we look at a you can see that it contains

the values 4412 minus 517 6039, and 100. Currently, all the elements are distinct. However, this is not at all a requirement of the array. Also remark that the very first element 44 is indexed, or positioned at index of zero in the array, not one, zero. This confuses

a lot of intro computer science students. The confusing part is that most if not all, mathematics is one based while computer science is zero based. This is what causes the confusion. But Worst of all, is quantum computing. I did research one summer in quantum computing

during my undergrad, and the field is a mess. It tries to please mathematicians, computer scientists and physicists all at the same time. And indexing just doesn't work well. Anyways, back to arrays. I should also note that elements can be iterated over using a

for each loop something that's offered in some programming languages. It doesn't require you to explicitly reference the indices of your array. Although the indexing is done internally, behind the scenes, the notation of the square brackets denotes indexing. So

array A square bracket zero, close square bracket is equal to 44, meaning a at position zero is equal to the value 44. Similarly, a position one is 12, a, four, six and seven is nine.

But a index nine is out of bounds. And our program will throw an exception. Unless you're in C, it doesn't always throw an exception, unfortunately, okay. Now if we assign positions zero to B minus one that happens if we assign index five B to and if we assign index x to

be 25, let's look at operations on dynamic arrays. So dynamic arrays can grow and shrink in size as needed. So the dynamic array can do all similar get set operation static arrays can do but unlike the static array, it grows inside as dynamically as needed. So if we

have a containing 34, and four, there, if we add minus seven, it gets appended to the end. If we add 34, again, then it will add it to the end. And we can also remove elements. So you see here, our dynamic array shrink in size. Pretty cool, right? Okay, so we already

talked about this a little bit. But how do we formally implement a dynamic array? Well, the answer is typically this is done with a static array. But this is not the only way, of course. So first, we create a stack if you're a with some initial capacity, usually

nine zero. So as we add elements, we add elements to the underlying static array, keeping track of the number of elements added. Once, we have to add an element with exceeds the capacity of our internal static array, what we can do it again, double the size, copy all the

elements into this new static array, and add the new element we need to add, let's see an example. So suppose we create a dynamic array with an initial capacity of two, then we begin adding elements to it. So the little circle with the slash through it is a placeholder

for an empty position. Okay, so we add seven, everything's fine, we are nine, everything's fine. But once we add three, it doesn't fit in our internal static array. So we doubled the size of the array, copy all the elements in, and now we can add three. Now, if we add

12, everything's still okay, we're doing good. And if we add five, okay, we have to do a resize again. So double the size of the container, copy all the LLM elements into this new, larger array, and then finish off by adding five. And similarly, we can add six without any

issues. All right, time to look at the dynamic array source code. This is part two of two in the array series. So the source code for this video can be found at the following link github.com, slash my username slash data dash structures. Also make sure you saw the last

video so you know what's going on with this array implementation. Alright, here we are in the array class. So I've designed an array class to support generics of type T. So whatever type of data we want put in this array, that's fine. So here are three instance variables

that we care about our, which is our internal static array. Len, which is the length the user thinks the array is. And capacity is the length of the actual

array, because sometimes our array might have more free slots. And we don't want to tell the user that there's extra free slots that are available. That's just our internal knowledge. So there's two constructors. The first one will initialize the array to be of size 16.

The other one you give it a capacity, the capacity of course, has to be greater than or equal to zero. And then we finish Why's our array and cast it to a type T also noticed I put this suppress warnings and unchecked just because of annoying generics in Java.

So here are two simple methods size, get the size of the array and check if the array is empty, pretty self explanatory. Similarly forget inset, we just index into the array if we want the value or set it if we want to set the value, technically, I shouldn't

be doing a bounds check for both of these, but I'm not apparently. Okay, clear. So here, we just remove all the data in our array and reset the length. Simple. This next one is the Add method where things actually get a little bit more complicated. So this condition

says, Hey, if the length plus one is greater than or equal to the capacity, then it's time to resize my right. The way I'm resizing is I'm doubling the size of the static array. You don't have to double the

size, but I've decided that doubling the size is convenient. So when I double the size, I have to create a new array with the new capacity. copy everything in this is what this line or these lines are doing, it's copying the old values back into this new array, and

then it sets the old array to be the new array. And lastly, here, we just copy the new value into our right. So this remove AZ method will remove a particular value at a given index. First, we check if the index is valid. If it's not through index out of bounds exception,

otherwise, grab the data at the Remove index. initialize a new array of size length minus one. Now copy everything into the new array, except

for when it's at that remove index. Now I'm sure there's easier ways to do this. But I decided to do the following maintain two indices i and j. increment i and j as you go. But when i is equal to the Remove index, then we skip over the Remove index by fixing j

temporarily and using j to lag behind, if you will while is still in the original array. So I guess pretty clever overall. And then set the array to be the new array we just generated. Reset the capacity and return the data we have just removed. So this next one

remove, we scan through the array. If we find the object we're looking for, remove it at the index and return true otherwise return false. Index of is very similar. If you find it return I otherwise return minus one. Contains just checks if index of is not equal to minus

one. All right, this next one, I return an iterator for the array. So an iterator allows us to iterate over the array providing an abstraction for it. So I need to override two methods. And this is has next. So there exists an x element in our array, if the index

is less than the length of the array. I should also be checking for concurrent modification here, just in case someone decides to change the array for some reason why we're modifying it might add that later might not.

Also, there's the next method, which just returns the next element in the array relative to the iterator. Okay, and lastly is the to string to get a string representation of this array.

Nothing too complicated. Alright, so this is a very simple data structure. It's just a dynamic array. If you look at Java's ArrayList It looks very Very similar to this. Today we're going to talk about singly and doubly linked lists one of the most useful data structures

out there. This is part one of two and the second part we will be looking at some source code on how to implement a doubly linked list. So for today's outline, in the first section, we're going to answer some basic questions concerning singly and doubly linked lists,

namely, what are they and where are they used. Next, we'll cover some terminology concerning linked lists, so everyone knows what I mean when I say the head of linked lists versus the tail of the weight class. Then last in the discussion, we'll talk about the pros

and cons of using singly and doubly linked lists, then how to insert and remove elements from both singly and doubly linked lists as well as some source code. So stay tuned. Alright, discussion. So what is the link list linked lists is a sequential list of nodes that hold

data which point to other nodes also containing data. So below is an example of a singly linked list containing some arbitrary data. Notice that every node has a pointer to the next node. Also notice that the last node points to no meaning that there are no more nodes

at this point. The last node always has a null reference to the next note, for simplicity, I will omit this in the following

slides. Okay, so where are linked lists use. One of the places they get used the most is actually in the abstract data type implementation of lists, stacks and queues because of their great time complexity for adding and removing elements. You also see linked lists and things

like circular lists, making the pointer of the last node points the first node. So circular linked lists are used to model repeating events cycles, maybe like having a round robin ordering on a bunch of elements or representing corners with polygon. So definitely allow use as they're

linked lists can also be used to model real world objects such as a line of train carts that could be useful. And moving on some more advanced examples. We also heavily use linked lists and hash table separate chaining, and for adjacency, lists and graph so we'll get

to those in a later video. Okay, a bit of terminology surrounding link lists. First thing you need to know when creating a linked list is that we always maintain a reference to the head of the link lists. This is because we need somewhere to start when traversing

our list. We give a name to the last element of the linked list. Also this is called a tail of the list. Then there are also the nodes themselves, which contain pointers. pointers are also sometimes called references. And these pointers always point the next node.

You should also know that the nodes themselves are usually represented as structs, or classes when actually implemented. We'll get to this when we look at the source code. Okay, singly versus doubly linked lists, sort of concerning the kinds of linked lists that there are there

are two types, singly linked and doubly length. singly linked lists only contain a pointer to the next node, while doubly linked lists not only contain a pointer, the next node, but also to the previous node, which makes it quite useful sometimes. This is not to

say we cannot have triple or quadruple the length lists, I just wouldn't know where to place additional pointers, pros and cons of doubly linked lists. So there are trade offs. Between picking a singly and a doubly linked list. What are they? If we look at the singly

linked lists we observed that uses less memory. Why? Well, pointers to nose can actually take up a lot of memory. If you're running on a 64 bit machine references use eight bytes on a 32 bit machine four bytes each. So having a singly linked list means you only need one

pointer for each node, hence, twice as much memory is saved. a downside however, is that you cannot access previous elements because you don't have access to them. You would need to traverse from the head of a linked lists all the way up to the previous node defined

it. Now concerning doubly linked lists with a grid Pro is that having access to the tail we can easily traverse the list backwards, something we can't do with a singly linked list. Also having a reference to know Do you want to remove, you can remove it in constant

time and patch the hole you just created. Because you have again access to both the previous and an ex notes, this is something you cannot do with a singly linked list, you would leave the list severed into a downside however, to the doubly linked list is it does

use twice as much memory. Okay, let's go into some implementation details on how we can create linked lists and remove elements from linked lists. Starting with a singly linked list. So here is a singly linked list. I've outlined where the head and the tail is. Now

we want to insert 11. At the third position where seven is currently, let's walk through an example. So the first thing we do is we create a new pointer which points to the head. This is almost always the first step in all linkless operations. Now what we're going

to do is seek up to but not including the node we want to remove. So if we seek ahead, and we advanced our traverser pointers, setting it equal to fives next node, which is now 23. And now we're actually ready already where we need to be to insert the next node. So

we create the next node, that's the green node 11. And we make 11 elevens. Next pointer, point to seven. And the next steps that change 23 is next pointer to be 11. Remember, we have access to 23 is next pointer, because we have

a reference to it with the traverser. Okay, and now we flatten out the list, we can see that we've correctly inserted 11 at the right position. And we're done. Okay, all right time to insert with a doubly linked list. This is much trickier because of all the pointers

flying around. But it's the exact same concept. Notice that the dump doubly linked list not only has pointers to the next node, but also to the previous node, we also have to change those in the insertion phase. Okay, create a traversal pointer, which points to where

the head is, and advance it until you are just before the insertion position. So we advanced the traversal by one and now we're just before the node so we start traversing let's create the new node which is node 11. Point elevens, next pointer to equal seven.

Also point leptons previous pointer to be 23. Which we have a handle on because of the traverser. How we make sevens previous pointer equal to 11. So we can go backwards from seven to 11. And the last step, make 20 threes next pointer equal to 11. This is so that we can

go forwards from 23 to 11. So in total remarked that we changed exactly four pointers. So we've flattened out the list, you can see that 11 has been inserted in the correct position. All right now how to remove elements from a singly linked list. So suppose we want to

remove the node with a value nine. How do we do this? Well, the trick we're going to use is not to use one pointer but two, you can use one but for visual effects, it's easier to show you how it is done by using two. So we create pointers, travel one and track two

for traverser one in Traverse e two respectively. So traverser one points to the head, traverse or two points to the heads. next node. Now we're going to do is advanced traffic to until we find the node we want to remove while also advancing draft one. Okay, we have found node

nine. So this is the stopping point. I'm going to create another pointer to the node we wish to remove so we can deallocate its memory later. Okay, so now I had to have advanced traffic to to the next node Note nine has turned red. I've done this to indicate that

this will that at this point, node nine is ready to be removed. I'm just keeping it around for the visual effect. Okay, so now set trav once next pointer to be equal to trap two. And now is an appropriate time to remove the temporary pointer because doing nothing with

it and their temp has been deallocated. Make sure you always clean up your memory to avoid memory leaks. This is especially important in C and c++ and other programming languages where you manage your memory. Now you can see that nine is gone, and our singly linked

list is shorter. Okay, now for the last bit of implementation, let's look at how to remove nodes from a doubly linked list, which is actually easier in my opinion to removing from singly linked lists. The idea is the same, we seek up to the node we wish to remove.

But this time, we only need one pointer. I mean one traverse or pointer. Because each node is singly linked list has a reference to the last node, so we don't need to manually maintain it like we did with the singly linked list.

So let's start travel at the very beginning and seek until we hit nine. Okay, we have reached nine. And we want to remove it from the list. To do this set for us pointer to be equal to 15 with access to four and 15 because they are traves, previous and next

pointer respectively. Similarly set 15 previous pointer to equal four. Notice that drive is now read, meaning it is ready to be removed. So we get rid of travel. And now if we flatten out the doubly linked lists, we see that it no longer contains nine. Let's do a bit of

complexity analysis on linked lists how good actually are linked lists. On the left column, we have singly linked lists. And on the right doubly linked lists. The complexity for searching in a linked list is linear in the worst case, because if the element we're looking for is

not there, we have to traverse all of the n elements. inserting it the head, though, is constant time, because we always maintain a pointer to the head for a length list, and hence we can add it in constant time. Similarly for the tail. To remove the head of a singly

linked lists, and a doubly linked list is also constant time. Again, because we have a reference to it, so we can just move it at and advanced the head by one. However, removing from the tail is another story. It takes linear time to remove elements from

a singly linked list. Can you think of Why? Well, even if we do have a reference to the tail in a singly linked lists, we can remove it but only once. Because we can't reset the value of what the tail is. So we had to seek to the end of the list and find out what the

new tail is equal to. W linked list however, do not have this problem, since they have a pointer to the previous node. So we can continually remove nodes from the tail. And finally, removing somewhere in the middle is also linear time because in the worst case,

we would need to seek through n minus one elements, which is linear. Alright, time to look at some double e linked list source code. This is part two of two in the linked

list series. So the link for the source code can be found on GitHub and github.com slash Williams he's a slash data dash structures. Please start this repository if you find the source code helpful so that others may also find it. And also make sure you watch the

first part of the linkless series before continuing. Here we are in the source code. We're looking at the implementation of a doubly linked list in Java. So first, notice that I have declared a Few instance variables. So we are keeping track of the size of the link list, as well

as what the head and the tail currently are. To begin with the head and the tail are no meaning link list is empty. Furthermore, we will be using this internal node class quite excessively, because it contains the data for our nodes. And it also contains the previous

and next pointers for each node since this is a doubly linked list. So we have one constructor for the node, namely the data and the previous and the next pointers themselves, we need both otherwise, we can't do much. So his first method I have declared here is to clear the

list, it does so in linear time by going through all the elements and deallocating them last time deallocates them by setting them equal to No. So we started to reverse or at the head, we loop while the traverser is likely to no meaning there are still elements less

and then we do our deallocation business. And at the end, we set the size equal to zero and reset the head and tail. Perfect. These size and empty methods are pretty self explanatory, get the size and check if the size of our linked list is empty. Okay, so here I have

a public method to add an element by default, we're going to append to the end of the linked list or at the tail. But I also support adding to the beginning of the linked list. So how do we do this, if this is the first element, make a list is empty, then we set the head

and the tail to be equal to the new node, which has, you can see here both previous and next pointers set to No. Otherwise, if the list is not empty, then we say the heads previous pointer is equal to this new node. And then we set the head, the head pointer

to be whatever hands previous is. So we backup the pointer in a sense. And we also don't forget to increment the size. A very similar thing is done when we want to add to the tail length list, except we're moving the tail pointer around.

OK, let's move to peak. So peaking is just looking at either the element at the beginning of the linked list or at the end of the linked list. And we throw a runtime exception if the list

is empty, because doesn't make sense to peek an empty list. Okay, now we get to the first more complex method, which is remove first. So this is if we want to remove the head of the linked list. So we can't do much if the list is empty. Otherwise, we'd get the data,

we extract the data at the head, and then move the head pointer forward, we decrease the size by one. So if the list is empty, we set the tail to be known as well. So both the head and the tail are now No. Otherwise, we deallocate the memory of the previous node

that we just removed. This is especially important if you're in C or c++, make sure to free or delete pointers, then at the end, we return the data. Very similar thing is done for last except we're using the tail this time to remove from the tail the linked list and not the

head. Okay, and here's a generic method to remove an arbitrary node remark that I set this to private because the node class itself is private so the user shouldn't have access to the node. That's just something we're using internally inside the linked list data structure

to manage the list. So if the node that we're removing is either at the head or the tail, detect that and call our methods either remove first or remove last. Otherwise, we know we're somewhere in the middle of linked list. And if we are we make the pointers adjacent to

the to our current node equal to each other. So we're effectively skipping over the current node and And of course, don't forget to clean up your memory and return the data. So we have to temporarily store the data. Of course, before we delete the node, otherwise, we've

deleted the node and the data is already gone. Now, suppose we want to remove a node of a particular index and our linked list. Yes, we can do this. Even though our nodes are not explicitly indexed, we can pretend that they are. So first check that the index is

valid, otherwise throw an illegal argument exception. So here, we are trying to be a bit smarter than just naively going through a linked list either when we start searching from the front of the linked list to find our index or from the back depending on if

the index is closer to the front or to the back, although this method remains linear. So for the Remove method, we want to be able to remove an arbitrary value from my linked list, which is object. So we're going to also support searching for null values in case

someone decided that the value of the node should be no, that's fine. So we checked that special case. Otherwise, we traverse through the length list until we find a null element and then remove that node and return true we return true if we actually found the element

we want to remove. Otherwise, we return false down here. In this else statement, we search for the element we want to remove, we use the dot equals method to check if we found the element. If so, remove that node and return true.

Okay, here we have a related method which is index of. So this is not remove at an index, or remove value, but get whatever index this object is at. Again, sports searching for

null. So even if our values No, we'll just return the first place we find no element. So again, first link list. Otherwise, search for a non null element and also increment the index as we go. We can use the index of four our method contains to check if an element

is contained within a linked list because we return minus one if the element is not found. Something that's useful sometimes is to have an iterator for the link list. This is also trivial to implement, just start a pointer, traverse at the head and traverse

until you reach the end. Notice I'm not checking for concurrent modification error, but if you want to, it's pretty easy to do that. And lastly, at the very bottom, we have to the to string method to print a string or to get rather a string representation of our

linked list. May I begin by saying that the stack is a remarkable, absolutely remarkable data structure, one of my favorites. In fact, this is part one of three in the stack videos. Part Two will consist of looking at a stack implementation, and part three will be some

source code for how a stack is implemented using a linked list. So here are the topics that we'll be covering in this video as well as the others. First we will answer the question about what is a stack and where is it used? Then we will see some really really cool examples

of how to solve problems using stacks. Afterwards, we will briefly look at how stacks are implemented internally and the time complexity associated the stacks operation. And lastly, of course, some source code. Moving on to the discussion about stacks. So what is a stack? A stack

is a one ended linear data structure which models the real world stack by having two primary operations, namely, push and pop. Below you can see an image of a stack I have constructed. There is one data member again popped off the top of the stack and another

data member getting added to the stack. Notice that there is a top pointer pointing to the block at the top The stack. This is because elements in a stack always get removed and added to the top of the pile. This behavior is commonly known as LIF o, or last in first

out. Let's look at a more detailed example on how a stack works and how things are added and removed from a stack. So let's walk through an example on the left side, I have some instructions on what we need to add and remove to the stack. So the first operation is a pop. So we remove

the top element from the stack, which is Apple. So boom, Apple is gone. Now we push onion onto the stack. So we add onion to the top of the stack. Next x instruction says to push celery onto the stack. Next is watermelon, which we put on top of the stack. Next operation

says to pop so we remove the element at the top of the stack. This is the watermelon we just added. The next operation also a pop. So we removed from the top of the stack. This is celery. And last operation push lettuce onto the stack. So we add lettuce on the very

top of the stack. So as you can see, everything operates on the top of the stack, we don't have access to anything else but the top of the stack. This is critical in our understanding of how

a stack works. So when in Where is a stack used, stacks are surprisingly used absolutely everywhere. They're using text editors to enter tags you've written in browsers to navigate backwards or forwards. They use some compilers to make sure you have the correct number of

matching braces, and in the right order. stacks are used to model real world stacks such as books, plates, and even games like the Tower of Hanoi, which we'll get to shortly.

stacks are also used behind the scenes to support recursion by keeping track of previous function calls. When a function returns it pops the current stack frame off the stack and rewinds to the next function that is on stack. It's rather remarkable that we use

stacks all the time in programming and never even notice it. Something else you can use stacks for us to perform a depth first search on a graph. A depth first search can be done manually by maintaining your own stack, or by using recursion. Well guess what both use

stacks as we have just discussed complexity analysis. So the following complexity table assumes that you implemented a stack using a linked list. Pushing takes constant time because we have a reference at the top of the stack at all times. Well the same argument

goes for popping and peeking. Searching however, still takes linear time, the element we're searching for isn't necessarily at the top of the stack. So we may need to scan all the elements in the stack, hence require a linear amount of work. Now here's the cool example

of a problem using stacks problem. So given a string made up of the following brackets, round brackets square brackets curly brackets determine whether the brackets properly match. So analyzing examples below to understand what type of bracket sequences valid and which

ones are invalid. So before I show you the solution, try and come up with a solution yourself. Hint use a stack Okay,

in this first example, consider the following bracket sequence. As we are processing the string from left to right, I will be displaying the current bracket and the associated reversed bracket. So let's begin. For every left bracket we encounter we simply push those on the stack.

So this is the left square bracket that I have highlighted in light blue. So we push this one on the stack. Same goes for the next left square bracket and for this left curly bracket

Okay, this is a right square bracket. So we encountered a right square bracket. We need to do two checks. First we check if the stack is empty. If so the bracket sequence is invalid. But

if there are still things in the stack that we pop the top element and check if its value is equal to the reversed current bracket. Right now the top element is equal to the reversed bracket. So we are good. Next is a right square bracket again. So is the stack

empty. No, it isn't. So we're good. Is the top element of the stack equal to the reversed bracket? Yes, it is. So let's keep going around a left bracket. Let's push it onto the stack. A right bracket. Is the stack empty? No. Okay, so we're good. Is the top element of the stack

equal to the reverse bracket? Yes. Okay. So we're good. And other right bracket? Is the stack empty? No. Okay, good. And there's the top element of the stack equal to the reverse bracket. Yes. Okay, good. And now we're done processing the string, we need to make sure

the stack is empty. Now. Why is that? Well, in case the last few characters and the bracket sequence were left brackets, they would still be in the stack, right? But our stack is empty. So we can conclude that this bracket sequence is indeed valid. All right, let's do another

example with another bracket sequence. So trying to work this one out. So the first bracket is a left bracket, so we push onto the stack. The second bracket is also a left bracket. So we push onto the stack. This next bracket is a right bracket. So let's check

if the stack is empty. No, it's good. And is the top element of the stack equal to the reverse bracket? Yes, it is. This next bracket is a right bracket. Is the stack empty? No. So we're good. And is the reverse bracket equal to the bracket at the top of the stack?

No, it isn't. So this bracket sequence is invalid. So here's the pseudocode of the algorithm we just ran through. So if we let us be a stack, and for every bracket in our bracket string, we can get the reverse bracket for that current bracket easily. So if our bracket

is a left bracket, push it on to the stack. Otherwise, we check if the stack is empty. And if the element at the top of the stack is not equal to the reversed. If either of those conditions are true, then we return false otherwise, we return whether the stack

is empty or not. And if it is empty, then we have a valid bracket sequence otherwise we do not. I want to take a moment and look at the Tower of Hanoi, a very popular game amongst mathematicians and computer scientists. To see how it relates with stacks. The game

is played as follows. You start with a pile of discs on the first peg on the left. And the objective of the game is to move all the disks to the right most this pile, and each move, you can move the top desk of a pile to any other pile with

a restriction that no disk be placed on top of a smaller desk. So we can think of each peg as a stack, because we're always moving the top element in a peg and placing it on another peg. So shall we play, I will let the animation

run. And you will see how each peg acts like a stack. It's pretty cool. So you just saw how transferring elements from one page to another is exactly the same as popping a disk from one stack and pushing that same disk onto another stack, given that

the disk you're placing on top is smaller. So that's really cool. Welcome to part two of three in the stack series. This is going to be a short video on one way to implement a stack. So those stacks are often implemented as either arrays singly linked lists or even

sometimes double linked lists here We'll cover how to push nodes onto a stack with a singly linked list. Later on, and we will look at the source code, which is actually written using a doubly linked list. Okay, to begin with, we need somewhere to start to be in

our link place, so we're going to point the head to a null note. This means that the stack is initially empty. Then the trick to creating a stack using a singly linked list is to insert the new elements before the head and not at the tail of the list. This way, we have pointers

pointing in the correct direction when we need to pop elements off of the stack. As we will soon see, the next element however, we need to push onto the stack is a two. So let's do that. To create a new node, adjust the head pointer to be the newest node and

then hook on the nodes next pointer to where the head was before. And we use the same idea for five and also 13. Now let's have a look at popping elements. This isn't too hard either, just move the head pointer to the next node and deallocate the last note. So here we pop

the first node off the stack and set the nodes reference to be null. So they will be picked up by the garbage collector if you're coding in Java. And it will since there are no other references pointing to it. If you're in another programming language that requires you to

explicitly deallocate free memory yourself like C or c++, now is the time to do that. Or you will get memory leaks. Getting a memory leak in a data structure is one of the worst kinds of memory leaks, especially if it's a custom data structure that you intend on

reusing. So keep watching out for that not only in this video, but in all the data structures that we will be covering. If you see in an implementation and not correctly cleaning up my memory, please please point out to me, or send a pull request to the GitHub repository

so we can patch that. Okay, so we keep proceeding by removing the head and bouncing the head pointer down to the next node. Pop again, and pop again. There we go. We've stopped popping we've reached last note and the stack is now empty. Welcome to part three of three

in the stack series videos. Today we'll be looking at some source code for a very simple stack. So the source code can be found on github.com slash William fiza slash data dash structures. Make sure you understood part one and two of the stack series before continuing.

So you actually know how we implement a stack using a linked list. Also, if you like this video series, and the implementation of the stack data structure I'm about to present to you then please start this repository on GitHub so that others can have an easier time

finding it as well. Here we are in the stack source code the senate implementation in the Java programming language. So the first thing you may notice is here I have an instance variable of a length list. This is the linked list provided by Java. In fact, it's a doubly

linked list provided by Java. This is a little lengthy list they provide in their package Java dot util that I will be using today, instead of the one that I created, and the link list

videos, this is just for portability, in case you want to use this stack for whatever reason. So we have two constructors, we can create an empty stack, or we can create a stack with one initial element. This is occasionally useful. First method we can get the size of

the stack. So to get to do that, we return the size of the internal links list with all the elements of our stack easy. We also check if the stack is empty by checking if the size is zero. So this next one is just push so to push an element onto the stack, we just

append that element as the last element in our internal linked list. Easy enough we can also pull element of the stack. So to do this, we check if the stack is empty. If it is, then we throw an empty stack exception because we can't pop an element off of an empty stack.

That doesn't make sense. Similarly, the same thing with peak, we can't observe what the top element of the stack is, if the stack is empty. And if it's not there, we can pick the last element of our list. And lastly, we can return an iterator to allow the user

to iterate through our stack. This iterator returns an iterator for our linked list, which supports concurrent modification errors. So this was a really, really quick implementation that was static. It's only like 50 lines of code. Let's talk about queues are probably

one of the most useful data structures in computer science. So this is going to be part one of three in the Q series. So the outline of things we'll be looking at. First, we're going to begin by talking about queues and what they are. Then we're going to go into

some complexity analysis concerning queues. Then we'll discuss the implementation details of n queuing and D queuing elements from a queue followed by some source code at the very end in the last video. So a discussion about queues. So what exactly is a queue?

So below you can see an image of a queue. But a queue is just a linear data structure that models a real world queue. Having two primary operations we can do which are enqueuing, and D queuing. So ever queue has a front and a back end, we insert elements through the

back and remove through the front. Adding elements to the back of the queue is called n queuing. and removing elements from the front of the queue is called D queuing. However, there's a bit of terminology surrounding queues because there's not really any consistency

or when we refer to as queuing D queuing, many people will use multiple different terms. So and queuing is also called adding but also offering a similar type of thing happens when we're talking about D queuing. So this is when we remove things from the front of the

queue. This is also called polling elements. However, some people will also refer to this as removing an element from the queue. But the problem with saying that is that can cause some ambiguity, did they mean removing from the front of the queue specifically, or from

the entire queue? Make note that if I say removing I'm going to be referring to removing from the front of the queue unless I say otherwise. So let's look at an example of how queue works in detail. However, first, notice I have labeled the queues front and back ends, so you know

where I'm going to be in queueing and D queuing from respectively to avoid confusion. first instruction says in queue 12, so we add 12 to the end of the queue, then dq, so we remove the first element from the front of the queue, which is 55. Another dq operation, this time

we removed minus one from the front of the queue. Next, and Q seven, so add seven to the back of the queue. dq, so remove the front element being 33. And lastly, and Q minus six, so at the back

of the queue, just like that. So now that we know where a queue is, where does this data structure actually get used? Well, a classic example of where cuneus gets us is to model a real world queue where you're

waiting in line at a movie theater or in the line at a restaurant. For instance, have you ever been to say McDonald's, where all the caches are full. As soon as one of them gets fried, the next person in line gets to order food? Well, that's a cue. So queues are can

also be really useful if you have a sequence of elements coming in, but you only keep track of say, the x most recent elements, while you can add those elements to queue, and once your queue gets larger than x elements, just dq essentially queues are also often used

in server management. So, suppose for a moment that you have a web server, that's idly waiting for requests from people to use your website, that at any given moment, you can simultaneously serve up to five people. But no more. If 12 requests come in, in a short amount of time,

you're not going to be able to process all of them as new ones come in. So what you do is you process the five that you're able to, and the remaining seven gets a chill and a queue waiting to be served. And whenever you finish processing a request, you dq and the

next request, and then you start processing it, and you do this until the queue is empty. While you're doing this, more requests come in to access your web page, while you just add them to the end of the cube. queues are also using graph theory. To perform a breadth

first search traversal on a graph, which is actually really useful. We're going to see this example in the next video. All right now concerning complexity analysis of a queue. So as we're seeing, it's pretty obvious that n queuing and D queuing operations are constant

time. There's also another operation on a queue I have not mentioned yet, and this is peaking. peaking means that we're looking at the value at the front of the queue without removing it, the source or cost and time. However, checky if an element is contained

within the queue, is linear time since we would potentially need to scan through all the elements. There's also element removal In this sense, not in the sense of D queuing or polling, but in actually removing an element from the queue internally. This also requires

linear time, since we would have to scan through all unknown elements in the worst case. In this video, we're going to have a look at how queues are used to do a breadth first search. And then we're going to look at the actual implementation details of how n queuing

and D queuing elements works. Okay, onto the breadth first search example. So breadth first search is an operation we can do on the graph to do a graph traversal. If you don't know what I mean, when I say graph, I mean a network not a bar graph or a line graph or anything

like that. But first, I should explain the breadth first search in the breadth first search. The objective is to start a node and traverse the entire graph, first by visiting all the neighbors of the starting node, and then visiting all the neighbors of the first

node you visited and then all the neighbors of the second node you visited and so on, so forth, expanding through all the neighbors as you go. So you can think of each iteration of the breadth first search as expanding the frontier from one node outwards at each iteration

as you go on. So let's begin our breadth first search at node zero. So I'm going to label node zero as yellow and put it in the frontier or the visiting group. And now I'm going to visit all the neighbors of zero being one and nine and add those to the frontier. And

then we resolve the neighbors of one and nine being only eight. Similarly, for eight, so seven, and visit all the neighbors of seven. So I added a bunch of elements, my friend here, and now visit all the neighbors of the yellow nodes.

And now we're done our breadth first search because we no longer have any elements on frontier. Notice that there's 12 that is the unvisited because 12 is a lunar node on an island all by itself. So we are not able to reach it for the breadth first search, which

is fine. Suppose you want to actually code a breadth first search, how would that be done? Well, the idea is to use a cube. So first, we add the starting node to our queue. And then we mark the starting node as visited. And while our queue is not empty, we pull

an element from our queue or D queuing. And then for every neighbor of this node, we just D queued if the neighbor has not been visited yet mark the neighbor is visited and added to the queue. So now we have a way of processing all the nodes in our graph in a breadth first

search order. Really, really useful, very, very popular graph traversal algorithm. So now let's look at implementation of queues. So let's begin with an queueing. So it turns out that you can implement the queue abstract data type in multiple different ways. But

the most popular methods are to either use arrays, singly linked lists, or doubly linked lists. If you're using an array, you have to make sure your arrays are going to be big enough. If it's a static

array, if it's a dynamic array, then you'll be fine. Right here, I'm going to show you how to do it with a singly linked list and the source code, we're using a doubly linked list. So stay

tuned for that. In a singly linked list, we're going to have a head pointer and a tail pointer. So initially, they're both No. But as we n q, we add, well, we just add the first note, so nothing really interesting is going on right now. But as we add more elements, you

can see that we're pushing the tail pointer forward. So we're adding a node and then getting the tail pointer point to the next node. Now dq is a bit of the opposite. And so pushing the tail forward, we're going to be pushing the head forward. So push the head forward

one, and then the element that was left over was the one we want to dq and return to the user. So why don't we push the head pointer forward, we said in the last note to know so that it can be picked up by the garbage collector if you're in Java. And if you're

in another programming language, which requires you to explicitly deallocate or free memory, yourself like C or c++, now's the time to do that. So you see, as we keep D queuing, we're just pushing the head forward and forward again. And at the very end, if we add a bunch

of elements, then remove them all then the head and the tail again, point to know which is where we started. All right, now it's time to have a look at some source code for Q. So I implemented a queue and you can find the source code at the following link on github.com

slash my user name slash data dash structures. Also make sure you have watched and understood parts one and two from the Q series before continuing. Alright, here we are looking at some source code for a queue. So this source code is in the Java programming language,

although you can probably translate it into any programming language that you need. So the first thing to remark is I have an instance variable here of a linked list. So this is a Java's implementation of a doubly linked list. We also use this in the stack implementation,

as you'll see the queue and the stack implementations are very, very similar. So here I have two constructors, one create just an empty queue. And another optional one, which will create a queue but with a first element. In fact, I should probably check if this is no, but

we we might want to allow no elements. So let's just leave it like that. So the next method is the size, it just gets the size of the link list. And similarly, this checks if the length list is empty. Those are both pretty self explanatory. Okay, next interesting

method is the peak method, the peak method returns the element that's at the front of the queue, but it will throw an error if your queue is empty because you can't peek anything when your queue is empty. Similarly, for poll, this will pull the element to the front of

the queue, but unlike peak will actually remove the element from the queue. So next, we scroll down a little bit, I have offer which adds an element to the back of the queue. I guess I am allowing for no elements. So if you don't want elements, just put an if statement and

throw an error or something. So the poll removed from the front. And you can see offer ads to the back. So remove first and add last. And the last method. And here is an iterator in case you want to be able to iterate through all the elements in your queue. Very short

and very simple implementation just under 50 lines of code, you can create a queue. Although there are faster ways of creating queues, especially with arrays. The idea with arrays, especially static arrays, if you know the maximum amount of elements

that will be in your queue at any given time, then you can create an array of that maximum size and have pointers to the front and the back positions in your queue. And add and remove elements based on the relative position of those pointers. If you ever get to a position

where you're running off the edge of your array, then you can loop around to the front of the array and keep processing elements like that this a lot faster than having to maintain references to the next node, such as in a linked list. So I guess I'll say that's

your homework is to create a static array based queue. Today, we're going to talk about everything to do with priority queues from where they're used to how they're implemented. And towards the end, we'll also have a look at some source code. Along with all the priority

queue stuff. We're also going to talk about heaps since both topics are closely related, although not the same. So the outline for the priority queue series is we're going to start with the basics talking about what are priority queues and why they're useful. And

then we'll move on to some common operations we do on priority queues and also discuss how we can turn min priority queues into max priority queues followed by some complexity analysis. And we'll talk about common ways we have implemented priority queues. Most

people think heaps are the only way we can implement a priority queue, or that priority queues somehow are heaps, I want to dispel that confusion. Next, we're going to go into some great detail about how to implement the priority queue using a binary heap. there

we'll look at methods of sinking and swimming nodes up and down our heap. These terms are used to get and shuffle around elements in a binary heap. As part of the implementation explanation, I also go over how to pull and add elements. So there's a lot to cover. So

let's get started. discussion and examples. This is going to be part one of five in the priority queue series. So what is a priority queue? a priority queue is an abstract data type that operates similar to a normal queue except for the fact that every element has

a certain priority. So elements with a higher priority come out of the priority queue first. As a side note, I'd like to remark that priority queues only support elements that are comparable, meaning that the data we insert into the priority queue must be ordered in some way, either

from least to greatest or raised lease. This is so we can assign relative priorities between elements. Okay, let's go into an example. So suppose we have all these values that we inserted into a priority queue on the right, and that we impose an ordering on the numbers

such that we want to order them from least to greatest. So the smaller numbers have a higher priority than the bigger ones. So they will be removed from the priority queue first. Suppose we have now a list of instructions. So what the poll operation means is remove

the element that has the highest priority in our priority queue. So let's see how this works. So if I say Paul, then I remove the element with the highest priority, which happened to be one. Now I say add two, so we add two to our priority queue. And Paul, so next report

of smallest elements in our priority queue, and that happened to be the two we just added. Next, we add for all this smallest, this is three, add five, oh, also add nine and then pull the rest. So as I pull the rest, I'm continuously grabbing the smallest element

in the priority queue. So it turns out that as we added, and Paul numbers, we got an ordered sequence. This is a coincidence. Actually, as we added the pull numbers from the priority

queue, we do not necessarily end up getting an ordered sequence, we are only guaranteed that the next number that is removed from the priority queue is the smallest number that was currently in the priority queue. So how does the priority queue know, which

is the next smallest number to remove? As humans, we could see the numbers visually inside the priority queue and look and know what one was the smallest the whole operation was going to return. But fundamentally, how does the machine know this? Does it resort

all the elements inside a priority queue before each pull operation? No, in fact, that would be highly ineffective. Instead, it uses what is called a heap. So the next big question then is what is a heap? Usually I make up my own definitions, but I really liked this

one from wiki. A heap is a tree based data structure that satisfies the heap invariant also called the heap property. If a is a parent node of B, then A is ordered with respect to B for all nodes A and B in the heap. What this means is the value of the parent node

is always greater than or equal to the value of the child node for all nodes. Or the other way around that the value of the parent node is less than or equal to the value of the child node for all nodes. This means we end up getting two types of heaps, Max heaps,

and min heaps. So max heaps are the one with where the parent node is always greater than its children. And the min heap is the opposite. So both of the following are actually binary heaps binary because every node has exactly two children. And the children cannot see

or no values I have not drawn in. So why are we interested in heaps? heaps form the canonical underlying data structure for priority queues? So much so that priority queues are sometimes called heaps, although this isn't technically correct, since the priority queue, again,

is an abstract data type, meaning it can be implemented with other data structures also. Okay, we're going to play a little game, I'm going to give you some structures. And you need to tell me whether it is a heap or not. So inspect the following structure and try

to determine whether it's a heap or not, you can pause the video if you'd like. But I'm just going to give you a short moment here. No, we have a violation of the heap invariant and this tree. So it's not a heap. Is this structure a heap? Yes, it is a heap because

it satisfies a heap invariant, and it is a tree. So we often see heaps like these and why we're called binomial heaps. Note that heaps aren't necessarily binary heaps. They can have any number of branches. On to our next one. So is this a valid heap? Yeah, it's

a valid heap. Because even though this one is strangely, strangely structured, we're free to move around the visual representation of the nodes as we please. So yeah, it's a valid heap. How about this one? No, this structure is actually not even a tree because it contains

the cycles. All heaps must be trees. What about this one? Yeah, so heap. What about this one? Also heap because it satisfies the heap invariant that all all nodes are less than or equal to or greater than or equal to its parent. How about this one? No, it's

not onto the heap and because it does not satisfy that heap invariant. However, if we do change the root to be 10, then we can satisfy the heap invariant via a min heap. Or rather sorry, a max heap. So when and where is a priority queue and he used probably one

of the most popular places we see priority queues is in Dykstra shortest path algorithm to fetch the next nodes we explore. priority queues are really handy anytime you also need a behavior in which you need to dynamically fetch the next best or the next worst element.

They're also used in Huffman encoding, which is often use for lossless data compression. Many best first search algorithms use priority queues in their implementation to continuously gain grab the next most promising node in the graph as it's being traversed. And finally,

we also see priority queues in prims minimum spanning tree algorithm on directed graphs. So it seems priority queues are really important, especially for graph theory algorithms, which is where we see them often. Okay, on to some complexity with priority queues implemented

as a binary heap. To begin with, there exists a method to construct a binary heap from an unordered array in linear time, we're not going to cover this algorithm, but it's pretty cool. And it forms the basis for the sorting algorithm heapsort. Next is pulling and, or

rather removing pulling or removing an element from the root of the heap. This takes logarithmic time, because you need to restore the heap invariant, which can take up to logarithmic time. So peaking or seeing the value at the top of our heap can take constant time, which

is really nice. Adding an element to our heap takes logarithmic time, again part because we possibly have to reshuffled heap by bubbling up the value as we will see in a later video. Then there are a few more operations we can do on priority queues. So removing a an element,

which is not the root element. So the naive way of removing an element in a heap is to do a linear scan to find the items position and then remove it. The problem with this is it can be extremely slow in some situations, especially if you're removing a lot. But generally

don't do this. And it's not a problem, which is why most implementations are just Yes, lazy and do the linear scan solution. However, there does exist a way to reduce the removing time complexity, which I will go over later in a later video in great detail in this video

series. So stay tuned for that this method uses a hash table to reduce the removing time complexity to be logarithmic, which is super critical, actually, if you're removing as much as you are adding. Now the naive method to check containment within a heap. binary

heap is linear. Again, you just scan through all the elements. But with the help of a hash table, we can reduce this to be a constant time, which is super neat. Especially if we use the hash table implementation for the removing speed up we get as a free bonus.

The downside however, to using hash table implementation is that it does require an extra linear space factor. And it does add some constant overhead because you're accessing your table a lot during swaps. Today, we're going to talk about turning min priority queues

into max priority queues. This is part two, a five in the priority queue series. So you may already be asking yourself, why is it important that I know how to convert a main priority queue into a max priority queue? Well, here's the problem. Often in the standard

library, most programming languages, they will only provide you with either a max priority queue or a min priority queue. Usually it's a main priority queue, which sorts elements by the smallest element first, but sometimes we need the max priority queue depending on

what we're programming. So how do we do this? How do we convert one part one type of priority queue To another type. Well, a hack we can use is to abuse the fact that all elements in a priority queue must implement some sort

of comparable interface, which we can simply negate, or invert. To get the other type of heap. Let's look at some examples. Suppose for a moment that we have a priority queue consisting of elements that are on the right side of this screen, and that these are in

that min priority queue. So if x and y are numbers in the priority queue, and x is less than or equal to y, then x will come out of the priority queue before y. the negation of this is x is greater than or equal to y. And so y then comes out before x, because

all these elements are still in the priority queue. Wait a moment you say, isn't the negation of x is less than or equal to y, just x greater than y, and not x is greater than or equal to y? Well, not for competitors. You see if x is equal to y, whether or not the competitor

is negated, x should still equal y. So now let's see what happens when we pull all these elements out of priority queue with our negated comparateur. So first, we will get 13 because it's the greatest. Next comes 11 753. And two. An alternative method for numbers is

to negate the number before you insert it and negate it. Again, when it comes out. This is a hack specific to numbers, but it's pretty nice. So let's see how that works. So let's negate all the numbers inside a priority queue. And now we can see that definitely minus 13

is the smallest so should come out first. So minus 13, and indeed comes up first. But now we have to remake the data and we 13. Everything is good so far. Next is minus 11. So really positive 11. And so on my seven, seven, and so I'm just so keep polling and

then arena, get the value to get it out of the priority queue. It's a pretty neat hack. Okay, now let's look at my other examples using strings. So suppose Lex is a competitor for strings, which sorts strings in lexicographic. Order, this is the default for most programming

languages, then, let's call n Lex be the negation of Lex. And also let's assign s one and s two to be some non null strings. So below, you can see that our comparateur assigns minus one if s one is less than s two Lexa graphically zero. So equal x so graphically, and plus

one if s one is greater than s two lexicographically. And then n lacks is just the negation of that. So just to break it down, ALEKS sorts strings, like so graphically, but we're interested in gaining legs so that longer strings appear before sort of shorter strings and also that

strings with letters at the end of the alphabet appear before those containing letters. At the beginning of the alphabet, I think I said that right. This was in effect turn a man he into a maxi beep. Let's look at a concrete example. So by adding all the numbers on the

right to a prayer queue with the lexicographic comparateur, here's the ordering we should expect. First we get a because it's the shortest string that has characters appearing closer closest to the start of the alphabet, then it comes at B, then f Zed, then x then x R

and x x. So now let's do the same thing with n Lex. And we should hopefully obtain the opposite sequence in reverse order. And then we get x x x r x f, Zed mi N A. So it did exactly what we intended to do. Today

we're going to talk about adding elements to a binary heap. This is part three of five The priority queue series, we'll get to adding elements to our binary heap shortly. But first, there are some important terminology and concepts leading to that, which we need to go over

prior to add elements effectively to our priority queue. Okay, so a very popular way to implement a priority queue is to use some kind of heap. This is because heaps are the data structure, which give us the best possible time complexity for the operations we need to perform with

a priority queue. However, I want to make this clear, a priority queue is not a heap. A priority queue is an abstract data type that defines the behavior a priority queue should have. The heap just lets us actually implement that behavior. As an example, we

could use an unordered list to achieve the same behavior we want for a priority queue. But this would not give us the best possible time complexity. So concerning heaps, there are many different types of heaps including binary heaps, Fibonacci heaps, binomial heap,

pairing heaps, and so on, so on. But for simplicity, we're just going to use the binary heap. binary heap is a binary tree that supports the heap invariant. In a binary tree, every node has exactly two children. So the following structure is a binary heap, which satisfies the heap

property that every parent's value is greater than or equal to the child that every node has exactly two children. Well, no, you may be thinking the bottom nodes, also known as leafs don't have children. Well, actually, Yes, they do. Here they are. They're the knowledge

children in gray. But for simplicity, I won't draw those because they're annoying to draw. Okay. The next important bit of terminology, we need to understand is the complete binary tree property. The complete binary tree property means that at every level, except possibly

the last is completely filled, and that all the nodes are as far left as possible in the binary tree. As you will see, when we insert nodes, we always insert them at the bottom row. As far left to meet this complete binary tree property. Maintaining the complete binary

tree property is very, very important, because it gives us an insertion point, no matter what the heap looks like, or what values are in it. The next note, we insert will go into the hollow circle that and the next one will go to the right of it, and so on until eventually

we fill up the row, at which point we need to start a new row. So the insertion point is a very important. One last thing before we actually get into how to add values into a binary heap, is we need to understand how to represent one of these binary heaps. And

there is a canonical way of doing this, which is to use an array actually. So using an array is a very convenient actually, because when we're maintaining this complete tree property, the insertion position is just the last position in our array. However, this isn't the only

way we can represent the heap, we can also represent the heap using objects and pointers and recursively add and remove nodes as needed. But the array construction is very elegant, and also very, very fast. So on the left is the index tree just to help you visualize

the position of each node in the array. And on the right is the actual tree remark that as you read elements in the array from left to right, it's as though you're pacing through the heap, one layer at a time.

So if we're at no nine, which is index zero, we're at the top for node eight. We're at position one. And as I keep moving along, you can see that we're just pacing through the array going from left to right. So it's very convenient, that way When not also another

interesting property of story, I'm binary heap in array is that you can easily access all the children and parent nodes. So suppose I is the index of a parent node, then the left child is going to be at index two times i plus one, and the right child of that node

is going to be at two i plus two, this is zero base. If it's one base, then you would just subtract one. So suppose we have a node seven, which is highlighted in purple. Well, its index is two. So by our formula, the left child of seven should be located at two times

two, plus one, or, or five. If we look at index five, we expect to get one and if we look at the right child, we should expect to get two times two plus two or six. If we look in our array, this gives us the value of two. So using this technique, we have all

we need to manipulate the knowns now array in the source code I will be presenting in Part Five for the series, we will see that I use this representation for simplicity. All right. So now we want to know, how do I add nodes to a binary heap and to maintain

the heap invariant, because if we I noticed our binary tree and we don't maintain the heap property? Well, the binary heap is useless. We'll do some examples. On the left, I have some instructions, which tell us what values we need to insert into the heap. The first

value is a one, which we can see, which should actually appear at the root, since we're dealing with a min heap. But instead of inserting wire the route directly, what we do is we put one at the bottom left of the tree in the insertion position I was talking about

and performance call bubbling up as my undergrad prof loves to say, this is sometimes called swimming or even sifting up all really cool names for a really neat operation. So we answered one and the insertion position. But now we're in violation of the heap invariant since one

is less than seven, but one is found below seven. So what do we do, what we do is we swap one and seven, like so. But now we're still in violation of the heap property, since one is a child of six, but one is less than six. So what do we do we swap them, but yet

again, violation the property. So we swap, and now one is at the root where it should be. And now the heap invariant to satisfy and we can stop swimming or bubbling up or whatever you want to call it. So the next one is 13. So as usual, begin by putting it

in the insertion position. And now, we need to satisfy the heap invariant, so bubble up 13. Notice that we're no longer in violation of the heap property since 14 is less than 13, and 13 is less than 12. So 13 is actually in its correct position. Sometimes we don't

have to bubble up our elements that much. The next values we need to insert are for zero and 10. Try seeing where these end up, pause the video if you need. It's a good little exercise. But I will keep going for now. So forgoes in the insertion spot left of all

the nodes, it's there, and we bubble it up until we can't anymore. And we start with the property is satisfied. Next zero, my favorite number. Of course, I've arranged that zero be at the top of the tree as you will see right now in violation of the heap invariant.

So let us bubble up and like magic zeros at the top of the tree. Next is insert 10. Next numbers 10. So we put out an insertion position. And however this does not violate the heap invariant, so we do nothing.

Today we're going to look at how to remove elements from a binary heap. This is Part Four or five in the priority queue series. Make sure you watch the last video so we understand the underlying structure of the binary heap.

So let's get started. In general, with heaps we always want to remove the root value because it's the node of interest. It's the one of the highest priority is the smallest or the largest value when we remove

Route, we call it polling, a special thing about removing the route that we don't need to search for its index. Because in an array implementation, it has position, or index zero. So when I say pull in red, we have the node we want to remove, and in purple is the

one we're going to swap it with. So the note in purple is always going to be the one at the end of our array, which we also have its index. So we swapped them, we get rid of the one. And now, since 10 is at the top, well, we're not satisfying the heap invariant. So

we need to make sure that the heap invariant is satisfied. So we need to do what's called bubbling down now instead of bubbling up. So what we do is we look at 10s, children, five and one, and we select the smallest, and we swap with the smallest. So 10 would

go to one. So make sure you default, selecting the left node in case there was a tie. So as you can see, 1010s children are two and two, they're both equal. So we're going to select the left node to break tight. And now we bubble down 10 again. And now the heap

invariant is satisfied. Now we want to remove the value 12. So pulling was removing the element at the root. But 12 is not at the root. However, we still want to be able to remove 12. So what we do is we have to search for 12 in our tree, even though we don't know

its position yet. So we start at one, and we do a linear scan through all our elements until we find 12. So five is not 12, two is not 12, and so on until find 12. And now we found 12. And now we know where its position is. So we can mark it as the node we want

to remove, and also swap it with the purple node being the last node in our tree, swap them remove the 12. And now we're in violation of the heap invariant. So now we want to bubble up three, until the heap invariant is satisfied. And now we've satisfied the heap invariant

so we can start. Now we want to remove three, same thing as last time search for three in the tree. Three wasn't far it was just two nodes away. So now to remove an element, again, swap it with the last node in the tree. Drop it. But now the question is, do we bubble

up or bubble down the value because you don't really know what the value of the node and last position is when you're swapping it in. So this is we bubble up a bubble down Well, we already satisfy that heap invariant from above. So we need to bubble down 15. So So

five was smaller, so we swapped it with five, now eight are smaller, so we swap it with eight. And again, the heap invariants are satisfied. Now we want to pull So Mark, the root node, red swap it, remove the one. And now we want to buckle down. And the heap invariant

is satisfied. Now we want to remove six. So search for six in our tree. Okay, we have found six and do the swap. Remove six. Now do we bubble up a bubble down? The answer is neither the heap invariant is already satisfied. So we don't need to touch our node.

We got lucky. So from all this polling and removing we can conclude the following that polling takes logarithmic time since we're removing the root and we already know where to find it. And also that removing a random node can take up to linear time. So We have

to actually find the index of that node we want to remove before removing it. However, if you're as dissatisfied with this linear removal as I am, you'd figure out that there has to be a better way. And indeed there is. And I'm about to show you a hack to improve

this complexity to be logarithmic in the general case. So stay tuned. Okay, so now we're looking at how to remove nodes on my heap with the improved time complexity. To do this, we'll need to make use of a hash table, a data structure I have not yet covered. So buckle up, things

are about to get a little wild. I promise I'll cover the hash table thoroughly in a later video. But right now, it's going to look like magic. Back to the central issue, we have a bunch of nodes scatter across our heap at some positions, and instead of doing

a linear scan to find out where the node we want to remove is, we just want to be able to do a lookup and figure that out. The way we're going to do this is that every node is going to be mapped to the indexes found that. So when we want to remove a particular

node, just look up its index and started doing it. Linear scan. Sounds good, right? That sounds great, except for one caveat. What about if the heap has multiple nodes with the same value? What problems will that cause? Well, just a few but nothing we can't handle.

To begin with, let's talk about how we can deal with the multiple value problem. Instead of mapping one value to one position, we will map one value to multiple positions. And we can do this by maintaining a set or tree set of indices for which a particular node value

or key if you want maps to. So can I example. Okay, so observe the blue heap remark that has repeated values. Namely, we can see that the two is there, three times seven is there twice, 11 and 13. Once the low I have drawn the index tree, a tree, which can help us

determine the index position of a node in the tree 11, for example, is that index 313 at index five, and the first to index zero. On the left is the hash table. With the key value pairs. Notice that two is found in three positions 02, and six, while seven is found

two positions, one and four, and so on. So this is how we're going to keep track of the positions of the values in the tree. If notes start moving in the tree, we also need to keep track of that. For example, if a bubble up or a bubble down cursory to track all those

movements, and where the swabs go to so we can update the index position in our map, we swap 13. And the last seven, for example, the following should happen. So we look at where seven and 13 are in our table. And then I've mapped those respective positions as

red for the seven and yellow for the 13. And this is what happens when we do a swap, we do a swap in the tree but also in the table. And that's it. Okay, so this all sounds great. We keep track of repeated values by maintaining a set of indices apart to the node, the particular

value was found out. But now let's ask a further question. If we want to remove a repeated node in our heap, which node do we remove and doesn't matter? Because if we look in our heap right here, there's three possible two values we can remove doesn't matter which

one we remove. The answer is no, it does not matter. As long as in the end, we satisfy the heap invariant and that's the most important thing. So let's look at an example. Not just for removing

but also of adding and pulling elements with this new scheme I just proposed. It's not that hard, trust me. So first one, we want to insert three. Sweet place three at the bottom of the heap in the insertion position. We also need To track where the new node is,

so we add three to our table long with its position, which happens to be at index seven. Look at the index, tree and grade confirm this. Now that three is has been inserted, we need to make sure the heap invariant satisfied, currently it is not. So what we do is we bubble

up three, the parent of three is 11, which is greater than three, so we need to swap those two notes, I have highlighted the seven and the index three because it maps to three in the heap and three in the index three, because it maps to the value 11. Now swap

those both in the tree and in the table. Awesome. Now the heap variants still not satisfied. So do a similar thing. For the note above, we grab the parent and do a swap in the tree on the table. And now the bat invariants are satisfied. So three has been inserted successfully.

The next instruction is to remove to from the heap. So which tool should we remove? Well, as I said, it doesn't matter as long as we satisfy the heap invariant in the end. If we remove the last two, we can immediately satisfy the heap invariant with one swamp.

But for learning purposes, I will simply remove the first one found in our set, which happens to be located at index zero. So we want to remove the two at position zero. So how do we remove a note again, so we did a look up. So we didn't have to do that linear scan,

which was nice. And now we swap it with the end, the last node, which happens to be 11, we remove the last node. Now we need to satisfy the heap invariant. So we need to bubble down 11. So we look at 11 children, which happens to be three and two, two is smaller. So it's

the one we're going to swap with. So swap it in the table and, and the tree. Now, we are still not in satisfaction of the human variant. So look at 11th children being 13 into two smaller, so swap it with two. And that's it, we're done. The last instruction

says the poll, so we get the value of the route, just two and swap it with 11. Get rid of the two and bubble down 11. So as you can see, we're constantly updating our table and but still doing the same operations. This is part five of five and the priority queue

series. And we're going to have a look at some source code for the priority queue today. So if you want the source code, here's the GitHub link. With all the data structures in the series, the priority queue is one of them. Also make sure you've watched parts

124, so you can actually understand what's going on. Alright, let's dive into the code. Alright, here we are inside the source code. So notice that inside my priority queue, the types of elements I'm allowing inside my priority queue have to be comparable elements as we

talked about. So if they implement the comparable interface, then we are going to allow them inside our queue. So this is anything like strings, integers, anything with a comparable interface. So let's have a look at some of the instance variables. So I have the heap

size. So this is the number of elements currently inside the heap. But then I also have another instance variable, which is the heat capacity. So this is going to be the size of the list. That we have four elements which may be larger than the heap size is. And this is the actual

heap. And we're going to be maintaining it as a dynamic list of elements using Java's list. Next, for our logging of and removals, I'm also going to keep track of this map as you

want to map an element to a tree set of integers. So these won't be all the positions inside our heap, which we can find this element T. All right. Next, I've got a few different constructors for our priority queue. We can just Create a brighter queue. And by default,

I'm creating and initially empty priority queue with a capacity of one. But I also allow you to create a priority queue with a defined initial capacity, which actually is more useful, because then we don't have to keep expanding our dynamic list every time. So I would recommend

this. But also, even better, is if you know all the elements that are going to be inside your heap, you can actually construct the priority queue in linear time, using an operation called heapify, which I didn't talk about in the slides. But both can be very, very

useful. So So this just has all the usual setup stuff. Here, I'm adding all the elements to the math and but also to the heap. And then here's the heapify process. So we start at halfway through the heap size, and then we start decreasing, and then we sync all

the elements. And you're like, Wait a second, isn't the seek sink? a logarithmic removal? Well, yes, it is in the general case, but not if we're doing it in this fashion. I put a link to this paper appear just because the heapify operation isn't quite intuitive why

it has this linear complexity. And if you look at the analysis in the paper, you will end up seeing that the complexity boils down to a convergent series. And that's why we constantly say it's linear time. But in general, this isn't what you might be tempted to do.

If you're given a collection of elements, you would initialize the heap, and then you would just use our add method to add the elements one at a time. And this will give you an N log N bound. But definitely use the heapify whenever possible. Okay, now some pretty simple

methods we have is empty, just returns true or false if the heap is empty or not, then clear. So when we clear the heap, we remove all the elements inside our heap array, but also inside our map. So that's why he called map dotclear. Size returns a size, it's pretty

simple. peek, the first really useful method just looks at the top of our primary priority queue. And if it's empty returns No. Otherwise, we do a look up at the first index inside our heap and return it because it's the root node

poll. Similar to pique, except that we're going to remove, remove the very first element. And we're also going to return it because you want that information. x contains. So

because we have a map with our elements, we can do a map lookup to see if our elements inside heap. And this reduces our complexity from linear, in which case, we have to scan through a linear scan through all elements to check containment to constant time, which

is remarkable. But you have a job in case people don't usually maintain this map. I just wanted to do it. Just to show you guys that is possible. Although the map does add a lot of constant overhead and you may or may not want. I personally find that the overhead

is quite a lot. And I usually don't really remove things very frequently for maps. So it might not be entirely worth it. But it's up to you. If you're doing as many additions as you are removals then definitely worth it. Alright, now let's have a look at the

Add method. So, so this element, sorry, this method adds an element to the prayer queue. And that element cannot be no. So what we do is, first we check if our heap size is less than capacity. Otherwise we have to expand our capacity of the heap. Next, we make sure

we add it to the map. So we keep track of it. And then we swim it up. Remember that we have to swim. I know Rob because we add it to the very end of our list. And so we had to, like adjust where it goes inside our heap by swimming upwards. This next method

called less is is a helper method, which helps me check if node i is less than or equal to node j. And this uses the fact that both elements node one and node two are comparable. So we can invoke the Compare to method. If we go back up that comes from this interface, the

comparable interface, which we needed. So, let's go back down. Alright, so returns true if i is less than or equal to J. Awesome. So next, this is the bottom up notes. So we are going to try to swim node k. So first, who grabbed the parent of node k, we can do

that by solving for the parent. So remember that I'm working in. I'm starting at zero, some people like to start the heaps index, that one, I like everything's zero based. So I get the parent, which is that this position k minus one divided by two, because we're

going upwards. And while K is still greater than zero, so we're not at the root, and we're less than our parent, then we want to swim upwards. So we're going to swap the nodes parent and K. And then K is when we can become the new parent. And then we have to get the

parent of K once more. And then we'll keep doing this going up our heap and swapping notes. So that's how you do the swim. So the sink is similar, but a little different. So top down node sink. And here, we want to sync node k. And what we do is I grab the left

node, but I also grab the right node. Remember, we're working zero based, so plus one plus two instead of a plus zero plus one. And then I need to figure out, which is less either is going to be the left one or the right one. And I assumed to start with that the left

one is going to be smaller than the right one. And here I correct that hypothesis, in case it was false. So I checked that the right notice within the size of the heap. And if the right node is less than the left node, then the smallest ones are going to be the

right node. And our stopping condition is that we are outside the bounds of the tree, or we can't sink any more. And we can do a similar thing, we swap and then case the next smallest here

like like we did in the last method also. So the swap method, I made a an explicit method to swap because I also have to swap things inside the map and then set the values also. And this is really what adds a lot of overhead for the math is the fact that every time we

call the swap method, we also have to swap things inside the map, which, which can be a lot of overhead really, it technically maps our constant lookup times but the fact that you're doing all this internal hashing and collisions and whatnot, it can get costly.

So remove. So if the element is now returned false, we know we don't have any no elements inside our heap. So this is how you would do a linear removal and linear time, I commented out in case you want to revert back and remove the map and whatnot, is with scan through

all the elements. And once you find the element you were looking for, just remove it at that index and return true. Otherwise, we're going to use our map. So get the index so wherever the element one of the elements are. And if it exists, then remove it at that index. Okay,

now let's have a look at the Remove add method. So this is what I covered in the last video. So if our heap is empty, well, can't really remove anything. Otherwise, we're going to swap the index Why remove with the last element, which is going to be at heap size. And then

we're going to kill off that node and also remove it from our map. So if it so happened that I was equal to the heap size, meaning we just removed the very last element in our heap, just remove, return the removed data. Otherwise, when we did the swap, we have to

either sink that node up or down. And I'm caring too lazy to check whether I need to sink or swim. So I just tried both. So first I try sinking and then if nothing happened, then I try swimming downwards. And in either case, return the Remove data. Perfect. So

this just readjusts where, where the swap node position goes, either bubble up or bubble down. This method is just a method I use in my testing framework to make sure everything is good. So it checks essentially the integrity of the minimum heap. So initially, you call

this method with K equals zero, and that starts at the root as you want to recursively go down the tree and check are we maintaining the heap invariant property which we need. So our basis, you want to be that k is outside the heap size. And if so, we're just going

to return true. Otherwise, get our children left and right. And now, we're going to make sure that k is less than both our children. And if that's not the case, return false. And if we ever returned false, because we have an and statement when we're recursing,

right here, that that gets propagated throughout the recursion, and this whole method will return false. Otherwise, if everything returns true and hits the base case, then we know for sure it's in the minimum

heap. Okay, these last few methods are just map helper methods. So things to add things into the map, things, how to remove elements from the map, and so on. And what I'm doing here, as I'm using a tree set to add and remove elements, because I know the tree set implementation,

Java has a Balanced Binary Search Tree. So all operations on tree sets are logarithmic, which is really nice. So you guys can have a look at those in more detail. It just gets values removes values. And lastly, do a map swap. So yeah, it swaps values in the heap,

or in the map rather. So yes, have a look at those in more detail. But I pretty much covered everything about the priority queue. All right, time to talk about the union find also sometimes called the disjoint set, this is my favorite data structure. So let's get

started. So an outline of things we'll be covering about the union fight. First, I'll be going over a motivating example, magnets. Just to illustrate how useful the union find be. Then we'll go over a classic example of an algorithm which uses the union find specifically

crucibles a minimum spanning tree algorithm, which is very elegant, and you'll see why it needs the union find to get the complexity it has. Then we're going to go into some detail concerning the find in the Union operations, the two core operations, the union find users.

And finally, we'll have a look at path compression. What gives us the really nice amortized constant time the unifying provides? Ok, let's dive into some discussion examples concerning the union find. So what what is the union fine. So, the unifier is a data structure that tracks

elements which are split into one or more disjoint sets. And the union find has two primary operations. Find an union. A word find does is given an element, the union find will tell you what group that element belongs to and you Onion merges two groups together.

So if we have this example with magnets, suppose all these gray rectangles you see on the screen are magnets. And also suppose that the magnets have a very high attraction to each other, meaning they want to merge together to form some sort of configuration. So, if I label

all the magnets and give them numbers, and we start merging, the magnets have the highest attraction, first, we're going to merge six and eight together since the closest. So in our union find, we would say union six, and eight. And when we do a lookup on to find

out which groups six and eight belong to, they will belong to the blue group. Now, perhaps two, three, and three and four are highly attracted to each other, so they would form a group. So they would form the yellow group. And perhaps 10 1314, would also form a group.

And this keeps on going, and we unify magnets into groups. And perhaps we merge some magnets onto already existing groups. So we unify grey magnets, which is just a magnet in its own group, and add to an already existing group. But also we can unify groups of Magnus,

which are different colors, and we assign it an arbitrary color. So blue, so suddenly, everything in the yellow group went into the blue group. And now when we would do a lookup in our union find to determine which group say two, three or four. Now we'd say you're

in the blue group, and the union fine, does all this merging and finding in a very efficient manner, which is why it's so handy to have around. Now explaining currently how that works. We'll get into that in the later video. This is

just a motivating example. So where are other places that the union find is used? Well, we will. Well, we see the unifying again in carousels, minimum spanning tree algorithm. In another problem called grid percolation, where there's a bunch of dots on a grid, and

we're trying to see if there's a path from the bottom of the grid to the top of the grid, or vice versa, then the union find lets us do that efficiently by merging together paths. Also, similar kind of problem in network activity are two vertices in the graph connected to

each other through a series of edges. And also perhaps in some more advanced examples, like the least common ancestor in a tree, and also image processing. So what kind of complexity can we attribute to the union fight? The complexity is excellent. So it's construction

is linear time, which isn't actually bad at all, then the union find getcomponent. And check if connected operations all happened in what's called amortized constant time. So almost constant time, although not quite constant time. And finally, count components

where we can determine how many components are in our magnetic examples, how many different groups of nine that's we have. And we can do that in constant time, which is really, really great. Okay, let's talk about a really neat application of the Union find, which

is crew skills, minimum spanning tree algorithm. So you might be asking yourself, what is a minimum spanning tree? So if we're given some graph with some vertices and some edges, the minimum spanning tree is a subset of the edges which connects to all the vertices and does

so at a minimal cost. So, if this is our graph, with some edges and vertices, then a possible minimum spanning tree is the following and has edge weight 14 or total edge weight 14. Note that the minimum spanning tree is not necessarily unique. So if there is another

minimum spanning tree, it will also have a total weight of 14. So how does it work? So we can break it up into three steps essentially. So the Step is easy. Just take our edges and sort them by ascending edge edge weight. Next thing we want to do is we want to walk through

the sorted edges and compare the two nodes that the edge belongs to. And if the nodes already belong to the same group, then we want to ignore it because it will create a cycle in our minimum spanning tree, which we don't want. Otherwise, we want to unify

the, the two groups those nodes belong to. And keep going. I will keep doing this process until either we run out of edges, or all the vertices have been unified into one big group. And you'll soon see what I mean by a group, which is when our union find the structure

is going to come into play. So if this is our graph, then to run crystals algorithm on it, first, let's scale the edges and sort them. So on the left side, you see I have all the edges and their edge weights sort in ascending order. So next, we're gonna start

processing the edges one at a time, started starting with the top, so I two J. So I've highlighted the edge, it Jane, orange. And you can see that a connects nodes, i and j, i and j currently don't belong to any group. So I'm going to unify them together into group,

orange. Next is edge eight, he, so he don't belong to any group. So I'm going to unify them together into group purple. Next is CGI. So I belongs to group, orange. But see doesn't have a group yet. So see can go into group orange. All right, E to F, F doesn't belong

to a group. So F can go to group purple. Next, H and G, knee, neither age nor g belong to a group. So I'm going to say you guys belong to the red group. And next we have the Ruby. They also don't belong to a group. So give

them their own group, let's say group green. Alright, and now, I believe this is when things get interesting. Now, we're trying to connect C to J. But notice that C and j are a both belong to group orange. So we don't want to include that edge, because it's going to create

a cycle, so ignore it. And to check that they belong to the same group, we would use the find operation in our union fine to check what group they belong to. So this one, the unifying really comes into play. Next is edge did he So know that he belongs to purple,

and D belongs to group green. So now we want to merge them together because they don't belong to the same group. So either the purple groups wanted to become the green group, the green groups and the purple group. And it doesn't really matter, so that we would merge

them. And this is when the union operation in our union find becomes useful. It allows us to merge groups of colors together very efficiently. And that's the important note. Next edge would be d, h, h belongs to group red, and the purple. So merge the groups together,

let's say they both become group purple. Next up, we want to add edge, add, but add already belong to the same group. So that would create a cycle. So we don't want to include that edge. So skip. next rounds include edge BTC BTC belong to different groups. So merge the

two groups into one larger group. So we have found the minimum spanning tree using crystals minimum spanning tree algorithm. Pretty neat, right? So the underlying data structure, which allows us to do this is the union find it allows us to merge groups of colors together

efficiently, but also to find out which groups nodes belong to so that we don't create a cycle. So so that's crystals algorithm. It's super simple. Given that you know how the union find works. So I'm going to go into some detail in next video, explaining how

the Find and the union operations work internally, and how We can actually implement it in some useful way. Okay, so now we're going to talk about the union and find operations we can do on the union find, or the disjoint. Set. This is the video where I demystify how those

actually work internally. So to create our union find, the first thing we're going to do is we're going to construct a by ejection, or simply a mapping between our objects and the integers in the range zero inclusive to N non inclusive, assuming we have n elements.

So this step in general is actually not necessary. But it's going to allow us to create an array based unit find, which is very efficient, and also very easy to work with. So if we have some random objects, and we want to assign a mapping to them, then we can do so arbitrarily,

as long as each element maps to exactly one number. So that is my random by ejection. And we want to store these mappings perhaps in the hash table, so we can do a lookup on them and determine what everything is mapped to. Next, we're going to construct an array.

And each index is going to have an associated object. And this is possible through our mapping. So for instance, in the last slide, a was mapped to five, so slot five, or index five is going to be a slot.

So what you see in this picture is at the top is that array we just created, which contains our mapping. And in the center is just a visual representation of what's going on. The value in the array for each position is currently the index, which it is at. This is because

originally, every node is a root node, meaning it maps to itself. But as we perform the instructions on the left of unifying groups together, or objects together into groups, we're going to find that we're going to change the values in our array to map to other letters. And

specifically, the way we're going to do it is first some index i, in our array, index eyes parent is going to be whatever index is at position I. So for instance, if we want to unify C and K, we look at C and K. And we discover that C has a root node of four,

and K as of nine. So either C's won't come case parent, or K is going to see its parent. And I chose that case parent is going to be seat. So now at index nine, which is case position, I'm going to put a four, because I know that C is a four. So next, F and E

are going to do a similar type of thing. And I'm going to say that f is going to F parent is going to be E. So at F position, which is one I'm going to put a zero because he is zero. Similar thing for a and J. But here's where things get a bit more interesting. So

now we want to unify A and B. So if I look ay ay has a six in itself, but six is J. So I know that A's root node for group greens j and B is a single node because it's a self loop. And in general, I'm going to merge smaller components into the larger ones. So now, bees

are point to J, because the green groups root node was J. So I write mode C and D. So I find the root node of D which is the and find the root note of C which is C and I'm going to merge the smartcompany into the into the larger component, which is the orange group.

Now these want to be part of the orange group. Now I want to merge D and I. So similar thing happens. And I now points that C. Now, I want to merge L and F. So F's parent is E. So I'm going to merge L and B into the red group. Now I want to merge C and A. So this is an

interesting example. So I find a C's root node, which happens to be C, I find a root node which is J. Now, component, orange has four elements, big component, green only has three. So I'm going to merge the green component into the orange component. So now j is going

to point to C. So I want to unify A and B. So I do. So if I go up and follow the parent nodes until I reach a root node, as parents as Jay Jays, parents see, so I know that a belongs to the orange group. And if I do a similar thing with B, I also discovered that

B's parent is also C, which is the orange group. So I don't need to unify them, they're already unified together. So H and J, G, they currently don't have a group, so I'm going to arbitrarily merge them into a new group. So it'd be the blue group. So H and F. So

if I look, h is parent ID, G, and s parent is he the right component is larger, so I'm going to merge the blue group into it. And now since g was the root node, I make it point to E, which was also the root node. Now I want to

merge H and B. So H is root node is E, if we follow up the chain from H to G, D, and B's root node is C, because we go from B to J to C. So now since the orange component is larger than the red component, we're going to point the root of the red component to

the root of the orange component. So he now points to see. Okay, and note that in this example, I'm not using a technique called path compression. This is something we're going to look at in the next video, which is an optimization on the union find. To summarize,

if we want to find out which component a particular element maps to, what we have to do is find the root of that component by following all the parent nodes until we reach self loop or a node whose parent is itself and that will uniquely determine which component that

element belongs to. And to unify two components together, what we do is we find the root nodes of each component. And then if the root nodes are different, because if they're the same, then they belong to the same component already. So if they're different, make one of the root

nodes point to the become the parent of the other room. So just some remarks about this union find data structure. So in general, we don't really aren't union elements. Just because this would be inefficient as we'd have to update other children which point

to that note, we don't have access to those. But we could probably in theory, keep track of that. I just don't see any application currently. But there there might be also remarked that the number of components in our union find is going to be equal to the number of

root nodes remaining. Because each root node is responsible for a component and also remark that the number of root nodes never increases, that always decreases because all we do is unify components, so components only get bigger and bigger and bigger. Now we want to talk

about the complexity of the Union find. So I said in the first video that the US plane has an amortized time complexity. However, the implementation of this show you does not have an amortized time complexity. Not yet Not without the path compression, which is

something we're going to look at in the next video, which is what makes the human fine an absolute beast of it. structure, you must watch the next video. But just as an example, if we need to check, if H and B belong to the same group or a different group, it's

going to take five hops in the worst case, and while potentially much more, so H, we find the root node, which is C, and then we go from B, and then find the root node is also C. So this takes quite a few hops. Let's talk about path compression. Now, this operation

is really what makes the union find one of the most remarkable data structures, because it's how the union find gets to boast in its efficiency. So let's dive right in. But before we get started, it's critical that you watch the last video so that you understand how

the find in the Union operation work. Otherwise, you want to understand what's going on and what's up with path compression, and how we're going to get that really nice, amortized constant time.

Alright, suppose we have this hypothetical union find, I say hypothetical, because with path compression, I'm almost certain it's impossible to achieve a data structure, or a structure that looks like this. Nonetheless, it's a good example. So now suppose we want

to unify nodes, E and L. Or just unify groups, orange, and blue, but we have access to E and L. And that's what we're calling the unify operation on? Well, we would have two pointers that start on E and L. And where we would want to do is find the root node of e and

find the root node of L, and then get one of them to point to the other. But with path compression, we do that, but we're also going to do something else. So let's start by finding the parent note of E. So E's parent is D, and D is C, C to B, and B, A, and then eight

F. So we found the root node of E. But with path compression, here's what we're going to do. Now that we have a reference to the root node, we're going to make e point to the root node. And similarly DS are important to the root node and C and B, and a. So now

everything along the path got compressed, and now points to that root node. And in doing so, at every time we do a lookup, on either A, B, C, D, or E in constant time, we will be able to find out what the parent or the root node is for that component. Because we

immediately point to it, we don't have to traverse a sequence of other nodes. And we can do this because in a union find, we're always unifying things together and making them more and more compressed. We're never unusual unifying things, if you will. So if

we do the same thing for L, we find LS parent. So we traverse up all the parents until we find the root. And then we compress the path. So j points to G, I points to G, H points to G. And so we compress that path. But we also have found the parents now. So make one

point to the other. And we've unified both groups. So now the group that was once with E, and once with l have now been merged into one single group. But the only difference is we've compressed along the way as we've done this, and now it's so much more efficient.

Now let's have a look at another example. And this one, I want to compare and contrast, the regular union find operations where we're doing the last video to the last compression version, we now know. So if I run all those union instructions, this is what happened.

So it's the beginning all these pairs of components, and then executing the instructions on the right. And this is the final state of our union find and know that if I'm trying to determine what groups say a and j or n, then I have to traverse a whole bunch of different

nodes. So j goes, I use h h goes to eat. But now if I include path compression, let's see what happens. So I still have all those components. But now I as I execute the instruction on the right hand side, this is what happens. So I get the green group. But then, because

of path compression, that j merged into the H, so already that path is a little shorter. And then I keep executing more instructions. But as I'm doing it, the path gets compressed dynamically. So so I'm getting more and more compression. And even up to the very end.

So on the last example, we haven't even finish all the instructions, and we have reached the final state. But with path compression, as long as there's something compressed along our path, we get to compress the path along the way, pointing it to the root. So right

now, we only have one, root, B, E, and almost everything in constant time, points to E. So we do a lookup on any of our nodes. And we know that the route is easy. So we know the last component. And this structure

becomes very stable eventually, because of this path compression. This is why the union find with path compression is so efficient. Let's have a look at some of the Union find source code. So here's the link to the source code. And you can find it on my GitHub repository

github.com slash William fees, slash data structures. I also have a bunch of other data structures from past videos. And before we dive into the code, and make sure you watch the other videos pertaining to the union find, as I will be making some references to them.

Okay, let's dig in. Here we are inside the code. And I have a class called union find and see a few instance variables. So let's go over them. The first is size, just how many elements we have in our union find. There are at least two arrays, one called ID and

one called size. So the interest, while the more interesting was ID, and idea eyes, that array I talked about which at index i points to the parent node of AI. And if Id add AI is equal to AI, then we know that AI is a root node. So we're essentially keeping track

of all these like tree like structures right inside an array, which is practical. And also because we create a by ejection between our elements. And some numbers, this is how we're able to access them through this ID array. And just for convenience, I track the number

of components, that's sometimes some useful information you might want. So if you create a union find, well, you need to know how many elements are going to be inside your union find. And I make sure that we have a positive number of elements, otherwise I throw an exception.

Now go ahead and initialize some instance variables. And I initialize ID to equal i. So initially, everyone is a root node, and every component has a size of one. So find is pretty simple. It's given a a node, it finds which component it belongs to, and also

does path compression along the way. So if we're at p and want to find the root node of P, what we're going to do is we're going to find the root node using this one while loop. So we initialize a new variable called root to P. And then we loop until the root

is not equal to ID at root. So aka This is a root node or a self loop that we found and so we can stop and the root is stored in the variable called root. And then what we do is we do the path compression. This is what I talked about in the last video. So starting

back at p, we assign everything from idmp to equal the root and this is what compresses the path gives us that nice amortized time complexity, you can also do this recursively. But I don't like having the overhead and doing things iteratively you can be slightly faster.

Okay, so now, we have these simple methods, we can call. So if p and q are inside the same component, this will return true, because the root P and the root q will be equal. Otherwise, this will return false. And just calling find will do path compression. So even if we're

just checking if two components are connected, and it calls the find method, and we're compressing the path, same thing here, if we decide to find the component size, relative to some index p, then when we index into the size and call find, we'll find Well, we'll find

the root but at the same time, we'll also do path compression, which is nice. And I would just like to note that the the root nodes are the ones who will always contain the size because they're the ones that are found, well, she won't think about it like

at the end of the chain. Size just returns a number of components and our you can find disjoint, set components number components is pretty self explanatory. And the unifying method is the last interesting method. So this is the one that will unifies two components

together. So so first of all we do is we find what the root node for P is and what the root node for Q is. And if the root nodes are equal, then they're already in the same group, and we don't do anything. Otherwise, by convention, I just merge the smaller group into the larger

group. Although I know some people like to keep the theoretical largest path in a component, and then merge according to not and that may be slightly more efficient, but it's more work. So I just like to merge the smaller group into the larger group. And also, since

the roots are different, and we're emerging, we know that the number of components or sets must have decreased by one. So that's why at the bottom here, I, I say the number of components, subtract that by one, because we know we're gonna have one less component.

So this whole time, inside this class, I've been treating being q as integers and not as elements, like letters that I that we saw in our in the slides. And this is because by ejection, I would do a lookup to find out what maps to the element P and that should

give me an integer, and what maps to the element queue. And then I could use those with this union find data structure created, and turn everything into the realm of numbers instead of dealing with objects and having all this more complexity, it's much easier to have

an array based union find. You could also have a pointer based union find with node objects. But this is really nice, and it's a really clean implementation. All right, I want to start talking about a very exciting topic, and that is trees. And you'll soon

start to realize that there are tons and tons and tons of tree data structures. But today I want to focus on a very popular country and that is binary trees. And with binary trees, we must talk about binary search trees as well. So today's tutorial is going to focus

on binary trees and binary search trees where they're used and what they are. And then later tutorials, we're going to cover how to insert nodes into binary search trees remove nodes, and also do some of the more popular tree traversals which can apply to other general

trees. Also, not just binary trees. Okay. So I'm going to give you guys a quick crash course on trees before we get started. So we say a tree is an undirected graph, which can satisfy either of the following definitions, there are actually multiple definitions, but

these are the most popular ones. So trees non directed graph, which is connected and a cyclic, a cyclic means there are no cycles. Another definition is we have n nodes, but we have n minus one edges. And lastly, for any two vertices, there's only one path between

those two vertices, you can have two different paths, they would imply that we don't have a tree because there's another route to get to another node. And so we'd have a cycle. Okay, and context is trees, we can have something called a rooted tree, which is the topmost

node of our tree, you can think of it that way. And if you're trying to route the tree, and you don't have a route yet, it doesn't matter which node you pick, to route the tree, because any node you pick can become the root node, think of it as picking up the tree by

that node. And suddenly, it's the new root. We have something called are the concept of child and parent nodes. So child node is a node that extends from another node. Think of it as going down or it's an A parent node is the inverse of this. So you're going up

towards the root. So we have an interesting question, and that is, what is the parent of the root node? The answer is that the root node has no parent, although sometimes it may be useful to say that the parent of the root node is itself. And we see this often

when programming, for instance, a file system, tree has this property. So if I open up the command line, I'm in some directory, so I can say pwd at the current directory. So I'm somewhere in the file system tree. And if I want to go up to my parent, I can say CD

dot dot slash, and now I'm up in another directory, or in to the parent directory. And I can keep doing this and going up and up in the file system tree directory system. But if I go directly to the root node, which is slash, I see that I'm in the folder slash, so the

very top at the root of the directory, and I say CD dot, dot, then, if I check out where I am, I'm again at the root. So in this context, for a file system, the parent of the root is the root. Pretty cool. So just as an example, if we pick the node zero, and has two children,

three and two and a parent four, we also have the concept of something called a leaf node, this a node which has no children, and these have been highlighted in orange. So they're just at the very bottom of your tree. Think of it that way. And there's also another term,

which is sub tree, this is the tree entirely contained within an under tree. And we usually use triangles to denote sub trees. It's possible for a sub tree to consist of only a single node, so that's fine. So if this so tree with that circle node being the root, and we pick

particular sub tree and look what's inside of it, then we get another tree, which contains nodes and more sub trees. Then we pick another sub tree, look with inside of it, and then we get another tree. And eventually, we're going to hit the bottom. So now we can pose

the question, what is a binary tree? And this is this simple. This is a tree in which every node has at most, two children. So both those trees below are binary trees, because they have at most two children. You can see that the tree on the right, eight has one child,

and that's fine, because the criteria is at most two. Now we're going to play a game. I'm going to give you some various structures, and you're going to have to guess whether it is a binary tree or not. So is this a binary tree? Yes. Yes, it is every node has at most

two children. How about this one? No, you can see that seven has three children. So it's not a binary tree. How about this one? let you guys think about it a bit more. Yes, this is a binary tree. It may be a degenerate one, but it's still a binary tree. Alright,

let's move on to binary search trees. So what is a binary search tree? Well, first of all, it's a binary tree. But Furthermore, it also satisfies what's called the binary search tree invariant. And that is that the less left subtree has smaller elements than the

value of the current node. And the right subtree has larger elements than that of the current node. So below are a few binary search trees. We're going to play the same type of game, and I'm going to give you some trees, and you're going to have to guess whether they're

binary search trees or not. What about this structure? And this one, we could say it depends on whether you want to allow duplicate values inside your tree. It so happens that binary search tree operations allow for duplicate values. There's nothing wrong with that. But

most of the time, we're only interested in having unique values inside our tree. So this particular tree depends on what your definition of a binary search tree is. How about this? tree? Yes, this is a binary search tree. How about this tree? Notice I've only changed

the elements within the tree. Yes, this is also a binary search tree. We're not limited to only having numbers within our binary search tree, we can place any type of data which is comparable and can be ordered. How about this tree? No, this is not a binary search

tree. And the reason is the the node nine is in the wrong position. When we would be inserting nine, we would have to place it in the right subtree of eight because nine is larger than eight so belongs in its right subtree. How about this structure? This structure

isn't even a tree actually, because it contains a cycle. And the requirement to be a binary search tree is that you must be a tree. And this last one, I'm going to give you a bit more time to look at this one. Because it's not a regular type of structure you might

think of as a binary search tree. And the answer is yes, this structure does satisfy the binary search tree invariant that every right subtree contains larger elements. You will you'll see that that is true. And also every left subtree that contains smaller elements.

It doesn't look like a tree, but it satisfies our definitions of a tree and a binary search tree. Okay, so we've been talking about binary trees, binary search trees, where are they used? Why are they useful? So in particular, binary search trees are used in many implementations

of abstract data types for sets, and maps and so on. They're also used to implement balanced binary search trees, which we'll probably get to in a later video. Can you see binary search, or sorry, binary trees in binary heaps? We've already seen this in

priority queues when we're making a binary heap. But we also see binary trees and things like syntax trees, so you're parsing an arithmetic expression, then you place it in an abstract syntax tree. And then you can simplify expression. compilers and calculators use this to evaluate

expressions. So wherever you punch in your calculator gets person to binary tree and evaluated. And lastly, I just threw in a trip, which is another type of probabilistic data structure. So now let's look at the complexity of these binary search trees because they

looked very interesting and also very useful. And indeed they are. So in the average case, when you're just given some random data, the time complexity is growing. Be logarithmic, which is really good. So if you're inserting

nodes, deleting nodes, removing nodes searching for a value tree, whatever, the average time complexity is going to be the logarithmic. And these binary trees, or binary search trees are very easy to implement. So this is really good. However, in the worst case, if your

tree and D generates to being a line, then we can have some linear behavior going on, which is really bad. So there's some trade offs. If you want to use just a pure binary search tree, that it's going to be easy to implement. And on average, it's going to have

this logarithmic behavior. But in the worst case, you might be looking at some linear stuff, which is not so good. Okay, let's have a look at how to insert some elements into a binary search tree. So let's dive right in. So first, to add elements to our binary

search tree, we need to make sure that the elements we're adding are actually comparable, meaning that we can order them in some way inside the tree. Meaning at every step, we know whether we need to place the element in the left subtree or the right subtree.

And we're going to encounter essentially four cases. So when inserting an element, we want to compare the value to the value of the current node we're considering to do one of the following things. Either, we're going to recurse down the left subtree, because our element is smaller

than the current element, or we're going to recurse down the right subtree because our element is greater than the current element. Or it might be the case that the current element has the same value as the one we're considering. And so we need to handle duplicate values,

if we're deciding to add duplicate values to a tree or just ignoring that. And lastly, we have the case that we've hit a null node, in which case it's time to create a new node and insert it in our tree. Let's look at some animation now. So on the left, I have a bunch

of insert instructions. So we have all these values we want to insert into our binary search tree. And currently the search tree or the binary search tree is empty. So first, we want to insert seven. So seven becomes the root of the tree, because it's the first note.

Next, we want to insert 20. So 20 is greater than seven, so insert it to the right. Next we want insert five. So we always start at the root when we're inserting, and that's an important point. So you start at the root, and then you move your way down the tree to

figure out where you want to insert the node. So we start at the root, and then we're like, oh, five is less than seven. So we're going to insert it to the left. Now 15, so the route go to the right, because 15 is greater than seven, then to the left ps 15 is less than

20 at 10. Now four, so four is less than seven, move left, four is less than five, move left, create the new node. Now we have four again. So let's see what happens here. So seven moved to the left and moved to the left. Now we've encountered a value that already exists in

our tree. So as I said before, if your tree supports duplicate values, now's the time to add another node. And you would either pick by convention if you want it on the left or on the right. Otherwise, you'd do nothing. And I'm going to choose to do nothing. Insert

33. So start at the root, go to the right, because 33 is greater, go to the right again. Now insert two, so two smaller than everything in our tree, so it would go all the way to the left. Now try and see where 25 would go. So 25 simply go to the right, then we're going

to go to the right again, because it's greater than 20. But we're going to go left now because it's less than 33. And finally sex so once left, once right, and we've inserted everything into our binary

search tree. So on average, the insertion time is going to be logarithmic. But in the worst case, this behavior could degrade to linear time. Let's have a look at that. So if our instructions are the following insert 12345, and six. So we start at one, then go

and insert two sets to the right. Okay, now let's insert three, well, three is greater than everything. So I have to place the right again, how about four, okay, four is also greater than everything. Oh, looks like we're creating this line now. And now six, six is

still greater than everything. So as you can see, this type of linear behavior is really bad. And we don't want to create lines like this. Because if we want to query where six is in the tree, or if we want to remove five, or do anything, are buying your surgery, first