All language subtitles for Data-Structures-Easy-to-Advanced-Course-Full-Tutorial-from-a-Google-Engineer_en

In these first few videos, I want to lay the\n

need throughout these video tutorials. Let's\n

data structure? one definition that I really\n

data so that it can be used efficiently. And\n

a way of organizing data in some fashion so\n

or perhaps even updated quickly and easily.\n

Well, they are essential ingredients in creating\n

reason might be that they help us manage and\n

this last point, is more of my own making.\n

to understand. As a side note, one of the\n

bad mediocre to excellent programmers is that\n

fundamentally understand how and when to use\n

they're trying to finish. data structures\n

okay product and an outstanding one. It's\n

student is required to take a course in data\n

begin talking about data structures that we\n

structures. What I'm talking about is the\n

an abstracted type and how does it differ\n

that an abstract data type is an abstraction\n

interface to which that data structure must\n

a specific data structure should be implemented,\n

example I like to give is to suppose that\n

to get from point A to point B. Well, as we\n

to get from one place to another. So which\n

transportation might be walking or biking,\n

specific modes of transportation would be\n

We want to get from one place to another through\n

abstract data type. How did we do that? Exactly?\n

some examples of abstract data types on the\n

on the right hand side. As you can see, a\n

have a dynamic array or a linked list. They\n

indexing elements in the list. Next, we have\n

themselves can be implemented in a variety\n

for a queue, I put a stack based queue because\n

using only stacks. This may not be the most\n

it does work and it is possible. The point\n

how a data structure should behave, and what\n

surrounding how those methods are implemented.\n

data types, we need to have a quick look at\n

to understand the performance that our data\n

we often find ourselves asking the same two\n

is, how much time does this algorithm need\n

algorithm need for my computation. So, if\n

to finish, then it's no good. Similarly, if\n

a space equal to the sum of all the bytes\n

your algorithm is also useless. So just standardize\n

much space is required for an algorithm to\n

invented big O notation, amongst other things\n

we're interested in Big O because it tells\n

cares about the worst case. So if your algorithm\n

possible arrangement of numbers for your particular\n

suppose you have an unordered list of unique\n

seven, or the position where seven occurs\n

seven, that is at the beginning. Or in the\n

very last element of the list. for that particular\n

with respect to the number of elements in\n

every single element until you find seven.\n

just consider the worst possible amount of\n

that particular input. There's also the fact\n

when your input becomes arbitrarily large.\n

the input is small. For this reason, you'll\n

multiplicative factors. So in our big O notation,\n

when I say n, n is usually always want to\n

there's always going to be some limitation\n

a one wrapped around a big O. If your algorithm\n

we say that's big O of a log event. If it's\n

quadratic time or cubic time, then we say\n

Usually, this is going to be something like\n

than one to the n. And then we also have n\n

these like square root of n log log of n,\n

any mathematical expression containing n can\n

valid. Now, we want to talk about some properties\n

in the last two slides, Big O only really\n

really big. So we're not interested when n\nis small, only

what happens when n goes to infinity. So this\n

The first that we can simply remove constant\n

if you're adding a constant to infinity, well,\n

a constant by infinity, yeah, that's still\n

of course, this is all theoretical. In the\n

billion, probably, that's going to have a\n

However, let us look at a function f, which\n

f of n is seven log of n cubed plus 15 n squared\n

of n is just n cubed, because n cubed is the\n

look at some concrete examples of how big\n

constant time with respect to the input size,\n

So on the left, when we're just adding or\n

constant time. And on the right, okay, we're\n

depend on n. So it runs also in a constant\n

arbitrarily large, well, that loop is still\n

Now let's look at a linear example. So both\n

linear time with respect to the input size,\n

So on the left, we're incrementing, the counter\n

clearly, when we wrap this in a big go get\n

complicated, we're not incrementing by one,\n

to finish that loop three times faster. So\n

is two algorithms that run in quadratic time.\n

at times. So n times as big O of n squared.\n

zero with an eye. So pause the video and try\n

squared. Okay, let's go over the solution.\n

first loop isn't as important. So since I\n

is going to be directly related to what AI\n

loop. So if we fix AI to be zero, we do n\n

If we fix it, too, we do n minus two work\n

what is n plus n minus one plus n minus two\n

a well known identity, and turns out to be\n

wrap this in a big O, we split our equation,\n

Now let's look at perhaps a more complicated\n

how do we ever get these log Eurythmics or\n

a classic algorithm of doing a binary search,\n

So what this algorithm does is it starts by\n

in one at the very end of the array, then\n

if the value we're looking for was found at\n

or not, if it has found it, it stops. Otherwise,\n

either the high or the low pointer. remark\n

half of the array, each iteration. So very,\n

range check. So if you do the math, the worst\n

N iterations, meaning that the binary search\n

a very powerful algorithm. Here's a slightly\n

notice that there is an outer loop with a\n

that there are two inner loops, one that does\n

work. So the rule we use to determine the\n

loops on different levels and add those that\n

using the rule above, we can see that it takes\n

n plus two n for both inner loop Which gives\n

All right, so this next one looks very similar,\n

outer loop with AI, we have AI going from\n

on the outside. But we have to multiply that\n

j goes from 10, to 50. So that does 40 loops\n

the amount of work. Plus however, the second\n

J equals j plus two, so it's accelerated a\n

a little faster. So we're gonna get on the\n

we have to multiply that by three n. So we\n

is going to give us big of enter the force,\n

in our function, f of n. For some other classic\n

the subsets of a set, that takes an exponential\n

N subsets, finding all permutations of a string\n

one is merge sort. So we have n times log\n

iterate over all the cells of an array of\n

right, let's talk about arrays, probably the\n

of two in the array videos. The reason the\n

a fundamental building block for all other\n

with arrays and pointers alone, I'm pretty\n

structure. So an outline for today's video.\n

about arrays and answer some fundamental questions\n

Next, I will explain the basic structure of\n

able to perform on them. Lastly, we will go\n

look at some source code on how to construct\n

discussion and examples. So what is a static\n

containing elements, which are indexable,\n

n minus one also inclusive. So a follow up\n

So answer this is this means that each slot\n

a number. Furthermore, I would like to add\n

chunks of memory. Meaning that your chunk\n

cheese with a bunch of holes and gaps. It's\n

in your static array. Okay, so when and where\n

everywhere, absolutely everywhere. It's hard\n

fact, here are a few places you may or may\n

the first simple example is to temporarily\n

you're probably familiar with. Next is that\n

from an input or an output stream. Suppose\n

that you need to process but that file is\n

we use a buffer to read small chunks of the\n

a time. And so eventually we're able to read\n

as lookup tables because of their indexing\n

retrieve data from the lookup table if you\n

and at what offset. Next, we also use arrays\n

that only allows one return value.

So the hack we use then is to return a pointer\n

all the return values that we want. This last\n

are heavily used the programming technique\n

to cache already computed subproblems. So\n

problem, or the coin change problem. All right,\n

access time for static array and a dynamic\n

arrays are indexable. Searching, however,\n

we potentially have to traverse all the elements\n

the element you're looking for does not exist.\n

array doesn't really make sense. The static\n

grow larger or smaller. When inserting with\n

linear time, because you potentially have\n

recopy all the elements into the new static\n

a dynamic array using static arrays. However,\n

seem a little strange? Well, when we append\n

the internal static array containing all those\n

appending becomes constant time. deletions\n

are linear, you have to shift all of the elements\n

into your static array. Okay, so we have a\n

a contains the values 4412 minus 517 6039\n

but this is not a requirement of an array.\n

has index position zero in the array, not\n

science students, you have no idea. The confusing\n

is one base to work computer science is one.\n

the values 4412 minus 517 6039, and 100. Currently,\n

is not at all a requirement of the array.\n

is indexed, or positioned at index of zero\n

a lot of intro computer science students.\n

mathematics is one based while computer science\n

But Worst of all, is quantum computing. I\n

during my undergrad, and the field is a mess.\n

scientists and physicists all at the same\n

Anyways, back to arrays. I should also note\n

for each loop something that's offered in\n

you to explicitly reference the indices of\n

internally, behind the scenes, the notation\n

array A square bracket zero, close square\n

is equal to the value 44. Similarly, a position\n

But a index nine is out of bounds. And our\n

in C, it doesn't always throw an exception,\n

zero to B minus one that happens if we assign\n

be 25, let's look at operations on dynamic\n

in size as needed. So the dynamic array can\n

can do but unlike the static array, it grows\n

have a containing 34, and four, there, if\n

end. If we add 34, again, then it will add\n

So you see here, our dynamic array shrink\n

talked about this a little bit. But how do\n

the answer is typically this is done with\n

of course. So first, we create a stack if\n

nine zero. So as we add elements, we add elements\n

of the number of elements added. Once, we\n

of our internal static array, what we can\n

elements into this new static array, and add\n

an example. So suppose we create a dynamic\n

we begin adding elements to it. So the little\n

for an empty position. Okay, so we add seven,\n

fine. But once we add three, it doesn't fit\n

the size of the array, copy all the elements\n

12, everything's still okay, we're doing good.\n

resize again. So double the size of the container,\n

array, and then finish off by adding five.\n

issues. All right, time to look at the dynamic\n

in the array series. So the source code for\n

github.com, slash my username slash data dash\n

video so you know what's going on with this\n

in the array class. So I've designed an array\n

type of data we want put in this array, that's\n

that we care about our, which is our internal\nstatic array.

which is the length the user thinks the array\n

array, because sometimes our array might have\n

the user that there's extra free slots that\n

So there's two constructors. The first one\n

The other one you give it a capacity, the\n

or equal to zero. And then we finish Why's\n

I put this suppress warnings and unchecked\n

So here are two simple methods size, get the\n

empty, pretty self explanatory. Similarly\n

if we want the value or set it if we want\n

be doing a bounds check for both of these,\n

we just remove all the data in our array and\n

the Add method where things actually get a\n

plus one is greater than or equal to the capacity,\n

I'm resizing is I'm doubling the size of the\n

size, but I've decided that doubling the size\n

I have to create a new array with the new\n

this line or these lines are doing, it's copying\n

then it sets the old array to be the new array.\n

into our right. So this remove AZ method will\n

First, we check if the index is valid. If\n

otherwise, grab the data at the Remove index.\n

one. Now copy everything into the new array

for when it's at that remove index. Now I'm\n

decided to do the following maintain two indices\n

when i is equal to the Remove index, then\n

temporarily and using j to lag behind, if\n

So I guess pretty clever overall. And then\n

generated. Reset the capacity and return the\n

remove, we scan through the array. If we find\n

the index and return true otherwise return\n

it return I otherwise return minus one. Contains\n

one. All right, this next one, I return an\n

us to iterate over the array providing an\n

two methods. And this is has next. So there\n

is less than the length of the array. I should\n

here, just in case someone decides to change\n

it might add that later might not.

there's the next method, which just returns\n

the iterator. Okay, and lastly is the to string\n

Nothing too complicated. Alright, so this\n

a dynamic array. If you look at Java's ArrayList\n

we're going to talk about singly and doubly\n

out there. This is part one of two and the\n

code on how to implement a doubly linked list.\n

we're going to answer some basic questions\n

namely, what are they and where are they used.\n

linked lists, so everyone knows what I mean\n

the tail of the weight class. Then last in\n

and cons of using singly and doubly linked\n

from both singly and doubly linked lists as\n

discussion. So what is the link list linked\n

data which point to other nodes also containing\n

list containing some arbitrary data. Notice\n

node. Also notice that the last node points\n

always has a null reference to the next note,\n

slides. Okay, so where are linked lists use.\n

actually in the abstract data type implementation\n

great time complexity for adding and removing\n

like circular lists, making the pointer of\n

linked lists are used to model repeating events\n

on a bunch of elements or representing corners\n

linked lists can also be used to model real\n

that could be useful. And moving on some more\n

lists and hash table separate chaining, and\n

to those in a later video. Okay, a bit of\n

thing you need to know when creating a linked\n

to the head of the link lists. This is because\n

our list. We give a name to the last element\n

tail of the list. Then there are also the\n

pointers are also sometimes called references.\n

You should also know that the nodes themselves\n

when actually implemented. We'll get to this\n

versus doubly linked lists, sort of concerning\n

are two types, singly linked and doubly length.\n

to the next node, while doubly linked lists\n

but also to the previous node, which makes\n

say we cannot have triple or quadruple the\n

place additional pointers, pros and cons of\n

Between picking a singly and a doubly linked\n

linked lists we observed that uses less memory.\n

up a lot of memory. If you're running on a\n

on a 32 bit machine four bytes each. So having\n

pointer for each node, hence, twice as much\n

you cannot access previous elements because\n

to traverse from the head of a linked lists\n

it. Now concerning doubly linked lists with\n

we can easily traverse the list backwards,\n

list. Also having a reference to know Do you\n

time and patch the hole you just created.\n

previous and an ex notes, this is something\n

would leave the list severed into a downside\n

use twice as much memory. Okay, let's go into\n

create linked lists and remove elements from\n

list. So here is a singly linked list. I've\n

we want to insert 11. At the third position\n

an example. So the first thing we do is we\n

This is almost always the first step in all\n

to do is seek up to but not including the\n

and we advanced our traverser pointers, setting\n

23. And now we're actually ready already where\n

we create the next node, that's the green\nnode 11.

And we make 11 elevens. Next pointer, point\n

is next pointer to be 11. Remember, we have\n

a reference to it with the traverser. Okay,\n

that we've correctly inserted 11 at the right\n

time to insert with a doubly linked list.\n

flying around. But it's the exact same concept.\n

only has pointers to the next node, but also\n

those in the insertion phase. Okay, create\n

the head is, and advance it until you are\n

advanced the traversal by one and now we're\n

let's create the new node which is node 11.\n

Also point leptons previous pointer to be\n

traverser. How we make sevens previous pointer\n

to 11. And the last step, make 20 threes next\n

go forwards from 23 to 11. So in total remarked\n

we've flattened out the list, you can see\n

All right now how to remove elements from\n

remove the node with a value nine. How do\n

use is not to use one pointer but two, you\n

to show you how it is done by using two. So\n

for traverser one in Traverse e two respectively.\n

or two points to the heads. next node. Now\n

we find the node we want to remove while also\n

nine. So this is the stopping point. I'm going\n

to remove so we can deallocate its memory\n

traffic to to the next node Note nine has\n

this will that at this point, node nine is\n

for the visual effect. Okay, so now set trav\n

And now is an appropriate time to remove the\n

it and their temp has been deallocated. Make\n

memory leaks. This is especially important\n

where you manage your memory. Now you can\n

list is shorter. Okay, now for the last bit\n

nodes from a doubly linked list, which is\n

from singly linked lists. The idea is the\n

But this time, we only need one pointer. I\n

node is singly linked list has a reference\n

maintain it like we did with the singly linked\nlist.

So let's start travel at the very beginning\n

reached nine. And we want to remove it from\n

be equal to 15 with access to four and 15\n

pointer respectively. Similarly set 15 previous\n

now read, meaning it is ready to be removed.\n

out the doubly linked lists, we see that it\n

complexity analysis on linked lists how good\n

we have singly linked lists. And on the right\n

in a linked list is linear in the worst case,\n

not there, we have to traverse all of the\n

is constant time, because we always maintain\n

hence we can add it in constant time. Similarly\n

linked lists, and a doubly linked list is\n

a reference to it, so we can just move it\n

removing from the tail is another story. It\n

a singly linked list. Can you think of Why?\n

tail in a singly linked lists, we can remove\n

value of what the tail is. So we had to seek\n

new tail is equal to. W linked list however,\n

a pointer to the previous node. So we can\n

finally, removing somewhere in the middle\n

we would need to seek through n minus one\n

to look at some double e linked list source\n

list series. So the link for the source code\n

Williams he's a slash data dash structures.\n

source code helpful so that others may also\n

first part of the linkless series before continuing.\n

at the implementation of a doubly linked list\n

a Few instance variables. So we are keeping\n

as what the head and the tail currently are.\n

meaning link list is empty. Furthermore, we\n

excessively, because it contains the data\n

and next pointers for each node since this\n

for the node, namely the data and the previous\n

both otherwise, we can't do much. So his first\n

list, it does so in linear time by going through\n

time deallocates them by setting them equal\n

head, we loop while the traverser is likely\n

and then we do our deallocation business.\n

and reset the head and tail. Perfect. These\n

get the size and check if the size of our\n

a public method to add an element by default,\n

list or at the tail. But I also support adding\n

do we do this, if this is the first element,\n

and the tail to be equal to the new node,\n

and next pointers set to No. Otherwise, if\n

previous pointer is equal to this new node.\n

to be whatever hands previous is. So we backup\n

forget to increment the size. A very similar\n

length list, except we're moving the tail\npointer around.

move to peak. So peaking is just looking at\n

linked list or at the end of the linked list.\n

is empty, because doesn't make sense to peek\n

more complex method, which is remove first.\n

the linked list. So we can't do much if the\n

we extract the data at the head, and then\n

the size by one. So if the list is empty,\n

the head and the tail are now No. Otherwise,\n

that we just removed. This is especially important\n

delete pointers, then at the end, we return\n

except we're using the tail this time to remove\n

head. Okay, and here's a generic method to\n

this to private because the node class itself\n

to the node. That's just something we're using\n

to manage the list. So if the node that we're\n

detect that and call our methods either remove\n

somewhere in the middle of linked list. And\n

the to our current node equal to each other.\n

node and And of course, don't forget to clean\n

have to temporarily store the data. Of course,\n

deleted the node and the data is already gone.\n

particular index and our linked list. Yes,\n

not explicitly indexed, we can pretend that\n

valid, otherwise throw an illegal argument\n

bit smarter than just naively going through\n

from the front of the linked list to find\n

the index is closer to the front or to the\n

So for the Remove method, we want to be able\n

list, which is object. So we're going to also\n

someone decided that the value of the node\n

special case. Otherwise, we traverse through\n

and then remove that node and return true\n

we want to remove. Otherwise, we return false\n

for the element we want to remove, we use\n

the element. If so, remove that node and return\ntrue.

here we have a related method which is index\n

remove value, but get whatever index this\n

null. So even if our values No, we'll just\n

So again, first link list. Otherwise, search\n

the index as we go. We can use the index of\n

is contained within a linked list because\n

found. Something that's useful sometimes is\n

is also trivial to implement, just start a\n

until you reach the end. Notice I'm not checking\n

you want to, it's pretty easy to do that.\n

the to string method to print a string or\n

linked list. May I begin by saying that the\n

data structure, one of my favorites. In fact,\n

Part Two will consist of looking at a stack\n

source code for how a stack is implemented\n

that we'll be covering in this video as well\n

about what is a stack and where is it used?\n

of how to solve problems using stacks. Afterwards,\n

internally and the time complexity associated\n

some source code. Moving on to the discussion\n

is a one ended linear data structure which\n

primary operations, namely, push and pop.\n

constructed. There is one data member again\n

data member getting added to the stack. Notice\n

block at the top The stack. This is because\n

added to the top of the pile. This behavior\n

out. Let's look at a more detailed example\n

and removed from a stack. So let's walk through\n

on what we need to add and remove to the stack.\n

the top element from the stack, which is Apple.\n

onto the stack. So we add onion to the top\n

celery onto the stack. Next is watermelon,\n

says to pop so we remove the element at the\n

just added. The next operation also a pop.\n

is celery. And last operation push lettuce\n

top of the stack. So as you can see, everything\n

have access to anything else but the top of\n

a stack works. So when in Where is a stack\n

everywhere. They're using text editors to\n

backwards or forwards. They use some compilers\n

matching braces, and in the right order. stacks\n

books, plates, and even games like the Tower\n

stacks are also used behind the scenes to\n

function calls. When a function returns it\n

and rewinds to the next function that is on\n

stacks all the time in programming and never\n

stacks for us to perform a depth first search\n

manually by maintaining your own stack, or\n

stacks as we have just discussed complexity\n

assumes that you implemented a stack using\n

because we have a reference at the top of\n

goes for popping and peeking. Searching however,\n

searching for isn't necessarily at the top\n

elements in the stack, hence require a linear\n

of a problem using stacks problem. So given\n

round brackets square brackets curly brackets\n

So analyzing examples below to understand\n

ones are invalid. So before I show you the\n

in this first example, consider the following\n

string from left to right, I will be displaying\n

bracket. So let's begin. For every left bracket\n

So this is the left square bracket that I\n

this one on the stack. Same goes for the next\n

this is a right square bracket. So we encountered\n

checks. First we check if the stack is empty.\n

if there are still things in the stack that\n

is equal to the reversed current bracket.\n

reversed bracket. So we are good. Next is\n

empty. No, it isn't. So we're good. Is the\n

bracket? Yes, it is. So let's keep going around\n

A right bracket. Is the stack empty? No. Okay,\n

equal to the reverse bracket? Yes. Okay. So\n

stack empty? No. Okay, good. And there's the\n

bracket. Yes. Okay, good. And now we're done\n

the stack is empty. Now. Why is that? Well,\n

sequence were left brackets, they would still\n

So we can conclude that this bracket sequence\n

example with another bracket sequence. So\n

bracket is a left bracket, so we push onto\n

bracket. So we push onto the stack. This next\n

if the stack is empty. No, it's good. And\n

reverse bracket? Yes, it is. This next bracket\n

So we're good. And is the reverse bracket\n

No, it isn't. So this bracket sequence is\n

we just ran through. So if we let us be a\n

string, we can get the reverse bracket for\n

is a left bracket, push it on to the stack.\n

And if the element at the top of the stack\n

those conditions are true, then we return\n

is empty or not. And if it is empty, then\n

we do not. I want to take a moment and look\n

amongst mathematicians and computer scientists.\n

is played as follows. You start with a pile\n

the objective of the game is to move all the\n

this pile, and each move, you can move the\n

a restriction that no disk be placed on top\nof

a smaller desk. So we can think of each peg\n

top element in a peg and placing it on another\n

run. And you will see how each peg acts like\n

So you just saw how transferring elements\n

as popping a disk from one stack and pushing\n

the disk you're placing on top is smaller.\n

of three in the stack series. This is going\n

a stack. So those stacks are often implemented\n

sometimes double linked lists here We'll cover\n

linked list. Later on, and we will look at\n

using a doubly linked list. Okay, to begin\n

our link place, so we're going to point the\n

is initially empty. Then the trick to creating\n

the new elements before the head and not at\n

pointing in the correct direction when we\n

we will soon see, the next element however,\n

let's do that. To create a new node, adjust\n

then hook on the nodes next pointer to where\n

for five and also 13. Now let's have a look\n

just move the head pointer to the next node\n

the first node off the stack and set the nodes\n

up by the garbage collector if you're coding\n

references pointing to it. If you're in another\n

explicitly deallocate free memory yourself\n

Or you will get memory leaks. Getting a memory\n

kinds of memory leaks, especially if it's\n

reusing. So keep watching out for that not\n

that we will be covering. If you see in an\n

up my memory, please please point out to me,\n

so we can patch that. Okay, so we keep proceeding\n

pointer down to the next node. Pop again,\n

popping we've reached last note and the stack\n

in the stack series videos. Today we'll be\n

stack. So the source code can be found on\n

structures. Make sure you understood part\n

So you actually know how we implement a stack\n

video series, and the implementation of the\n

to you then please start this repository on\n

finding it as well. Here we are in the stack\n

Java programming language. So the first thing\n

variable of a length list. This is the linked\n

linked list provided by Java. This is a little\n

Java dot util that I will be using today,\n

videos, this is just for portability, in case\n

So we have two constructors, we can create\n

one initial element. This is occasionally\n

the stack. So to get to do that, we return\n

the elements of our stack easy. We also check\n

is zero. So this next one is just push so\n

append that element as the last element in\n

also pull element of the stack. So to do this,\n

then we throw an empty stack exception because\n

That doesn't make sense. Similarly, the same\n

top element of the stack is, if the stack\n

the last element of our list. And lastly,\n

to iterate through our stack. This iterator\n

supports concurrent modification errors. So\n

that was static. It's only like 50 lines of\n

one of the most useful data structures in\n

one of three in the Q series. So the outline\n

going to begin by talking about queues and\n

some complexity analysis concerning queues.\n

of n queuing and D queuing elements from a\n

very end in the last video. So a discussion\n

So below you can see an image of a queue.\n

that models a real world queue. Having two\n

and D queuing. So ever queue has a front and\n

back and remove through the front. Adding\n

n queuing. and removing elements from the\n

there's a bit of terminology surrounding queues\n

or when we refer to as queuing D queuing,\n

So and queuing is also called adding but also\n

we're talking about D queuing. So this is\n

queue. This is also called polling elements.\n

as removing an element from the queue. But\n

some ambiguity, did they mean removing from\n

the entire queue? Make note that if I say\n

from the front of the queue unless I say otherwise.\n

in detail. However, first, notice I have labeled\n

where I'm going to be in queueing and D queuing\n

instruction says in queue 12, so we add 12\n

the first element from the front of the queue,\n

we removed minus one from the front of the\n

dq, so remove the front element being 33.\n

So now that we know where a queue is, where\n

Well, a classic example of where cuneus gets\n

waiting in line at a movie theater or in the\n

ever been to say McDonald's, where all the\n

fried, the next person in line gets to order\n

also be really useful if you have a sequence\n

of say, the x most recent elements, while\n

your queue gets larger than x elements, just\n

in server management. So, suppose for a moment\n

for requests from people to use your website,\n

serve up to five people. But no more. If 12\n

you're not going to be able to process all\n

is you process the five that you're able to,\n

queue waiting to be served. And whenever you\n

next request, and then you start processing\n

While you're doing this, more requests come\n

add them to the end of the cube. queues are\n

first search traversal on a graph, which is\n

this example in the next video. All right\n

So as we're seeing, it's pretty obvious that\n

time. There's also another operation on a\n

peaking. peaking means that we're looking\n

removing it, the source or cost and time.\n

within the queue, is linear time since we\n

the elements. There's also element removal\n

or polling, but in actually removing an element\n

linear time, since we would have to scan through\n

this video, we're going to have a look at\n

search. And then we're going to look at the\n

and D queuing elements works. Okay, onto the\n

search is an operation we can do on the graph\n

what I mean, when I say graph, I mean a network\n

like that. But first, I should explain the\n

search. The objective is to start a node and\n

all the neighbors of the starting node, and\n

node you visited and then all the neighbors\n

so forth, expanding through all the neighbors\n

of the breadth first search as expanding the\n

as you go on. So let's begin our breadth first\n

node zero as yellow and put it in the frontier\n

visit all the neighbors of zero being one\n

then we resolve the neighbors of one and nine\n

seven, and visit all the neighbors of seven.\n

here, and now visit all the neighbors of the\nyellow nodes.

And now we're done our breadth first search\n

frontier. Notice that there's 12 that is the\n

island all by itself. So we are not able to\n

is fine. Suppose you want to actually code\n

done? Well, the idea is to use a cube. So\n

And then we mark the starting node as visited.\n

an element from our queue or D queuing. And\n

D queued if the neighbor has not been visited\n

to the queue. So now we have a way of processing\n

search order. Really, really useful, very,\n

now let's look at implementation of queues.\n

out that you can implement the queue abstract\n

the most popular methods are to either use\n

lists. If you're using an array, you have\n

array, if it's a dynamic array, then you'll\n

a singly linked list and the source code,\n

tuned for that. In a singly linked list, we're\n

So initially, they're both No. But as we n\n

so nothing really interesting is going on\n

can see that we're pushing the tail pointer\n

the tail pointer point to the next node. Now\n

the tail forward, we're going to be pushing\n

one, and then the element that was left over\n

user. So why don't we push the head pointer\n

so that it can be picked up by the garbage\n

in another programming language, which requires\n

yourself like C or c++, now's the time to\n

we're just pushing the head forward and forward\n

of elements, then remove them all then the\n

is where we started. All right, now it's time\n

So I implemented a queue and you can find\n

slash my user name slash data dash structures.\n

parts one and two from the Q series before\n

some source code for a queue. So this source\n

although you can probably translate it into\n

the first thing to remark is I have an instance\n

a Java's implementation of a doubly linked\n

as you'll see the queue and the stack implementations\n

constructors, one create just an empty queue.\n

a queue but with a first element. In fact,\n

we we might want to allow no elements. So\n

method is the size, it just gets the size\n

if the length list is empty. Those are both\n

method is the peak method, the peak method\n

the queue, but it will throw an error if your\n

when your queue is empty. Similarly, for poll,\n

the queue, but unlike peak will actually remove\n

down a little bit, I have offer which adds\n

I am allowing for no elements. So if you don't\n

throw an error or something. So the poll removed\n

to the back. So remove first and add last.\n

in case you want to be able to iterate through\n

and very simple implementation just under\n

Although there are faster ways of creating\n

The idea with arrays, especially static arrays,\n

that will be in your queue at any given time,\n

size and have pointers to the front and the\n

remove elements based on the relative position\n

where you're running off the edge of your\n

of the array and keep processing elements\n

maintain references to the next node, such\n

your homework is to create a static array\n

everything to do with priority queues from\n

And towards the end, we'll also have a look\n

queue stuff. We're also going to talk about\n

although not the same. So the outline for\n

start with the basics talking about what are\n

then we'll move on to some common operations\n

how we can turn min priority queues into max\n

analysis. And we'll talk about common ways\n

people think heaps are the only way we can\n

queues somehow are heaps, I want to dispel\n

some great detail about how to implement the\n

we'll look at methods of sinking and swimming\n

used to get and shuffle around elements in\n

explanation, I also go over how to pull and\n

let's get started. discussion and examples.\n

priority queue series. So what is a priority\n

type that operates similar to a normal queue\n

a certain priority. So elements with a higher\n

As a side note, I'd like to remark that priority\n

meaning that the data we insert into the priority\n

from least to greatest or raised lease. This\n

elements. Okay, let's go into an example.\n

inserted into a priority queue on the right,\n

such that we want to order them from least\n

higher priority than the bigger ones. So they\n

Suppose we have now a list of instructions.\n

the element that has the highest priority\n

works. So if I say Paul, then I remove the\n

to be one. Now I say add two, so we add two\n

of smallest elements in our priority queue,\n

Next, we add for all this smallest, this is\n

pull the rest. So as I pull the rest, I'm\n

priority queue. So it turns out that as we\n

sequence. This is a coincidence. Actually,\n

queue, we do not necessarily end up getting\n

that the next number that is removed from\n

that was currently in the priority queue.\n

is the next smallest number to remove? As\n

inside the priority queue and look and know\n

was going to return. But fundamentally, how\n

all the elements inside a priority queue before\n

be highly ineffective. Instead, it uses what\n

then is what is a heap? Usually I make up\n

one from wiki. A heap is a tree based data\n

also called the heap property. If a is a parent\n

to B for all nodes A and B in the heap. What\n

is always greater than or equal to the value\n

way around that the value of the parent node\n

child node for all nodes. This means we end\n

and min heaps. So max heaps are the one with\n

its children. And the min heap is the opposite.\n

heaps binary because every node has exactly\n

or no values I have not drawn in. So why are\n

underlying data structure for priority queues?\n

called heaps, although this isn't technically\n

is an abstract data type, meaning it can be\n

Okay, we're going to play a little game, I'm\n

need to tell me whether it is a heap or not.\n

to determine whether it's a heap or not, you\n

just going to give you a short moment here.\n

and this tree. So it's not a heap. Is this\n

it satisfies a heap invariant, and it is a\n

why we're called binomial heaps. Note that\n

can have any number of branches. On to our\n

a valid heap. Because even though this one\n

free to move around the visual representation\n

valid heap. How about this one? No, this structure\n

the cycles. All heaps must be trees. What\n

this one? Also heap because it satisfies the\n

than or equal to or greater than or equal\n

not onto the heap and because it does not\n

do change the root to be 10, then we can satisfy\n

Or rather sorry, a max heap. So when and where\n

of the most popular places we see priority\n

to fetch the next nodes we explore. priority\n

a behavior in which you need to dynamically\n

They're also used in Huffman encoding, which\n

Many best first search algorithms use priority\n

gain grab the next most promising node in\n

we also see priority queues in prims minimum\n

So it seems priority queues are really important,\n

is where we see them often. Okay, on to some\n

as a binary heap. To begin with, there exists\n

unordered array in linear time, we're not\n

cool. And it forms the basis for the sorting\n

rather removing pulling or removing an element\n

time, because you need to restore the heap\n

time. So peaking or seeing the value at the\n

is really nice. Adding an element to our heap\n

we possibly have to reshuffled heap by bubbling\n

Then there are a few more operations we can\n

which is not the root element. So the naive\n

do a linear scan to find the items position\n

is it can be extremely slow in some situations,\n

don't do this. And it's not a problem, which\n

lazy and do the linear scan solution. However,\n

time complexity, which I will go over later\n

series. So stay tuned for that this method\n

complexity to be logarithmic, which is super\n

much as you are adding. Now the naive method\n

heap is linear. Again, you just scan through\n

table, we can reduce this to be a constant\n

use the hash table implementation for the\n

The downside however, to using hash table\n

extra linear space factor. And it does add\n

your table a lot during swaps. Today, we're\n

into max priority queues. This is part two,\n

may already be asking yourself, why is it\n

priority queue into a max priority queue?\n

library, most programming languages, they\n

queue or a min priority queue. Usually it's\n

by the smallest element first, but sometimes\n

what we're programming. So how do we do this?\n

queue To another type. Well, a hack we can\n

in a priority queue must implement some sort

of comparable interface, which we can simply\n

heap. Let's look at some examples. Suppose\n

consisting of elements that are on the right\n

that min priority queue. So if x and y are\n

than or equal to y, then x will come out of\n

of this is x is greater than or equal to y.\n

all these elements are still in the priority\n

of x is less than or equal to y, just x greater\n

to y? Well, not for competitors. You see if\n

is negated, x should still equal y. So now\n

elements out of priority queue with our negated\n

it's the greatest. Next comes 11 753. And\n

to negate the number before you insert it\n

is a hack specific to numbers, but it's pretty\n

negate all the numbers inside a priority queue.\n

is the smallest so should come out first.\n

now we have to remake the data and we 13.\n

So really positive 11. And so on my seven,\n

then arena, get the value to get it out of\n

Okay, now let's look at my other examples\n

for strings, which sorts strings in lexicographic.\n

languages, then, let's call n Lex be the negation\n

two to be some non null strings. So below,\n

one if s one is less than s two Lexa graphically\n

one if s one is greater than s two lexicographically.\n

So just to break it down, ALEKS sorts strings,\n

in gaining legs so that longer strings appear\n

strings with letters at the end of the alphabet\n

the beginning of the alphabet, I think I said\n

he into a maxi beep. Let's look at a concrete\n

right to a prayer queue with the lexicographic\n

expect. First we get a because it's the shortest\n

closest to the start of the alphabet, then\n

and x x. So now let's do the same thing with\n

opposite sequence in reverse order.

And then we get x x x r x f, Zed mi N A. So\n

we're going to talk about adding elements\n

The priority queue series, we'll get to adding\n

there are some important terminology and concepts\n

prior to add elements effectively to our priority\n

a priority queue is to use some kind of heap.\n

which give us the best possible time complexity\n

a priority queue. However, I want to make\n

A priority queue is an abstract data type\n

should have. The heap just lets us actually\n

could use an unordered list to achieve the\n

But this would not give us the best possible\n

are many different types of heaps including\n

pairing heaps, and so on, so on. But for simplicity,\n

heap is a binary tree that supports the heap\n

exactly two children. So the following structure\n

property that every parent's value is greater\n

has exactly two children. Well, no, you may\n

leafs don't have children. Well, actually,\n

children in gray. But for simplicity, I won't\n

Okay. The next important bit of terminology,\n

tree property. The complete binary tree property\n

the last is completely filled, and that all\n

binary tree. As you will see, when we insert\n

row. As far left to meet this complete binary\n

tree property is very, very important, because\n

what the heap looks like, or what values are\n

the hollow circle that and the next one will\n

we fill up the row, at which point we need\n

is a very important. One last thing before\n

a binary heap, is we need to understand how\n

there is a canonical way of doing this, which\n

is a very convenient actually, because when\n

the insertion position is just the last position\n

way we can represent the heap, we can also\n

and recursively add and remove nodes as needed.\n

and also very, very fast. So on the left is\n

the position of each node in the array. And\n

as you read elements in the array from left\n

the heap, one layer at a time.

So if we're at no nine, which is index zero,\n

position one. And as I keep moving along,\n

the array going from left to right. So it's\n

interesting property of story, I'm binary\n

all the children and parent nodes. So suppose\n

left child is going to be at index two times\n

is going to be at two i plus two, this is\n

just subtract one. So suppose we have a node\n

its index is two. So by our formula, the left\n

two, plus one, or, or five. If we look at\n

look at the right child, we should expect\n

look in our array, this gives us the value\n

we need to manipulate the knowns now array\n

Part Five for the series, we will see that\n

All right. So now we want to know, how do\n

the heap invariant, because if we I noticed\n

heap property? Well, the binary heap is useless.\n

some instructions, which tell us what values\n

value is a one, which we can see, which should\n

with a min heap. But instead of inserting\n

put one at the bottom left of the tree in\n

and performance call bubbling up as my undergrad\n

swimming or even sifting up all really cool\n

one and the insertion position. But now we're\n

is less than seven, but one is found below\n

swap one and seven, like so. But now we're\n

one is a child of six, but one is less than\n

again, violation the property. So we swap,\n

be. And now the heap invariant to satisfy\n

whatever you want to call it. So the next\n

in the insertion position. And now, we need\n

13. Notice that we're no longer in violation\n

13, and 13 is less than 12. So 13 is actually\n

have to bubble up our elements that much.\n

zero and 10. Try seeing where these end up,\n

exercise. But I will keep going for now. So\n

the nodes, it's there, and we bubble it up\n

the property is satisfied. Next zero, my favorite\n

be at the top of the tree as you will see\n

So let us bubble up and like magic zeros at\n

numbers 10. So we put out an insertion position.\n

invariant, so we do nothing.

Today we're going to look at how to remove\n

Four or five in the priority queue series.\n

the underlying structure of the binary heap.

In general, with heaps we always want to remove\n

It's the one of the highest priority is the\n

Route, we call it polling, a special thing\n

to search for its index. Because in an array\n

zero. So when I say pull in red, we have the\n

one we're going to swap it with. So the note\n

the end of our array, which we also have its\n

one. And now, since 10 is at the top, well,\n

we need to make sure that the heap invariant\n

bubbling down now instead of bubbling up.\n

five and one, and we select the smallest,\n

go to one. So make sure you default, selecting\n

as you can see, 1010s children are two and\n

select the left node to break tight. And now\n

invariant is satisfied. Now we want to remove\n

element at the root. But 12 is not at the\n

remove 12. So what we do is we have to search\n

its position yet. So we start at one, and\n

until we find 12. So five is not 12, two is\n

found 12. And now we know where its position\n

to remove, and also swap it with the purple\n

them remove the 12. And now we're in violation\n

up three, until the heap invariant is satisfied.\n

so we can start. Now we want to remove three,\n

the tree. Three wasn't far it was just two\n

swap it with the last node in the tree. Drop\n

up or bubble down the value because you don't\n

last position is when you're swapping it in.\n

we already satisfy that heap invariant from\n

five was smaller, so we swapped it with five,\n

eight. And again, the heap invariants are\n

root node, red swap it, remove the one. And\n

is satisfied. Now we want to remove six. So\n

Okay, we have found six and do the swap. Remove\n

answer is neither the heap invariant is already\n

We got lucky. So from all this polling and\n

polling takes logarithmic time since we're\n

to find it. And also that removing a random\n

to actually find the index of that node we\n

if you're as dissatisfied with this linear\n

has to be a better way. And indeed there is.\n

this complexity to be logarithmic in the general\n

at how to remove nodes on my heap with the\n

need to make use of a hash table, a data structure\n

are about to get a little wild. I promise\n

later video. But right now, it's going to\n

we have a bunch of nodes scatter across our\n

a linear scan to find out where the node we\n

to do a lookup and figure that out. The way\n

is going to be mapped to the indexes found\n

node, just look up its index and started doing\n

sounds great, except for one caveat. What\n

the same value? What problems will that cause?\n

To begin with, let's talk about how we can\n

of mapping one value to one position, we will\n

can do this by maintaining a set or tree set\n

or key if you want maps to. So can I example.\n

has repeated values. Namely, we can see that\n

twice, 11 and 13. Once the low I have drawn\n

determine the index position of a node in\n

at index five, and the first to index zero.\n

value pairs. Notice that two is found in three\n

two positions, one and four, and so on. So\n

positions of the values in the tree. If notes\n

keep track of that. For example, if a bubble\n

movements, and where the swabs go to so we\n

we swap 13. And the last seven, for example,\n

where seven and 13 are in our table. And then\n

red for the seven and yellow for the 13. And\n

do a swap in the tree but also in the table.\n

We keep track of repeated values by maintaining\n

value was found out. But now let's ask a further\n

node in our heap, which node do we remove\n

our heap right here, there's three possible\n

The answer is no, it does not matter. As long\n

and that's the most important thing. So let's\n

but also of adding and pulling elements with\n

that hard, trust me. So first one, we want\n

bottom of the heap in the insertion position.\n

so we add three to our table long with its\n

Look at the index, tree and grade confirm\n

we need to make sure the heap invariant satisfied,\n

up three, the parent of three is 11, which\n

those two notes, I have highlighted the seven\n

in the heap and three in the index three,\n

those both in the tree and in the table. Awesome.\n

So do a similar thing. For the note above,\n

on the table. And now the bat invariants are\n

The next instruction is to remove to from\n

Well, as I said, it doesn't matter as long\n

If we remove the last two, we can immediately\n

But for learning purposes, I will simply remove\n

to be located at index zero. So we want to\n

we remove a note again, so we did a look up.\n

which was nice. And now we swap it with the\n

we remove the last node. Now we need to satisfy\n

11. So we look at 11 children, which happens\n

the one we're going to swap with. So swap\n

are still not in satisfaction of the human\n

into two smaller, so swap it with two. And\n

says the poll, so we get the value of the\n

of the two and bubble down 11. So as you can\n

but still doing the same operations. This\n

series. And we're going to have a look at\n

So if you want the source code, here's the\n

in the series, the priority queue is one of\n

124, so you can actually understand what's\n

Alright, here we are inside the source code.\n

types of elements I'm allowing inside my priority\n

talked about. So if they implement the comparable\n

inside our queue. So this is anything like\n

interface. So let's have a look at some of\n

size. So this is the number of elements currently\n

instance variable, which is the heat capacity.\n

That we have four elements which may be larger\n

heap. And we're going to be maintaining it\n

Next, for our logging of and removals, I'm\n

want to map an element to a tree set of integers.\n

our heap, which we can find this element T.\n

constructors for our priority queue. We can\n

I'm creating and initially empty priority\n

you to create a priority queue with a defined\n

because then we don't have to keep expanding\n

this. But also, even better, is if you know\n

your heap, you can actually construct the\n

called heapify, which I didn't talk about\n

useful. So So this just has all the usual\n

to the math and but also to the heap. And\n

at halfway through the heap size, and then\n

the elements. And you're like, Wait a second,\n

Well, yes, it is in the general case, but\n

a link to this paper appear just because the\n

it has this linear complexity. And if you\n

end up seeing that the complexity boils down\n

constantly say it's linear time. But in general,\n

If you're given a collection of elements,\n

would just use our add method to add the elements\n

log N bound. But definitely use the heapify\n

methods we have is empty, just returns true\n

clear. So when we clear the heap, we remove\n

also inside our map. So that's why he called\n

simple. peek, the first really useful method\n

queue. And if it's empty returns No. Otherwise,\n

our heap and return it because it's the root\nnode

Similar to pique, except that we're going\n

And we're also going to return it because\n

because we have a map with our elements, we\n

inside heap. And this reduces our complexity\n

through a linear scan through all elements\n

is remarkable. But you have a job in case\n

just wanted to do it. Just to show you guys\n

a lot of constant overhead and you may or\n

is quite a lot. And I usually don't really\n

it might not be entirely worth it. But it's\n

as you are removals then definitely worth\n

Add method. So, so this element, sorry, this\n

And that element cannot be no. So what we\n

less than capacity. Otherwise we have to expand\n

we add it to the map. So we keep track of\n

we have to swim. I know Rob because we add\n

had to, like adjust where it goes inside our\n

called less is is a helper method, which helps\n

node j. And this uses the fact that both elements\n

can invoke the Compare to method. If we go\n

comparable interface, which we needed. So,\n

if i is less than or equal to J. Awesome.\n

are going to try to swim node k. So first,\n

that by solving for the parent. So remember\n

some people like to start the heaps index,\n

So I get the parent, which is that this position\n

going upwards. And while K is still greater\n

less than our parent, then we want to swim\n

parent and K. And then K is when we can become\n

parent of K once more. And then we'll keep\n

notes. So that's how you do the swim. So the\n

top down node sink. And here, we want to sync\n

node, but I also grab the right node. Remember,\n

two instead of a plus zero plus one. And then\n

is going to be the left one or the right one.\n

one is going to be smaller than the right\n

case it was false. So I checked that the right\n

the right node is less than the left node,\n

And our stopping condition is that we are\n

sink any more. And we can do a similar thing,\n

like like we did in the last method also.\n

to swap because I also have to swap things\n

And this is really what adds a lot of overhead\n

call the swap method, we also have to swap\n

a lot of overhead really, it technically maps\n

you're doing all this internal hashing and\n

So remove. So if the element is now returned\n

inside our heap. So this is how you would\n

out in case you want to revert back and remove\n

all the elements. And once you find the element\n

index and return true. Otherwise, we're going\n

the element one of the elements are. And if\n

now let's have a look at the Remove add method.\n

So if our heap is empty, well, can't really\n

swap the index Why remove with the last element,\n

we're going to kill off that node and also\n

that I was equal to the heap size, meaning\n

heap, just remove, return the removed data.\n

either sink that node up or down. And I'm\n

sink or swim. So I just tried both. So first\n

then I try swimming downwards. And in either\n

this just readjusts where, where the swap\n

down. This method is just a method I use in\n

is good. So it checks essentially the integrity\n

this method with K equals zero, and that starts\n

down the tree and check are we maintaining\n

So our basis, you want to be that k is outside\n

to return true. Otherwise, get our children\n

sure that k is less than both our children.\n

And if we ever returned false, because we\n

that gets propagated throughout the recursion,\n

if everything returns true and hits the base\n

heap. Okay, these last few methods are just\n

into the map, things, how to remove elements\n

here, as I'm using a tree set to add and remove\n

Java has a Balanced Binary Search Tree. So\n

which is really nice. So you guys can have\n

values removes values. And lastly, do a map\n

or in the map rather. So yes, have a look\n

covered everything about the priority queue.\n

also sometimes called the disjoint set, this\n

started. So an outline of things we'll be\n

be going over a motivating example, magnets.\n

be. Then we'll go over a classic example of\n

crucibles a minimum spanning tree algorithm,\n

it needs the union find to get the complexity\n

concerning the find in the Union operations,\n

And finally, we'll have a look at path compression.\n

time the unifying provides? Ok, let's dive\n

union find. So what what is the union fine.\n

elements which are split into one or more\n

primary operations. Find an union. A word\n

will tell you what group that element belongs\n

So if we have this example with magnets, suppose\n

are magnets. And also suppose that the magnets\n

meaning they want to merge together to form\n

all the magnets and give them numbers, and\n

attraction, first, we're going to merge six\n

our union find, we would say union six, and\n

out which groups six and eight belong to,\n

two, three, and three and four are highly\n

a group. So they would form the yellow group.\n

And this keeps on going, and we unify magnets\n

onto already existing groups. So we unify\n

own group, and add to an already existing\n

which are different colors, and we assign\n

everything in the yellow group went into the\n

in our union find to determine which group\n

in the blue group, and the union fine, does\n

manner, which is why it's so handy to have\naround.

Now explaining currently how that works. We'll\n

just a motivating example. So where are other\n

we will. Well, we see the unifying again in\n

In another problem called grid percolation,\n

we're trying to see if there's a path from\n

or vice versa, then the union find lets us\n

Also, similar kind of problem in network activity\n

each other through a series of edges. And\n

like the least common ancestor in a tree,\n

complexity can we attribute to the union fight?\n

is linear time, which isn't actually bad at\n

check if connected operations all happened\n

So almost constant time, although not quite\n

where we can determine how many components\n

groups of nine that's we have. And we can\n

really great. Okay, let's talk about a really\n

is crew skills, minimum spanning tree algorithm.\n

minimum spanning tree? So if we're given some\n

minimum spanning tree is a subset of the edges\n

so at a minimal cost. So, if this is our graph,\n

minimum spanning tree is the following and\n

Note that the minimum spanning tree is not\n

minimum spanning tree, it will also have a\n

we can break it up into three steps essentially.\n

sort them by ascending edge edge weight. Next\n

the sorted edges and compare the two nodes\n

already belong to the same group, then we\n

cycle in our minimum spanning tree, which\n

the, the two groups those nodes belong to.\n

until either we run out of edges, or all the\n

And you'll soon see what I mean by a group,\n

is going to come into play. So if this is\n

on it, first, let's scale the edges and sort\n

all the edges and their edge weights sort\n

processing the edges one at a time, started\n

highlighted the edge, it Jane, orange. And\n

i and j currently don't belong to any group.\n

orange. Next is edge eight, he, so he don't\n

them together into group purple. Next is CGI.\n

have a group yet. So see can go into group\n

to a group. So F can go to group purple.

Next, H and G, knee, neither age nor g belong\n

to the red group. And next we have the Ruby.\n

them their own group, let's say group green.\n

get interesting. Now, we're trying to connect\n

belong to group orange. So we don't want to\n

a cycle, so ignore it. And to check that they\n

find operation in our union fine to check\n

unifying really comes into play. Next is edge\n

and D belongs to group green. So now we want\n

belong to the same group. So either the purple\n

green groups and the purple group. And it\n

them. And this is when the union operation\n

us to merge groups of colors together very\n

Next edge would be d, h, h belongs to group\n

let's say they both become group purple. Next\n

belong to the same group. So that would create\n

edge. So skip. next rounds include edge BTC\n

two groups into one larger group. So we have\n

minimum spanning tree algorithm. Pretty neat,\n

allows us to do this is the union find it\n

efficiently, but also to find out which groups\n

cycle. So so that's crystals algorithm. It's\n

union find works. So I'm going to go into\n

the Find and the union operations work internally,\n

useful way. Okay, so now we're going to talk\n

do on the union find, or the disjoint. Set.\n

actually work internally. So to create our\n

do is we're going to construct a by ejection,\n

the integers in the range zero inclusive to\n

So this step in general is actually not necessary.\n

based unit find, which is very efficient,\n

have some random objects, and we want to assign\n

as long as each element maps to exactly one\n

And we want to store these mappings perhaps\n

them and determine what everything is mapped\n

And each index is going to have an associated\n

So for instance, in the last slide, a was\n

So what you see in this picture is at the\n

our mapping. And in the center is just a visual\n

in the array for each position is currently\n

originally, every node is a root node, meaning\n

on the left of unifying groups together, or\n

to find that we're going to change the values\n

specifically, the way we're going to do it\n

eyes parent is going to be whatever index\n

to unify C and K, we look at C and K. And\n

and K as of nine. So either C's won't come\n

And I chose that case parent is going to be\n

position, I'm going to put a four, because\n

are going to do a similar type of thing. And\n

is going to be E. So at F position, which\n

is zero. Similar thing for a and J. But here's\n

now we want to unify A and B. So if I look\n

I know that A's root node for group greens\n

loop. And in general, I'm going to merge smaller\n

are point to J, because the green groups root\n

find the root node of D which is the and find\n

to merge the smartcompany into the into the\n

Now these want to be part of the orange group.\n

happens. And I now points that C. Now, I want\n

going to merge L and B into the red group.\n

interesting example. So I find a C's root\n

node which is J. Now, component, orange has\n

three. So I'm going to merge the green component\n

to point to C. So I want to unify A and B.\n

nodes until I reach a root node, as parents\n

belongs to the orange group. And if I do a\n

B's parent is also C, which is the orange\n

already unified together. So H and J, G, they\n

to arbitrarily merge them into a new group.\n

if I look, h is parent ID, G, and s parent\nis he

the right component is larger, so I'm going\n

g was the root node, I make it point to E,\n

merge H and B. So H is root node is E, if\n

B's root node is C, because we go from B to\n

is larger than the red component, we're going\n

the root of the orange component. So he now\n

example, I'm not using a technique called\n

going to look at in the next video, which\n

if we want to find out which component a particular\n

the root of that component by following all\n

or a node whose parent is itself and that\n

element belongs to. And to unify two components\n

of each component. And then if the root nodes\n

then they belong to the same component already.\n

nodes point to the become the parent of the\n

union find data structure. So in general,\n

because this would be inefficient as we'd\n

to that note, we don't have access to those.\n

of that. I just don't see any application\n

that the number of components in our union\n

root nodes remaining. Because each root node\n

that the number of root nodes never increases,\n

unify components, so components only get bigger\n

about the complexity of the Union find. So\n

has an amortized time complexity. However,\n

have an amortized time complexity. Not yet\n

something we're going to look at in the next\n

an absolute beast of it. structure, you must\n

if we need to check, if H and B belong to\n

going to take five hops in the worst case,\n

find the root node, which is C, and then we\n

also C. So this takes quite a few hops. Let's\n

is really what makes the union find one of\n

it's how the union find gets to boast in its\n

we get started, it's critical that you watch\n

the find in the Union operation work. Otherwise,\n

what's up with path compression, and how we're\n

Alright, suppose we have this hypothetical\n

path compression, I'm almost certain it's\n

a structure that looks like this. Nonetheless,\n

to unify nodes, E and L. Or just unify groups,\n

and L. And that's what we're calling the unify\n

that start on E and L. And where we would\n

find the root node of L, and then get one\n

compression, we do that, but we're also going\n

the parent note of E. So E's parent is D,\n

F. So we found the root node of E. But with\n

to do. Now that we have a reference to the\n

the root node. And similarly DS are important\n

everything along the path got compressed,\n

so, at every time we do a lookup, on either\n

be able to find out what the parent or the\n

immediately point to it, we don't have to\n

can do this because in a union find, we're\n

them more and more compressed. We're never\n

we do the same thing for L, we find LS parent.\n

find the root. And then we compress the path.\n

to G. And so we compress that path. But we\n

point to the other. And we've unified both\n

E, and once with l have now been merged into\n

is we've compressed along the way as we've\n

Now let's have a look at another example.\n

the regular union find operations where we're\n

version, we now know. So if I run all those\n

So it's the beginning all these pairs of components,\n

right. And this is the final state of our\n

determine what groups say a and j or n, then\n

nodes. So j goes, I use h h goes to eat. But\n

what happens. So I still have all those components.\n

the right hand side, this is what happens.\n

of path compression, that j merged into the\n

And then I keep executing more instructions.\n

dynamically. So so I'm getting more and more\n

So on the last example, we haven't even finish\n

the final state. But with path compression,\n

our path, we get to compress the path along\n

now, we only have one, root, B, E, and

almost everything in constant time, points\n

And we know that the route is easy. So we\n

becomes very stable eventually, because of\n

find with path compression is so efficient.\n

source code. So here's the link to the source\n

github.com slash William fees, slash data\n

structures from past videos. And before we\n

the other videos pertaining to the union find,\n

Okay, let's dig in. Here we are inside the\n

and see a few instance variables. So let's\n

many elements we have in our union find. There\n

one called size. So the interest, while the\n

array I talked about which at index i points\n

is equal to AI, then we know that AI is a\n

of all these like tree like structures right\n

because we create a by ejection between our\n

able to access them through this ID array.\n

of components, that's sometimes some useful\n

a union find, well, you need to know how many\n

find. And I make sure that we have a positive\n

Now go ahead and initialize some instance\n

So initially, everyone is a root node, and\n

is pretty simple. It's given a a node, it\n

does path compression along the way. So if\n

of P, what we're going to do is we're going\n

loop. So we initialize a new variable called\n

is not equal to ID at root. So aka This is\n

so we can stop and the root is stored in the\n

is we do the path compression. This is what\n

back at p, we assign everything from idmp\n

the path gives us that nice amortized time\n

But I don't like having the overhead and doing\n

Okay, so now, we have these simple methods,\n

same component, this will return true, because\n

this will return false. And just calling find\n

just checking if two components are connected,\n

the path, same thing here, if we decide to\n

index p, then when we index into the size\n

the root but at the same time, we'll also\n

And I would just like to note that the the\n

the size because they're the ones that are\n

at the end of the chain. Size just returns\n

disjoint, set components number components\n

method is the last interesting method. So\n

together. So so first of all we do is we find\n

node for Q is. And if the root nodes are equal,\n

we don't do anything. Otherwise, by convention,\n

group. Although I know some people like to\n

and then merge according to not and that may\n

work. So I just like to merge the smaller\n

the roots are different, and we're emerging,\n

must have decreased by one. So that's why\n

components, subtract that by one, because\n

So this whole time, inside this class, I've\n

as elements, like letters that I that we saw\n

by ejection, I would do a lookup to find out\n

give me an integer, and what maps to the element\n

union find data structure created, and turn\n

of dealing with objects and having all this\n

an array based union find. You could also\n

objects. But this is really nice, and it's\n

I want to start talking about a very exciting\n

start to realize that there are tons and tons\n

I want to focus on a very popular country\n

trees, we must talk about binary search trees\n

on binary trees and binary search trees where\n

tutorials, we're going to cover how to insert\n

and also do some of the more popular tree\n

trees. Also, not just binary trees. Okay.\n

course on trees before we get started. So\n

can satisfy either of the following definitions,\n

these are the most popular ones. So trees\n

a cyclic, a cyclic means there are no cycles.\n

we have n minus one edges. And lastly, for\n

those two vertices, you can have two different\n

a tree because there's another route to get\n

Okay, and context is trees, we can have something\n

node of our tree, you can think of it that\n

and you don't have a route yet, it doesn't\n

because any node you pick can become the root\n

that node. And suddenly, it's the new root.\n

child and parent nodes. So child node is a\n

of it as going down or it's an A parent node\n

towards the root. So we have an interesting\n

of the root node? The answer is that the root\n

may be useful to say that the parent of the\n

when programming, for instance, a file system,\n

command line, I'm in some directory, so I\n

somewhere in the file system tree. And if\n

dot dot slash, and now I'm up in another directory,\n

doing this and going up and up in the file\n

directly to the root node, which is slash,\n

very top at the root of the directory, and\n

I am, I'm again at the root. So in this context,\n

is the root. Pretty cool. So just as an example,\n

three and two and a parent four, we also have\n

this a node which has no children, and these\n

just at the very bottom of your tree. Think\n

which is sub tree, this is the tree entirely\n

use triangles to denote sub trees. It's possible\n

node, so that's fine. So if this so tree with\n

particular sub tree and look what's inside\n

nodes and more sub trees. Then we pick another\n

we get another tree. And eventually, we're\n

the question, what is a binary tree? And this\n

node has at most, two children. So both those\n

have at most two children. You can see that\n

and that's fine, because the criteria is at\n

I'm going to give you some various structures,\n

it is a binary tree or not. So is this a binary\n

two children. How about this one? No, you\n

it's not a binary tree. How about this one?\n

Yes, this is a binary tree. It may be a degenerate\n

let's move on to binary search trees. So what\n

it's a binary tree. But Furthermore, it also\n

tree invariant. And that is that the less\n

value of the current node. And the right subtree\n

node. So below are a few binary search trees.\n

and I'm going to give you some trees, and\n

binary search trees or not. What about this\n

on whether you want to allow duplicate values\n

search tree operations allow for duplicate\n

most of the time, we're only interested in\n

particular tree depends on what your definition\n

tree? Yes, this is a binary search tree. How\n

the elements within the tree. Yes, this is\n

to only having numbers within our binary search\n

is comparable and can be ordered. How about\n

tree. And the reason is the the node nine\n

inserting nine, we would have to place it\n

is larger than eight so belongs in its right\n

isn't even a tree actually, because it contains\n

search tree is that you must be a tree. And\n

more time to look at this one. Because it's\n

think of as a binary search tree. And the\n

the binary search tree invariant that every\n

will you'll see that that is true. And also\n

It doesn't look like a tree, but it satisfies\n

tree. Okay, so we've been talking about binary\n

used? Why are they useful? So in particular,\n

of abstract data types for sets, and maps\n

balanced binary search trees, which we'll\n

see binary search, or sorry, binary trees\n

priority queues when we're making a binary\n

like syntax trees, so you're parsing an arithmetic\n

syntax tree. And then you can simplify expression.\n

expressions. So wherever you punch in your\n

evaluated. And lastly, I just threw in a trip,\n

structure. So now let's look at the complexity\n

looked very interesting and also very useful.\n

when you're just given some random data

the time complexity is growing. Be logarithmic,\n

nodes, deleting nodes, removing nodes searching\n

complexity is going to be the logarithmic.\n

are very easy to implement. So this is really\n

tree and D generates to being a line, then\n

which is really bad. So there's some trade\n

search tree, that it's going to be easy to\n

this logarithmic behavior. But in the worst\n

stuff, which is not so good. Okay, let's have\n

a binary search tree. So let's dive right\n

search tree, we need to make sure that the\n

meaning that we can order them in some way\n

know whether we need to place the element\n

And we're going to encounter essentially four\n

to compare the value to the value of the current\n

things. Either, we're going to recurse down\n

than the current element, or we're going to\n

element is greater than the current element.\n

has the same value as the one we're considering.\n

if we're deciding to add duplicate values\n

we have the case that we've hit a null node,\n

and insert it in our tree. Let's look at some\n

of insert instructions. So we have all these\n

tree. And currently the search tree or the\n

want to insert seven. So seven becomes the\n

Next, we want to insert 20. So 20 is greater\n

we want insert five. So we always start at\n

an important point. So you start at the root,\n

figure out where you want to insert the node.\n

oh, five is less than seven. So we're going\n

go to the right, because 15 is greater than\n

20 at 10. Now four, so four is less than seven,\n

create the new node. Now we have four again.\n

to the left and moved to the left. Now we've\n

our tree. So as I said before, if your tree\n

to add another node. And you would either\n

or on the right. Otherwise, you'd do nothing.\n

33. So start at the root, go to the right,\n

Now insert two, so two smaller than everything\n

the left. Now try and see where 25 would go.\n

to go to the right again, because it's greater\n

And finally sex so once left, once right,\n

search tree. So on average, the insertion\n

worst case, this behavior could degrade to\n

if our instructions are the following insert\n

and insert two sets to the right. Okay, now\n

than everything. So I have to place the right\n

greater than everything. Oh, looks like we're\n

still greater than everything. So as you can\n

bad. And we don't want to create lines like\n

is in the tree, or if we want to remove five,\n

thing to find the node, that's going to take\n

one of the reasons why people haven't invented\n

or self balancing trees, which balance themselves\n

But that's it for insertion. It's really simple.\n

we know how to insert elements into a binary\n

elements from a binary search tree. And this\n

to make it very simple for you guys. So when\n

you can think of it as a two step process.\n

to remove within the binary search tree, if\n

we want to replace the node we're removing\n

to maintain the binary search tree invariant,\n

invariant is it's that the left subtree has\n

the right subtree has larger elements than\n

phase one the find phase. So if we're searching\n

one of four things is going to happen. The\n

we've went all the way down our binary search\n

So the value does not exist inside our binary\n

is the competitor value is equal to zero.\n

function that will return minus one if it's\n

it's greater than the current value. So it\n

to go down, or if we found value that we're\n

we found the value. If it's less than zero,\n

to be the left subtree if I compared to returns\n

exists, it's going to be the right subtree.\n

So suppose we have four or five queries, find\n

tree there on the right. So if we're trying\n

the root and 14 is less than so go left. 14\n

than 15. Go left. 14 is greater than 12. So\n

value that we are looking for. Alright, and\n

Wi Fi is less than 31. And now we found 25.\n

Okay, here's her go, go right, go right, your\n

look at 17. So 17 should be on the left. Now\n

again. And, oh, we've hit a point where we\n

that's another possibility the value simply\n

Left of 90, and the left of 19 is a null node.\n

value we're looking for. So now that we found\n

the Remove phase. And in the Remove phase,\n

first case is that the node we want to remove\n

two, and three, as I like to call them, is\n

right subtree, but no left subtree, or those\n

finally case for is that we have both a left\n

you guys how to handle each of these cases,\n

one, we have a leaf node. So if you have a\n

you can do so with a side effect, which is\n

search tree on the right, and we want to remove\n

eight is. Oh, and it is a case one, because\n

it without side effect. So we remove it. Perfect.\n

two and three. Meaning that either the left\n

the successor of the node we're trying to\n

left or right subtree. Let's look at an example.\n

let's find nine. Okay, we found nine. Now\n

is nine doesn't have a right subtree. So the\n

that left subtree. So seven. So now I can\n

of nine. Perfect. Now let's do another example\n

find four. So we find four. And this is our\n

But no, right. subtree. So where do we do,\n

node of that left. subtree. So three, so we\n

successor. Alright, that wasn't so bad, was\n

want to remove node which has both a left\n

is, in which subtree will the successor of\n

And the answer is both the successor can either\n

the smallest value in the right. subtree and\n

there can be two successors. So the largest\n

would satisfy the binary search tree invariant,\n

be larger than everything in the left subtree\n

left subtree and also it would be smaller\n

we had found it in the left. subtree similarly,\n

subtree It would also satisfy the biosurgery\n

be smaller than everything in the right subtree\n

than the right subtree and also larger than\n

was found in the right subtree and we know\n

than everything in the left subtree. So we\n

be two possible successors. So we can choose\n

and we want to remove seven, well seven is\n

and right subtree also seven, so find seven\n

the successor in our left subtree or our right\n

in the right subtree what we do is we go into\n

as possible, go left and go left again. And\n

stop. And this node is going to be the successor,\n

And you can see that quite clearly 11 is smaller\n

now what we want to do is, we want to copy\n

subtree 11 into the node we want to originally\n

seven with 11. Now we have a problem, which\n

want to now remove that element 11 which is\n

shouldn't no longer be inside the tree. And\n

to remove is always going to be either a case\n

it would be the case where there's a right\n

just do this recursively. So so just call\n

cases. Okay, so it's right subtree. So I want\n

right subtree and then remove it. So remove\n

to rebalance the tree like that. Alright,\n

this example, let's remove 14. So first, let's\n

go right. Alright, we found 14. Now we either\n

subtree like we did last time, or the largest\n

ladder this time and find the largest value\n

is we would go into the left subtree and dig\n

the left subtree in digges far right 913.\n

And now what we want to do as before is we\n

into the node we want to remove which is 14.\n

the remaining 13. So now just remove it and\n

I just want to go over some more examples.\n

removing is not quite so obvious. Alright,\n

see if we can remove 18 from this strange\n

root find a teen so dig all the way down.\n

be it's one of those case two or threes. It's\n

successor is just going to be the root node\n

replace it 17. So 17 is a new successor. Perfect.\n

want to remove minus two. So now first find\n

it found it. Now there's two subtrees pick\n

and we're going to go to the right. Alright,\n

one. And that's it. Okay, and that is removals\n

off binary trees and binary search trees with\n

in order post order and level order. You see\n

they're good to know. I want to focus on pre\n

because they're very similar. They're also\n

sort of get a feel for why they have their\n

before the two recursive calls, in order will\n

will print after the recursive calls. So if\n

the only thing that's different between them\n

move on to some detail on how preorder works.\n

stack of what gets called. So when we're recursing\n

node to go to. And what you need to know about\n

current node and then we traverse the left\n

for order where we're going to do is insert\n

we go down to D, go down to H. And now we\n

call stack and go to D and then we go to I\n

so we recurse back up, so we push AI off the\n

go back to B we also are a process B but now\n

and explore II. Now we've explored ease. So\n

off the stack. And now a now we need to explore\n

C then F then j and then right at the bottom,\n

are recursive push node k off the stack, push\n

C's right subtree. So g now l and now we're\n

would exit our function. And at the bottom,\n

Okay, now let's cover inorder traversal. So,\n

the left subtree that we print the value.\n

for this example, I'm going to be using a\n

binary tree. And you'll see something interesting\n

it's our route. Then we go left, then we go\n

I was going left, I would push those on to\n

because when I call in order, the very first\n

I only print once I've traversed the entire\n

now one is a leaf node, then I've already\n

I can print the current value. Then I recurse\n

threes left subtree now we go right now and\n

recurse. Now I can print six because I've\n

then recurse then print 11. Now we need to\n

left, go left may explore 12 recurs and we're\n

14. Also, because 14 has no sub trees up.\n

stack, print 15, because we will explode 15th\n

last thing we need to do is finish our function\n

So go back up. And now, did you notice something\n

traversal? Well, what happened was we printed\n

which is why it's called an inorder traversal.\n

the values in increasing order, which is really\n

inorder traversal. Now, let's look at the\n

says, okay, traverse the left subtree, then\n

done doing both of those, only then print\n

look at our tree right now, the last value\n

we need to process a lemon's entire left subtree\n

So let's start at 11 and explore its left\n

one, because we've explored both its left\n

we haven't explored its right subtree yet,\n

trees which don't exist. Now we can print\n

trees. And then similarly, they go down to\n

don't print 11, because we still need to do\n

Go up to 13, print 14, go back up to 13. And\n

we haven't explored all of its right subtree\n

the stack and print on the way back up. And\n

node we have visited. And that's pre order\n

to look at level order traversal, which is\n

other two, a level order traversal is we want\n

start with 11. They want to print six and\n

And you're like oh, how am I going to do that.\n

is by doing something called a breadth first\n

to the leaf node. So she knows what a breadth\n

the same thing, a tree is a type of graph,\n

do to do our breadth first search is we're\n

left to explore. And how it's going to work\n

only the root node. And we're going to keep\n

in our queue until our queue is over. A bit\n

queue. On the right, I've inserted node 11.\n

add elevens left child and right child to\n

the queue. And I've also removed 11. So so\n

by 15. And then I would keep adding children\n

So let's have a look. So I've pulled 11 from\n

Now the next thing on the top of the queue\n

three and eight the queue, then 15. Next up,\n

queue, and next up in the queues three. So\n

and then move on, explore eight, eight has\n

As you can see that as I'm exploring nodes,\n

most recent thing in the queue. And this gives\n

And this is how you do a breadth first search\n

we had to use that special trick of using\n

do level order traversals recursively, we\n

Okay, finally time to look at some source\n

code I'm about to show you can be found at\n

in the description at the bottom of this video,\n

can also find it more easily. And now let's\n

source code for the binary search tree. The\n

thing you will notice is I have a class representing\n

anything that is comparable, we need things\n

them accordingly within the binary search\n

variables, actually only two, in fact, one\n

binary search tree, and another one, which\n

this binary search tree is a rooted tree.\n

a left node and a right node, as well as some\n

here. So it's some comparable type T. Okay,\n

search tree is empty. It simply checks if\n

the node count, which gets either incremented\n

Okay, here's the public method to add elements\n

private method down here, as you will notice.\n

business and the public method to just check\n

the binary search tree. This insertion method\n

a new element into the binary search tree\n

something inside the binary search tree. So\n

search tree, okay, so supposing this branch\n

does not already exist in the tree, then we're\n

add this new element to the binary search\n

by one and return true because well, this\n

at the recursive method now. So our base case\n

insert our element at so we will create a\n

with the value of the element, we want insert\n

which sub tree we want to place our element\n

subtree of the first branch, or the right\n

look at removing. So here's the public method\n

the method if it exists within the tree. So\n

it is going to return false, meaning we have\n

string. And if it is contained, I'm also going\n

at this recursive method to remove the node.\n

base case, it's now returned now. And in the\n

to find it. And we know it exists. Because\n

within the tree so we can remove it. And that\n

Phase I was talking about in the later video.\n

if it's less than, so we're going in the left\n

It's going to be one of these two cases, otherwise,\n

finds the node. And here's where we do the\n

in my slides. But in fact, you can think of\n

because two the cases are very similar. So\n

node, it's really that that can also be thought\n

case is the case where the left subtree is\n

case, the right subtree is now but the left\n

I'll get to later, we have both subsidiaries.\n

have a right subtree, then I'm going to say\n

the root node of that right subtree. So node\n

destroy the data within this node and the\n

where I only have a left subtree. What I'm\n

left subtree and grab the root node. And I'm\n

to destroy this node because we know we don't\n

easy. Now let's look at the key. So we have\n

subtree. So as I mentioned in my slides, we\n

subtree, or the smallest node in the right\n

in the right subtree. So I go down to the\n

the node or the successor node if you will.\n

and call ourselves to remove the successor\n

in the left subtree then you can just uncomment\n

removing a nutshell and they also had these\n

dig right. Moving on, I also have this method\nthat checks

contains an element. So given an element return\n

is within this binary subtree. And this is\n

phase, if we reach a null node, we would definitely\n

get our comparative value, which is either\n

the left subtree, meaning this case, or greater\n

Or if we found the element, then that's zero\n

Just as a bonus, I also threw in a height\n

of the tree, it will do so in linear time,\n

method. And all this does is it's fairly simple.\n

return zero. Otherwise, we're going to return\n

the right subtree. Because one of our sub\n

that's going to be the one that we want the\n

add plus one. So this corresponds to a depth.\n

the height of the tree is, you want to go\n

created this method called traverse. And what\n

which is an enamel type, I'm going to show\n

then I pick whichever order you give me and\n

I want to traverse. So if you tell me I want\n

order fashion that I'm going to return you\n

want to traverse the tree in order for it\n

Let's have a look at what this tree traversal\n

So that is simply an e&m type you can see\n

things, it's pre order in order post order.\n

these traversals iteratively. So that you\n

be slightly slower, and perhaps less convenient,\n

want to dive into the code because it is fairly\n

traversal, then it does look pretty gross,\n

have to check for concurrent modification\n

great interview questions like how do i do\n

I do a post order traversal, iteratively,\n

great to practice. If you want to actually\n

go on the GitHub repository and have a look.\n

in the last slides. So you should be good\n

Anyways, I just want to be a bit more fancy\n

it for the binary search tree.

Today we're going to be talking about hash\n

of all times, if I had a subtitle, it would\n

let's get started. There's going to be a lot\n

We're gonna start off with with a hash table\n

why do we need one. Then we're going to talk\n

In particular, separate chaining, open addressing\n

there's a ton more, there, we're going to\n

is a really popular implementation. And there's\n

covered. So we're going to be talking about\n

that's done. I'm not even giving lots and\n

not super obvious how they work. And to finish\n

finally removing elements from the open addressing\n

All right. So to begin with, what is a hash\ntable.

a data structure that lets us construct a\n

a technique called hashing, which we'll talk\n

as long as it's unique, which maps to a value.\n

names, and the value could be someone's favorite\n

Mike is this purple, Katherine's is yellow,\n

so each key is associated with the value.\n

don't have to be unique. For example, Micah's\n

favorite color is purple. We often use hash\n

Below is a frequency table of the number of\n

Hamlet, which I Parson obtained this table.\n

word, Lord 223. But the word cabbage did not\n

track frequencies, which is really handy.\n

any key value pairs given that the keys are\n

about shortly. So to be able to understand\n

table, we need to understand what a hash function\n

will denote from now on as h of x, for some\n

number in some fixed range. So that's pretty\n

hash function. So if our hash function is\n

6x, plus nine modulo 10, well, all integer\n

inclusive. No matter what integer number I\n

certain values, or keys fuel into the hash\n

that the output is not unique. In that there\n

the hash function which yield the same value,\n

the same thing, and that's completely fine.\n

not just on integers, but on arbitrary objects,\n

suppose we have a string s, and we're gonna\n

defined below. So this hash function, all\n

characters within the string, and then at\n

any given string just output a number. And\n

simple inputs, so h of BB gets 66, or 66.\n

The empty string gets zero because we don't\n

effectively converted a string to a number.\n

you. Suppose we have a database of people\n

have an age, a name and a sex. I want you\n

going to be given a person object as an argument.\n

going to map a person to the set of values,\n

the video, just create any hash function that\n

so here's my attempt at creating such a hash\n

of possible hash functions we could define\n

And here's a simple one. So I'm gonna say,\n

whatever there is, that's the starting value\n

of the person's name, again, an arbitrary\n

males, and then mod by six. So as you can\n

defined. At this point, we're going to get\n

later. So this particular hash function yields\n

very, very important that we need to talk\n

if we have a hash function, and two objects,\n

then those two objects might be equal. We\n

check x against y. Yes, the hash function\n

there. But if the hash functions are not equal,\n

a good question. How can we use this to our\n

The answer is that instead of comparing X\n

hash values, and first let's compare the hash\n

and Y explicitly, and in this next example,\n

the problem of trying to determine if two\n

is something you want to do in an operating\n

the hash values for file one and file two,\n

to see if they match or don't match, because\n

super fast. So if possible, we don't want\n

X and Y directly or file one against file\n

per byte if their hash values are equal. So\n

more sophisticated than those that we use\n

hashing algorithms called cryptographic hash\n

property of hash functions is that they must\n

if h of x produces a y, then h of x must always,\n

value. This is super critical, because this\n

this happens, we do not want this. So an example\n

that introduces say, a global variable or\n

So in this particular hash function, the first\n

six. But then if I call it again, we've incremented\n

Oh, not good. Something else but hash functions\n

To minimize the number of hash collisions,\n

shortly. But a hash collision is when two\n

is h of x equals h of y. And the reason why\n

hash function are hit, so that we can fill\n

Table we generated earlier, William and key\n

able to answer a central question about the\n

our hash table. So what makes a key of type\n

going to implement our hash table using these\n

And to enforce that behavior, you'll see a\n

the keys you use, be immutable, meaning you\n

constants. So they're things like immutable\n

or lists or things you can add or remove things\n

condition, and we have a hash function that\n

say that, that that type is hashable. Okay.\n

details. How does the hash table work? Well,\n

really quick insertion look up, and the removal\n

that using the hash function as a way to index\n

a fancy word for an array. Think of it like\n

So again, we use the hash function as a way\n

function gives us an index to go look up inside\n

time. Given that we have a uniform hash function,\n

on the right as an indexable block of memory.\n

entries with the hash function, h of x. So\n

string key value pairs into the table that\n

their usernames, say in an online programming\n

function, I chose x squared plus three, Montana.\n

insert the key value pair, three by eater,\n

is by eater got a rank of three, and we want\n

we do is we hash the key, which is three,\n

plus three montagner. Two, so in our hash\n

put the key B three, and the value to be byte\n

say, which is usually what I call myself an\n

one. And if we hash one, then we get four.\nSo at index four

then we're going to put the key in the value\n

want to insert Lauren 425, we've got rank\n

table where she goes, then we can do the same\n

insert orange Knight, again began by hashing\n

keep doing this, you keep filling the table,\n

Now, in the event that we want to do a lookup,\n

to do is compute the hash value for R and\n

this user is. So say I want to find the user\nwith reign 10.

And I hash 10. Figure out its index is three\n

However, how do we handle hash collisions?\n

and eight have the same value. This is problematic.\n

them inside our table, they would index into\n

we use one of many hash collision resolution\n

but the two most popular ones are separate\n

separate chaining is that we deal with hash\n

usually a link lists to hold all the different\n

value. Open addressing is slightly different.\n

finding other places in the hash table offset\n

So an open addressing, everything is kept\n

you have multiple auxiliary data structures.\n

actually pretty remarkable. In fact, it's\n

time insertion, removal and search. But if\n

uniform, then you can get linear time, which\n

something super, super cool. And that is hash\n

dive right in what is separate chaining. Separate\n

resolution techniques. And how it works is\n

keys hash of the same value, we need to have\n

hash table. So it's still functional. Or what\n

auxilary data structure to essentially hold\n

and look up inside that bucket or that data\n

for. And usually, we use the length list for\n

lists, we can use arrays, binary trees, self\n

Okay, so suppose we have the following hash\n

of key value pairs of age and names. And we\n

been computed with some hash function. So\n

For now, we're just going to see how we can\n

Okay, so on the left is our hash table. So\n

of these key value pairs into this hash table\n

easy it is. Okay, so our first person is will\n

going to put in, in that slot three, Leah,\n

we're going to put her at index four. So the\n

rig age 61 hash two and put them there. And\n

get a little bit full in our hash table here.\n

Okay. Lera, age 34, hash to four, but we say\n

we do? Well, in separate chaining, we just\n

in the array is actually a linked list data\n

the link list and see if alera exists and\n

add lira at the very end of the chain.

so Ryan also hash to one but then we look\n

add a new entry at position one. alera age\n

exists. So in our hash table, so we're good.\n

to update it. So fin age 21, hash to three.\n

hash to three. So what we're going to do is\n

length list chain. So note that even though\n

value, that is index three, and they have\n

we store both the key and the value as an\n

how we're able to tell them apart. Okay, now\n

has to four. So scan through the linked list\n

we have to append mark at the very end. All\n

do lookups in this structure. So it's basically\n

a name, we want to find what the person's\n

when we hash him, we get one. So we suspect\n

say a bucket, I just mean, whatever data structure\n

link lists. So if you scan this linked list\n

comparing the key. So we're comparing the\n

a match. So keep going. Compare Ryan, Ryan,\n

inside in that entry, say, oh, his age is\n

the age of Mark hash mark. And since our hash\n

if there's a mark, then it's going to be found\n

bucket for scan through, oh, last one is a\n

that the value or the key looking forward\n

turn now. Okay, so here's a good question.\n

and lookup time complexity? If the hash table\n

list chains? Good question. And the answer\n

your hash table, you'll actually want to create\n

rehash all your items and re insert them into\n

fixed size. Okay, and another good question,\n

table with separate chaining? Well, the answer\n

your key. And instead of doing a lookup while\n

length list, that's another question. How\n

to model the bucket behavior? Yes, of course.\n

linked lists include arrays, binary tree,\n

approach and our hash map. So once they get\n

a binary tree, or maybe a cell balance spanning\n

methods are a bit more memory intensive and\n

be less popular, but they might be a lot faster\n

All right, it's time to have a look at some\n

table. So here I am on my GitHub repository\n

find the source code here under the hash table\n

the hash table. Today, we're going to be looking\n

in the later videos, probably one of these\n

So let's dive into the code. I have it here\n

So first things first, I have two classes,\n

chaining hash table. So let's have a look\n

individual items or key value pairs, you would\n

So in Java, we have generics, so a generic\n

So when I create an entry, I give it the key\n

So there's a built in method in Java to compute\n

you can override it to specify the hash code\n

convenient. So compute the hash code and cache\n

don't have to re compute this thing multiple\n

for something like a string, hash code can\n

good. So here, I have an equals method, which\n

because I don't want to have to do any casting.\n

If the hashes are not equal, we know from\n

equal, so we can return false. Otherwise,\n

about it for the entry class. Very simple,\n

thing. So the hash table itself. Okay, so\n

holds three, three items, and the load factor\n

or be 0.75. So that's the maximum capacity\n

important instance variables, we need to go\n

the load factor goes above this value, then\n

so the actual maximum number of items that\n

So the threshold. So this is computed to be\n

us, hey, you're above the threshold to resize\n

in the table. And this is the table itself.\n

have entries, pretty simple. So there's a\n

table, just using the default settings with\n

load factor. So this is a designated constructor,\n

factor is compute default capacity. And make\n

and capacity just so that I know you don't\n

weird things happening if the capacity is\n

threshold and then finally initialize the\n

a look at all these methods right here. So\n

table empty, is the hash table empty. So this\n

normalized index. And it's used when you want\n

it says in the comments here, essentially,\n

hash value in a domain, zero to capacity.\n

can be anywhere in the domain of an integer,\n

to positive to the 31. around that. So what\n

sign from the hash value, and then modified\n

so we can actually use it as a lookup index.\n

how the table that's straightforward. Contains\n

going to do is compute given a key. So we\n

the hash table. Right? So we're going to do\n

then now give us the bucket index. So which\n

in a hash table? I'm just going to seek to\n

if the entry is not equal to no exists, if\n

for add an insert are all common names for\n

or updating a value inside of the hash table\n

something we absolutely don't want. So just\n

going to create a new entry, find the bucket\n

method we'll get to. Okay, get. So given a\n

that key. Again, though, allow no keys. And\n

don't want to find which bucket this particular\n

find the entry. assuming it's not no, then\n

value. If it is no, well, the key doesn't\n

the key now from the hash table. So he's not\n

call his private remove entry method, which\n

so which, which bucket does this keyboard\n

to seek for the entry inside the link list\n

we're going to extract the actual link list\n

in Java. So this removed from that link this\n

the actual value, that's all we have to do.\n

So insert bucket insert entry is a given a\n

inside of it. Okay. So first, since we know\n

automatically get the linked list structure.\n

have to create a new linked list. So we're\n

list data structures, which is good, because\n

to. So next up, I find the entry that already\n

an update, for instance. So if the existence\n

a new entry to the end of the blank last.\n

the size, and check if we're above the threshold,\n

now to indicate that there was no previous\n

So then just update the value in the existing\n

So seek entry this method we've been using\n

particular entry at a given bucket index,\n

They probably know what's going on by now.\n

bucket index. Otherwise return now if it doesn't\n

the entries in the linked list and compare\n

was a match, return that entry otherwise return\n

method called resize table. So this resizes\n

the table. First we double the capacity. We\n

have a higher threshold because we have increasing\n

new capacity. So this new table is bigger\n

current table. Look for linkless data structures\n

loop through all these entries, calculate\n

insert it into this new table and after that\n

the old table at the end, set the table to\n

these last two methods, so just return all\n

fairly simple. And these last two methods\n

need to go over. So that's essentially, separate\n

with the link lists much more difficult to\n

or something like that. I'm pretty excited,\n

collision resolution technique for hash tables.\n

quick recap on hash tables so that everyone's\n

table is to construct a mapping from a set\n

to be hashable. Now, what we do is we define\n

into numbers, then we use the number obtained\n

into the array or the hash table. However,\n

time to time, we're going to have hash collisions,\n

So we need a way to resolve this and open\n

so what we're going to be using the open addressing\n

to keep in mind is the actual key value pairs\n

itself. So as opposed to say, an auxilary\n

method we saw in the last video. So this means\n

the hash tables, and how many elements are\n

there are too many elements inside of the\n

hard to find an open slot or a position to\n

of terminology, we say that the load factor\n

table and the size of the table. So this means\n

Here's a neat chart from Wikipedia. So on\n

methods. One of them is chaining, that is\n

open addressing technique. And we can see\n

it gets to a certain threshold, it gets exponentially\n

that say point eight mark. In fact, we're\n

usually. And what this says is, we always\n

by the Greek letter alpha, below a certain\n

our table once that threshold is met. Right,\n

into our hash table, here's what we do, we\n

on our key and we hash the value and this\n

table for where the key should go. But suppose\n

a key in that slot, well, we can't have two\n

work. So what we do is we use a probing sequence,\n

tell us where to go next. So we hashed to\n

And now we're going to probe along using this\n

going to eventually find an open spots along\n

an infinite amount of probing sequences to\n

have linear probing, which probes via a linear\n

when we're probing we start, usually x at\n

slot, then we just increment x by one. And\n

functions. for linear probing, we use a linear\n

function. And then there's double hashing,\n

is we define a secondary hash function on\n

inside the probing function. And the last\n

probing function that we can use. So given\n

seed it using the hash value of our key, which\n

to be the same thing. And then we can use\n

pretty neat, and increment by x each time\n

just getting the next number in the random\n

that. Alright, so here's a general insertion\n

a table of size n. And here's how the algorithm\n

x is a constant, or sorry, a variable that\n

going to increment x each time we fail to\n

just by hashing our key. And that is actually\n

look in a table first. So while the table\n

to No, we're going to say our new index is\n

hash to plus the probing function, mod n,\n

and then we're going to increment x, so that\n

at a different position. And then eventually,\n

set up our probing function in such a way\n

we will always find a free slot, because we\n

so here's the big issue with open addressing.\n

we choose modulo n, are going to end up producing\n

size itself. So imagine your probing sequence\n

cycles. And your table is of size 10. But\n

because it's stuck in a cycle. And all of\n

in an infinite loop. So this is very problematic,\n

to handle. Right, so let's have a look at\n

And using open addressing, it's got some key\n

the circle with a bar through it is the no\n

probing sequence p of x equals 4x. And suppose\n

and that the key hashes to eight. So that\n

at position eight, but Oh, it's already occupied,\n

there. So what we do well, we probe, so we\n

we get eight plus for my 12. Well, that's\n

Oh, that is also occupied, because the key\n

we compute P of two, and then they gives us\n

already occupied, and then we keep probing.\n

So we'll keep probing and probing and probing,\n

position. So although we have a proving function,\n

The probing function is flawed. So that's\n

functions are viable. They produce cycles\n

handle this? And in general, the consensus\n

we try to avoid it all together by restricting\n

to be those which produce a cycle of exactly\n

I have a little Asterix here and says there\n

are some probing functions we can use, which\n

And we're going to have a look at I think,\n

Alright, so just to recap, techniques such\n

and double hashing, they're all subject to\n

to do is redefine probing functions, which\n

length and to avoid not being able to insert\n

loop. So this is a bit of an issue with the\n

we can handle. Although notice that this isn't\n

in the separate chaining world, just because\n

just captures all our collisions. Okay, this\n

talking about hash tables, and the linear\n

So in general, if we have a table of size\n

what your probing function is. So we start\nour constant

or sorry, variable x at one, the key hash\n

gives us four key. And our first index we're\n

hash position. And while the table at the\n

is already occupied, then we're going to offset\n

probing function mode. And every time we do\n

our probing function pushes us along one extra\n

then we can insert the key value pair into\nthe table

Alright, so what is linear probing? So linear\n

according to some linear formula, specifically,\n

b. And we have to make sure that a is not\n

a constant which does nothing. Now have a\n

constant b is obsolete. And if you know why,\n

with the others. And as we saw in the last\n

currently, and it's that some linear functions\n

n. And we might end up getting stuck in a\n

our linear function to be p of x equals 3x,\n

some reason our table size was nine, then\n

Assuming that positions, four, seven and one\n

So the fact that we're only probing at those\n

all the other buckets, which is really bad.\n

loop, we cannot get stuck in this situation\n

question which values of the constant A and\n

M. It turns out that this happens when the\n

prime to each other. The two numbers are relatively\n

is equal to one So that is a an N have a GCD\n

function will always be able to generate a\n

to find an empty bucket. Awesome. Alright,\n

suppose we have an originally empty hash table,\n

And we selected our probing function to be\n

equals nine. And then we also selected a max\n

and the threshold will then be six. So we\n

based on the probing function we chose at\n

infinite loop while inserting? Based on what\n

answer is, yes, the greatest common denominator\n

not one. So let's go ahead and attempt to\n

may not hit any problems. Okay. So first,\n

some key value pairs, I want to insert, and\n

that the hash value for K one is equal to\n

of K one plus the probing sequence, add zero,\n

insert that key value pair at position two.\n

is equal to two again. So we're going to try\n

two. But oh snap, we have a hash collision.\n

to offset the probing function at one and\n

of inserting it now at two, we're going to\n

in because that slot was free. Now, let's\n

that hashes the three, then we can insert\n

Now, notice that we're trying to re insert\n

table. So instead of inserting it, we're actually\n

exists in the hash table. Alright, so from\n

two is two. So So then we look at position\n

So we increment x offset by P of one. And\n

update valuate there. Let's go to K five.\n

eight. So eight is taken. So we're going to\n

we're going to insert the key value pair there.\n

six hashes the five, then let's probe ones\n

a hash collision, let's keep probing. So now,\n

right, another hash collision, so we have\n

back to five. So we've hit a cycle. Alright,\n

expected this to happen because we knew that\n

to three and not one. So if we look at all\n

instead of six, we see that the ones that\n

with and the table size are 12457 and eight,\n

something else. So this comes to the realization\n

p of x to be one times x, then the greatest\n

going to be one no matter what our choice\n

one times x is a very popular probing function\n

hash table, and we wish in certain more key\n

going to pick a probing function that works,\n

I'm going to pick the table size to be 12\n

should occur. All right, so let's go with\n

one has a hash value of 10, then at index\n

a hash value of eight, then slot eight is\n

now, suppose k three is equal to 10, hash\n

to keep probing. Alright, so if we use our\n

So they'll give us three module and when we\n

k four. Now suppose the hash value for K four\n

we hit k three, which inserted last time.\n

able to pull out eventually when we hit the\n

we've actually reached the threshold of our\n

that I picked alpha to be 0.35. So n, which\n

And we just finished inserting the fourth\n

So how we usually resize the table is VSM,\n

or so on. But we need to double in such a\n

a doubling, and is equal to 24, and the GCD\n

so it's still 3.5. So our new threshold is\n

the programming function. Alright

so let's allocate a new chunk of memory for\n

the old elements in our old table into this\n

right. So we scan across all these elements,\n

along. So from before we knew that hash value\n

is going to go at position 10. Scan along\n

three was 10. So it should go in position\n

so we have to keep probing. So if we add our\n

we get 10 plus five, which is 15. So we're\n

table, keep probing nothing here and nothing\n

k two. So we know from before k two is equal\n

eight. Now we know k one is equal to 10. So\n

that's taken so to probe so the next position\n

us 20. So insert k one v one at 20.

so now we throw away the old table and we\n

table we're working with and we were at inserting\n

And that spot is free. So we are good. So\n

I know how insertion works. Now how do I remove\n

open addressing? And my answer this is that\n

And we're going to do it after we see all\n

it's actually non trivial. All right, let's\n

works. Let's dive right in. So let's recall\n

of size and using the open addressing collision\n

a variable called x to be one, which we're\n

to find a free slot, then we compute the key\n

going to check and we're going to the loop.\n

the table at that index is not equal to null,\n

happens, we're going to offset the key hash\n

in our case is going to be a quadratic function.\n

we will find an open slot to insert our key\n

probing? So quadratic probing is simply probing\n

when our probing function looks something\n

c, and a, b, and c are all constants. And\n

we degrade to linear probing. But as we saw\n

functions are viable because they don't produce\n

an infinite loop. So as it turns out, most\n

will end up producing a cycle. Here's an example.\n

to be p of x equals 2x squared plus two, the\n

the current table size was nine, then we would\n

we would probe at position zero, we would\n

suppose those two entries are full, and then\n

function is only ever able to hit the buckets,\n

to reach all the other buckets, 012356, and\n

when four and seven are already occupied.\n

then is, how do we pick a probing function,\n

numerous ways. But here are the three most\n

is to select the probing function to be p\n

size a prime number greater than three, and\n

one half or less than or equal to one half.\n

equals x squared plus x divided by two, and\n

And the last and final one says that p of\n

and keep the table size a prime number where\n

we can say that I were table size was 23,\n

to three mod four. So any of these will work.\n

how they work and whether table size should\n

So we're going to focus on the second one\n

by two and the table size is a power of two.\n

hash table, and we want to insert some key\n

probing function, p of x equals x squared\n

is a power of two, so it's eight. And that's\n

the table threshold is going to be three.\n

absolutely be a power of two, otherwise, this\n

guy. So suppose that k one hashes six, then\n

Right, next k two, suppose k two is equal\n

five, no collision there. Suppose k threes\n

need to handle that. So we're going to try\n

to six. So we probe again, and that brings\n

going cert, k three, and V three key value\n

before we can do that, we've reached the table\n

first. Okay, so let's allocate a new block\n

table to keep it a power of two. So our new\n

However, a new threshold is six, and the probing\n

the entries in the old hash table into the\n

k three hashed to five, so we're going to\n

there. And no element at position 123 or four,\n

right there. So we know from before that key\n

a preposition five, there's a hash collision,\n

one equals six, position six, or insert k\n

them before k one hash two, six, but we can't\n

So we're going to probe along. So we're going\n

that does it for resizing the table. So let's\n

to insert inside our table. So suppose that\n

buy 16 years, this position to, so we're going\n

we've already seen k three, and we know its\n

is already in our hash table, we're going\n

probing functions, zero gives us five. So\n

v3, which it was before. So suppose that the\n

to three mod 16. So that's why it's free.\n

seven suppose hashes to well, we have a collision\n

we probe, our probing function gives us an\n

can so now we are at position five, but that's\n

for a fourth time scan offset of six. So that\ngives us eight.

That slot is free. We're going to answer that\n

and the double hashing, open addressing collision\n

for those of you who don't know how we do\n

we start with a variable x initialized to\n

We set that to be the first index that we're\n

it's not now. So the goal is to find an empty\n

still hitting spots where there are already\n

to offset our key hash using a probing function.\n

probing function. And we're also going to\n

along further and further. Once you find a\n

pair into the hash table. Okay, so what's\n

is just a probing method like any other. But\n

to a constant multiple of another hash function.\n

something like this, we give it as input,\n

x, and we compute x times h sub two of k,\n

here's an important note, H 2k, must hash\n

your key is a string, well, h two of K must\n

the nature of K must also hash integers. So\n

that double hashing actually reduces to linear\n

until runtime, because we dynamically compute\n

reduces to linear probing at runtime, we may\n

probing, which is that we get stuck in an\n

our secondary hash function at runtime calculate\n

h1 of K was four, at the table size was nine,\n

occurring. So the cycle produces values of\n

to reach any of the buckets, 02356, and eight.\n

that means we're stuck in an infinite loop\n

to insert our key value pair because we're\n

issue we have to deal with. So to fix the\n

one strategy, we're going to pick our table\n

to compute a value called delta. So delta\n

occasionally Delta might be zero. And if that's\n

to be stuck in a cycle because we're not going\n

going to be multiplying by zero. So when this\n

All right. So here's the justification why\n

going to be between one inclusive and non\n

between delta and n is going to be one, since\n

conditions, we know that the probing sequence\n

to able to hit every single slot in our hash\n

free slot in the hash table, which there will\n

a certain threshold, that we're going to be\n

Okay, so here's a core question, how do we\n

the keys we're using have type T, and whenever\n

h 2k, two hash keys that are also of type\n

systematic way of generating these new hash\n

we might be dealing with multiple different\n

computer science, Almost every object we ever\n

building blocks, in particular integers, strings,\n

on. So we can use this to our advantage. Luckily,\n

these fundamental data types. And we can combine\n

function h two of K. Frequently, when we compose\n

functions called Universal hash functions,\n

data types, which is quite convenient. Alright,\n

hashing. So suppose we have an originally\n

probing function to be p of x equals x squared\n

be in our table size v n equals seven. Notice\n

max load factor to be alpha equals point seven,\n

So once we hit five elements, we need to grow\n

all these key value pairs on the left into\n

keyword and v one. Now suppose that the hash\n

is 67, and H 2k. One is 34. And first thing\n

two of K one modulo seven, which is the table\n

where this key value pair should go and should\n

h one of K two is two, and H, two of K two\n

just going to insert a position two, because\n

is two, and H 2k. Three is 10. These are just\n

So then delta would be three in this, in this\n

have a hash collision, because we're trying\n

two is already there. So what we need to do\n

the position to be our original hash function\n

plus one times our delta value, mod seven,\n

to position five right there. Now, right,\n

h one of K four is equal to two, and h two\n

delta. So h two of K four modulo seven is\n

is zero. So when this happens, we know that\n

we don't get stuck in an infinite loop. So\n

mod seven gives us two. So we have a hash\n

you keep probing. So now we probed by multiplying\n

So now we're going to try insert k three,\n

but with a new value. So we're going to be\n

h 1k three is equal to two. Actually, we should\n

is 10. So compute delta. So we have a collision.\n

and update its value. Now suppose the first\n

secondary hash function of k six is 23. Then\n

we try to insert it, it goes to position So\n

delta mod seven, that gives us five. There's\n

offset at two times delta minus seven, which\n

we're able to insert our key value pair there.\n

so it's time to resize and grow the table,\n

So one strategy when we're trying to resize\n

need to keep our table size to be a prime\n

find the next prime number above this value.\n

and the next prime number 14 is 17. So 17\n

a new table of size 17, and go through the\n

into the new table. So from before, a 12k,\n

compute delta, and we know we're going to\n

collision. Next up, and nothing in position\n

value for K to two and the secondary hash\n

to compute delta to be six. So we're going\n

Next 1k four. So we know h one of K four is\n

compute our delta value. And notice that our\n

before, but seven because our mod is a 17\n

But we need to keep probing. So compute the\n

nine months 17. Next one, insert k one, suppose\n

then compute delta. And that gives us zero.\n

h one of K one plus zero times delta gives\n

probing. now compute the offset at one times\n

the x value. So now two times delta t is four,\n

value pair there. And the last 1k three. So\n

K three is 10. Delta is then 10. And we have\n

us 12. And that slot is free. And we reached\n

old table and replace it with a new table.\n

pair from before which is k seven. Suppose\n

is three, then our delta value is three. And\n

right, I know a lot of you have been anticipating\n

from a hash table using the open addressing\nscheme.

So let's have a look first at what issues\n

it naively, I think this is valuable. Because\n

hash table, and we're using a linear probing\n

equal to x. And we want to perform the following\n

1k, two and K three, and then remove k two\n

for the sake of argument, let's assume that\n

and K three, all equal to one. This is a possible\n

hashes to one. So we're going to insert at\n

has a hash collision with K one which is already\n

so insert it in the next slot over, that's\n

let's probe Okay, another hash collision.\n

we are going to remove k two, and we're going\n

just going to clear the contents of the bucket\n

was equal to k two. So we haven't found the\n

have found k two. So we're just going to remove\n

table and obtain the value for K three. Let's\n

we get one and K one cycles here three. So\n

no element. So what does this mean? So since\n

we're forced to conclude that he three does\n

we would have encountered it before reaching\n

works inside a hash table. So this method\n

doesn't work. Because k three clearly exists\n

index three. So here's a solution to the removing.

an element, we're going to place a unique\n

element to indicate that a specific key value\n

we're doing a search, we're just going to\n

the deleted bucket with a tombstone like we\n

we now search for the key k three. Okay, so\n

equal to k three. So keep probing. Alright,\n

was deleted. So keep probing. All right, we\n

value v three as our answer for the search.\n

I have a lot of tombstones cluttering my hash\n

with tombstones is that we're actually going\n

table. So they're going to increase the load\n

resize the hash table. But there's also another\n

a new key value pair, then we can replace\n

key value pair. And I want to give you guys\n

Suppose this is our hash table of size eight,\n

p of x equals x squared plus x divided by\n

play doing this when we want to do a lookup.\n

inside the hash table and the hash value for\n

key k seven. So k seven, hash to five. So\n

four. So let's keep probing. So we probe quadratically.\n

and that's position six. Now, position six\n

we encounter which has a tombstone in it.\n

for later to perform an optimization. Okay,\n

seven yet. So when we probe at position two,\n

because we have a tombstone so we have keep\n

So let's keep probing, and Aha, we have found\n

v seven. Now, however, we can do an optimization,\n

four times to find k seven, because we just\n

an optimization we can do is to relocate the\n

position where there was a tombstone. So that\n

We call this lazy deletion or lazy relocation.\n

there with K seven v seven. And now we have\n

going to want to replace the old one with\n

going to be having a look at some source code\n

as a collision resolution scheme. And you\n

William fiza, slash data dash structures,\n

to find a whole bunch of hash table implementations.\n

here. In particular, we are quadratic probing,\n

all very similar to each other. So I will\n

curious, you can go on GitHub and check them\n

or slightly more different is the double hashing.

But other than that, they are really essentially\n

we're going to have a look at the quadratic\n

Alright, here we are inside the code for the\n

let's dive right in. So I have a class called\n

it takes in two generic types K and V. So\n

type. So you're gonna have to specify these\n

hash table for quadratic probing. So I have\n

to need. The first is the load factor, this\n

that we're willing to tolerate the current\n

we're willing to tolerate the modification\n

two instance variables that keep track of\n

the key count, which tracks the number of\n

table. Now, since we're doing open addressing,\n

inside an array. So instead of having one\n

decided just allocate two different arrays,\n

the code a lot easier. And shorter. Actually,\n

to be using, or rather setting when we call\n

was talking about in the last video. This\n

deletions. So every time we delete an entry,\n

we know this tombstone object is unique. Alright,\n

So whenever you want to initialize a hash\n

these constants. So this is a default load\n

it up as you like. So you can initialize it\n

constructor. So let's have a look. So the\n

check if the user pass in some sort of a weird\n

then set the max value for the load factor,\n

that the capacity is a power of two, I need\n

going to be with this method next to power.\n

That is just Above this current number, or\n

itself is a power of two, so we don't have\n

to be a power of two, then we compute the\n

the capacity and initialize our tables. Alright,\n

probing function I chose. So P of x, so we\n

x squared plus x divided by two. So this is\n

So given a hash value, it essentially strips\n

So it dumps our hash value inside the domain,\n

a clear method. And this is pretty self explanatory.\n

hash table and start fresh. Some helper methods\n

tables empty. And put add an insert or essentially\n

insert method. This inserts a key value pair\n

the key already exists. All right, we don't\n

an exception. If the number of buckets use\n

we're tolerating, we're going to resize the\n

we want to calculate the hash value from the\n

you can override this for your particular\n

Jane xR. So I is going to be the current index\n

to be bouncing around this I value is going\n

the first tombstone we encounter if we encounter\n

going to be using this for an optimization\n

to one, initially. Okay, so this is a do while\n

Alright, so first, we check in the key table,\n

is equal to minus one, that means we haven't\n

this tombstone. Okay, so this next check checks\n

meaning there's a key inside of it. So we\n

table. So that's what this does. It compares\n

trying to insert this key. And if j is equal\n

then just update the value. If we've hit a\n

the tombstone. And at the modification, count,\n

was there before just just in case why use\n

so we can do an insertion. So j is equal to\n

so far. So increment number of use buckets\n

pair. Otherwise, we have seen a tombstone\n

where the element is inserted where the deleted\n

of AI. So here we're inserting an AI, but\n

we're gonna return null because there was\n

a loop, so we get through all these if statements\n

need to keep probing we had a hash collision,\n

in it. So we need to probe so we need to offset\n

probing index or the probe. Addition and increment\n

to the next spot. And we'll do this while\n

so contains key and has key, just check if\n

do this, I'm being pretty lazy. And I'm just\n

instance variable in there called contains\n

key is inside our hash table or not. Because\n

have essentially the same code. So that's\n

at the get method since it's getting used\n

the original hash index is equal to the hash\n

do all the same stuff, or mostly except set\n

flag to be true, when we identify that the\n

our else condition is just shorter, we return\n

a new element, and set the contains slide\n

Remove method is actually quite a bit shorter.\n

is now find the hash set x to be equal to\n

too much. So we don't have a j position. So\n

probe until we find a spot. So for every loop,\n

position if this loop gets completed, so here's\n

skip over those. So if this happens, if the\n

return now. Otherwise, the key we want to\n

this check, because we check if it's null\n

So decrement, the key, count up the modification\n

here, and just wipe whatever value is in there.\n

the Remove method, and then just return the\n

okay, these two methods are pretty self explanatory,\n

that are contained within our hash table.\n

resize table method. So this is this gets\n

I mean, to grow the table size. And remember\n

implementation, we always need the capacity\n

the capacity is already a power of two, multiplying\n

fine. So we compute the new threshold allocates\n

table, but it's actually going to be the new\n

of interesting maneuver here, I swap the current\n

table, which I call an old table. In order\n

here, we'll get to that. So swap the key tables,\n

count and the bucket count. And the reason\n

the swap, well, the then the new table is\n

the old table. That might sound confusing,\n

insertions on or the pointer to it. Alright,\n

if we encounter a token or a pointer that's\n

So because we're avoiding reinserting tombstones,\n

even though our table might have been cluttered\n

all of them here. Alright, so that's that\n

at this yourself. It's just looping through\n

That's a pretty standard to string method.\n

open addressing. Today, I want to talk about\n

binary index tree, and you'll see why very\n

because it's such a powerful data structure.\n

really simple to code. So let's dive right\n

video series, and just some standard stuff.\n

structure exists, analyze the time complexity,\n

So in this video, we'll get to the range query,\n

and how to construct the Fenwick tree in linear\n

but I'm not going to be covering that in this\n

the motivation behind the Fenwick tree. So\n

and we want to query a range and find the\n

do would be to start at the position and scan\n

all the individual values between that range.\n

it'll soon get pretty slow, because we're\n

However, if we do something like compute all\n

do queries in constant time, which is really,\n

zero to be zero, and then we go in our array\n

sum, we get five and then five, plus or minus\n

is eight, and so on. So this is an elementary\n

out prefix sums. And then if we want to find\n

then we can get the difference between those\n

time thing to compute. The sum of the values\n

really great. However, there's a slight flaw\n

to update a value in our original array A,\n

Well, now we have to recompute all the prefix\n

recalculate all those prefix sums. And to\n

Chu was essentially created. So what is the\n

that supports range queries on arrays and\n

we won't be covering that in this video. So\n

dates are logarithmic. range, some queries\n

but you can't say add elements to the array\n

so let's look at how we can do range queries\n

is that unlike a regular array, a family tree,\n

rather for a range of other cells as well.\n

for other cells depending on what The value\n

representation. So on the left, I have a one\n

very important. And I, on the side of that,\n

of the numbers, you can clearly see what they\n

index 12, its binary representation is 1100.\n

most bit. So that is at position three, and\n

responsible for we're going to say two to\n

cells below itself. Similarly, 10, has a binary\n

least significant bit is that position two.\n

And 11 has this thing fit in there position\n

So here, I've outlined the lease Sydney, leasing\n

for all the odd numbers, which are just responsible\n

indicates, the blue bars don't represent value,\n

And that's really important for you to keep\n

arranged responsibility to now the cells have\n

all these ranges of responsibilities or powers\n

16 for 16 cells. So now, how do we do a range\n

in this standard array, but rather this weird\n

answer is, we're going to calculate the prefix\n

eventually going to allow us to do a range\n

sums, just like we did for a regular array,\n

going to start at some index and cascade downwards\n

I mean. So for example, let's find the prefix\n

the prefix sound from index, one to seven,\n

tree is inclusive. So if we look at where\n

the array at position seven. And then we want\n

us is six, and then four. Notice that we were\n

then we move down to six. And then from six,\n

responsibility to, and then we're at four\n

that brings us all the way down to zero. And\n

we are all the way down to zero. So the prefix\n

plus the array index six plus the array index\n

for index 11. So we always start at where\n

to cascade down. So the cell directly below\n

to so we're gonna go down to

so that's eight and an eight brings us all\n

And one last one, let's find the prefix son\n

four as arranger responsibility of exactly\n

so we can stop. Okay, let's pull this all\n

i and j. So let's calculate the interval sun\n

going to calculate the prefix sum of 15 and\n

of 15. And then we're going to calculate the\n

not going to calculate up to 11. inclusive,\n

a lot. Okay, so if we start at 15, then we\n

arranger responsibility of one, subtract one\n

responsibility if two, because the least significant\n

and then keep cascading down. So the prefix\n

plus 12 plus eight. All right, now the prefix\n

to start at 10. Now we want to cascade down\n

to subtract two from 10, we get to eight.\n

of eight, so cascade down, so eight minus\n

sum of all the indices of 15 minus those of\n

range sum. So notice that in the worst case,\n

which is all the ones and these are the numbers\n

of two, minus one. So a power of two has one\n

one, then your whole bunch of ones here. So\n

are ones. And those are the worst cases. So\n

say 15, and seven, both of which have a lot\n

base two of N operations. But in the average\n

going to implement this in such a way that\n

this is like super fast. So the range query\n

like literally no code, the range query from\n

so I'm going to define a function called prefix\n

down operation. So we started I and while\n

up the values in our final tree. And we're\n

bit. And we're all we're going to keep doing\n

can return the sum. So the range query manages\n

really neat little algorithm. I want to talk\n

let's dive right in. But before we get to\n

the Fenwick tree range query video. And I\n

the Fenwick tree is set up and how we're doing\n

your brain on how we actually did a prefix\n

what we did was, we started at a value at\n

continuously removed the least significant\n

so let's say we started at 13 or 13, at least\n

and we got 12. And then we found out that\n

So we remove four and then at least thing,\n

zero. And once we reach zero, we know that\n

analogous to this, instead of removing, we're\n

as you'll see. So for instance, if we want\n

to find out all the cells which are responsible\n

for a range of responsibility. So if we start\n

and add it to nine, and we get 10. So 10,\n

two, then we add it to 10, then find the least\n

it's 16. And then we would do the same thing,\n

know to stop. So if I draw a line outwards\n

ones I have to update. So remember, those\n

So the lines that I hit are the ones that\n

Okay. So 14, add some constant x, at position\n

need to modify? So we start six, and we find\n

we get eight, find the least significant bit\n

out from sex, then indeed the cells that I\n

updates for our Fenwick tree are that we need\n

the algorithm is really, really simple. So\n

array of size n, then while I, so I supposition\n

less than n, we're going to add x to the tree\n

significant bit of AI. And that's it, where\n

AI. And there are built in functions to do\n

at some source code. Alright, so that was\n

construct the Fenwick tree. Let's talk about\n

how to do range queries and point updates\n

seen how to construct the Fenwick tree yet.\n

you can't understand the Fenwick tree construction\n

updates work. Alright, so let's dive right\n

of a Fenwick tree. So if we're given an array\n

into a Fenwick tree, what we could do is initialize\n

all zeros and add the values into the Fenwick\n

get a total time complexity of order n log\n

do this in linear time. So why bother with\n

we're going to be given an array of values\n

a legitimate Fenwick tree, not just the array\n

going to propagate the values throughout our\n

And we're going to do this by updating the\n

as we pass through the entire tree, everyone's\n

a fully functional Fenwick tree at the end\n

idea. So you You propagate some thing to the\n

that parent propagate its value to its parent\n

almost delegating the value. So let's see\n

that. So if the current position is position\n

our parent, let's say that is J, and j is\n

of AI. Alright, so if we start at one, well,\n

the parent is at position two. So notice that\n

going to add two for the value of i, which\n

seven. Now, we want a bit position two. So\n

two. So two, plus at least significant bit\n

for two are immediately responsible for two.\n

who is responsible for three? Well, that's\n

value at index three. Now, who's responsible\n

So go to position eight, and add the value\n

So in our five, and then you see how we keep\n

cell responsible for us, now seven is updating\neight.

now, nobody, oh, eight doesn't have a parent.\n

only has 12 cells, but the parent that would\n

out of bounds. So we just ignore it. It's\n

I is nine nines, least significant bit is\n

So keep propagating that value 10s, parent\n

the same sort of situation we had with eight\n

we ignore it. So the values that are there\n

And with these values, we can do range queries\n

that we had. So let's look at the construction\n

this, we will have a look at some source code\n

language that I'm not using, this can be helpful.\n

into a Fenwick tree. Let's get it's about\n

actually clone or make a deep copy of the\n

manipulate the values array while you're constructing\n

because we're doing all this stuff in place.\n

I at one and go up to n and then compute j\n

significant bit of I do an if statement to\n

be less than or equal to and actually not\n

based and in a Fenwick tree. Yeah, I'm pretty\n

let's have a look at some Fenwick tree source\n

can find it at this link which I'll put in\n

data dash structures, and the Fenwick trees\n

tree folder. So let's dive right in. I have\n

Alright, so this source code is provided to\n

layer two, any language you're working. So\n

constructors. One, they'll create an empty\n

populate yourself. And another one, which\n

in the last video, and constructs the Fenwick\n

the constructor you want to use, and not the\n

either or. So one thing that you guys should\n

thing needs to be one based. In the last video,\n

go less than or less than or equal to the\n

on whether your array is one based or zero\n

one based in which case, it would be less\n

right. But other than that, so this is just\n

propagate the value to the parent. So that's\n

So pretty simple stuff. So this is probably\n

least significant bit method. And it's going\n

bit for some integer i. So this bit magic\n

the least significant bit value. Something\n

here, which uses Java's built in method find\n

However, using a Rob manipulation, like this\n

faster. Okay, so the prefix sums, this is\n

allows you to compute the prefix sum from\n

done one based. So this would do the cascading\n

a sum equal to zero, and add the values of\n

cascading down. And this line line 55 is equivalent\n

of I, which is a lot more readable than this\n

clears that bit. But you want to use as much\n

tree fast, even though it's already really,\n

you use, the less operation or machine level\n

program is going to be so much faster. Okay,\n

then we can call the prefix some methods right\n

So that's easy. So adding, so this is from\n

So we k can be positive or negative, that\n

to do as for AI, you're going to update everyone\n

that are responsible for you. And for each\n

K. And then you're going to propagate up to\n

least significant bit, and you're going to\n

at some valent index. And this additional\n

the index is equal to k, this might sometimes\n

and then call the Add method. So pretty simple\n

and half of it is comments. So this is a really\n

And interesting topic I want to talk about\n

powerful data structure to have in your toolbox\n

Stuff like arrays are a relatively new data\n

due to the heavy memory consumption needs\n

and talk about just what a suffix is. For\n

at the end of a string. For example, if we\n

of the string horse are, we are able to come\n

e, s, e, r, s, e, and so on. Now we can answer\n

is a suffix array is the array containing\n

see an example of this. Suppose, you want\n

On the left, I constructed a table with all\n

that particular suffix started in a string\n

all the suffixes in lexicographic order in\na table.

The actual suffix array is the array of sorted\n

to actually store the suffixes themselves\n

original string. This is an ingenious idea,\n

of the sort of suffixes without actually needing\n

All we need is the original string and the\n

suffix array is an array of indices which\n

for a bit of history on the suffix array,\n

to be a space efficient alternative to a suffix\n

a compressed version of another data structure\n

the suffix array is a very different from\n

about virtually anything, the suffix tree\n

such as a longest common prefix array, which\n

video, we're going to talk about perhaps the\n

with the suffix array. And that is the longest\n

array. The LCP array is an array where each\n

suffixes have in common with each other. Let's\n

show what the LCP array is, is to do an example.\n

the LCP array is, for the string, A, B, A,\n

do is construct the suffix array for our string\n

Notice that the very first entry that we placed\n

is zero. This is because this index is undefined,\n

our LCP array, let's begin by looking at the\n

they have in common with each other. We noticed\n

index of our LCP array. Now we move on to\n

have an LCP value of two and the next two\n

zero and the next to only have one character\n

and lastly, only one character in common.\n

highlighted in purple. In summary, the LCP\n

To sort of suffixes have in common with each\n

how much information can be derived from such\n

noting is that the very first index in our\n

LCP array as an integer array, by convention,\n

So that doesn't interfere with any operations\n

And this is fine for most purposes. Lastly,\n

to construct it very efficiently. There are\n

how to construct the LCP array, which run\n

in n log n time, and even in linear time.\n

of suffix arrays and LCP arrays, and that\n

There are a variety of interesting problems\n

that require you to find all the unique substrings\n

time complexity of n squared, which requires\n

the substrings of the string and dump them\n

the information stored inside the LCP array.\n

space efficient solution. I'm not saying that\n

substrings because there exists Other notable\n

with Bloom filters. Let's now look at an example\n

look at an example of how to find all the\n

A for every string there are exactly n times\n

of this I will leave as an exercise so listener,\n

notice that all the substrings here, there\n

the repeated substrings there are exactly\n

use the information inside the LCP array to\n

were the duplicate once in the table on the\n

AZ az a. Remember what the LCP array represents,\n

the original string share a certain amount\n

value at a certain index is say five, and\n

those two suffixes, in other words, there\n

two suffixes, since they come from the same\n

LCP position at index one, we see that has\n

string is the first character in a so we know\n

values three, so there are three repeated\n

ACA, the next interesting LCP values to for\n

substrings. Here we can eliminate z, and z\n

way of counting all unique substrings. We\n

is n times n plus one over two. And we also\n

is the sum of all the LCP values. If this\n

examples and play around with it. If we go\n

az, az a and we set n equal to five, which\n

the correct answer. have nine by punching\n

substring values summed up in the LCP array.\n

challenge concerning counting substrings,\n

to the Caris online judge for some practice.\n

array and LCP array available on GitHub github.com\n

There is a really neat problem called longest\n

the K common substring problem, which is really\n

state the problem and then discuss multiple\n

How do we find the longest common substring\n

being anywhere from two to n, the number of\n

strings, s one, s two, and s three, with the\n

a minimum of two strings from our pool of\n

substring between them. In this situation,\n

know that the longest common substring is\n

be multiple. The traditional approach to solving\n

dynamic programming, which can solve the problem\n

of the string lengths. Obviously, this method\n

avoid using it whenever possible, a far superior\n

is to use a suffix array, which can find the\n

sum of the string lines. So how do we do this?\n

longest common substring problem? Let's consider\n

two and s three. What we will first want to\n

larger string, which I will call t, which\n

we must be careful and place unique Sentinel\n

this for multiple reasons. But the main one\n

of suffixes when we construct the suffix array.\n

settle values need to be lexicographically\n

in any of our strings. So in the ASCII table,\n

sign are all less than any alphabetic character\n

so we're good in doing the concatenation.\n

construct the suffix array for tea. This procedure\n

linear suffix array construction algorithm.\n

both the LCP array values on the leftmost\n

would appear in the suffix array on the right\n

color to match it with the original string\nit belongs to.

In this slide, you can see that the suffixes\n

the top because they were lexicographically\n

And this is to be expected. For our purposes,\n

them into the string t ourselves. So back\n

longest common substring of K strings? Given\n

LCP array constructed? The answer is, we're\n

colors whom share the largest LCP value. Let's\n

equals three We have three strings, this means\n

can achieve a maximum of two, if we sell the\n

that each of them is a different color, meaning\n

And that the minimum LCP value in the selected\n

first entry in the window. This means that\n

string ca of length two, which is shared amongst\n

do another example. But this time, let's change\n

equals two, we want to have two suffixes of\n

prefix value between them. In this case, there\n

B CA, with a length of three shared between\n

we've covered only some trivial cases, things\n

colors you need are exactly adjacent with\n

this will be to use a sliding window technique\n

Here's what we'll do at each step, we'll adjust\n

window contains exactly k suffixes of different\n

correct amount of colors, we'll want to query\n

In the picture below, you can see that this\n

the LCP array for that window is two, again,\n

the minimum value for that window is two,\n

the prefix a G, which has length of two, as\n

on how we are actually going to perform the\n

current window we are considering. Turns out\n

it can be solved in a variety of ways. Since\n

just any arbitrary range query, we can use\n

range query problem to obtain the value we\n

a minimum range query data structure such\n

queries on the LCP array. This is theoretically\n

implement in my opinion. So to implement the\n

data structure to keep track of

the colors in our window, I recommend using\n

left, I drew a table to indicate how much\n

window, a valid window will require at least\n

than zero. In the example that we'll follow,\n

all three colors will need to be present in\n

query I mean, querying the LCP array for the\n

possibly updating the best longest common\n

can see that our window is missing some blue.\n

is to expand the window down. And when we\n

down. So let's expand our window downwards\n

and enough of each color to do a valid query.\n

the longest common substring for the window\n

the string a G. Now since we have enough features\n

one green suffix, and we still have at least\n

a query to find out that we get the same result\n

more. And now we don't have enough green.\n

we need to do is expand the window downwards\n

was a green suffix right there. And we can\n

longest common substring value found so far.\n

is only of length one. So the longest common\n

which is not as long as the longest common\n

length three, so we can ignore this one and\n

and we're short one color, and that is red.\n

suffix. So we expand and find a blue suffix.\n

searching the expand Finally, green suffix,\n

reached. This video is getting a little long,\n

next video, we'll look at a full example of\n

meantime, if you're looking for a challenge\n

make sure to check out the life forms problem\n

for an implementation of longest common substring\n

to check out my algorithms repository@github.com\n

going to finish where we left off in the last\n

example solving the longest common substring\n

For this example, we're going to have four\n

I have also selected the value of K to be\n

of two strings of our pool of four to share\n

them. I have also provided you with a concatenated\n

solution at the bottom of the screen. In case\n

out for yourself. The first step in finding\n

of our four strings is to build the suffix\n

on the right side and the left side, respectively.\n

substring algorithm, notice the variables\n

and a window LCS values will track the longest\n

values for the current window. And the LCS\n

values so far. So let's get started. Initially,\n

the window to contain two different colors.\n

do not meet this criteria. As I expand down,\n

one color, I expand on again and still one\n

and now we arrive at a blue suffix. And here\n

window. However, our query isn't fruitful\n

is zero. So there's no longest common substring\n

like we do now, we decrease the window size\n

nothing interesting. Decrease the window size\n

The current window contains a longest common\n

common substring BC and added to our solution\n

because we meet the color requirement. Our\n

is two, so we need two different color strings.\n

has happened because we find an LCP value\n

best value. So we update the solution set\n

BC, which is one character longer. Now we\n

was now too small, so we expand the LCP value\n

the window size. Now expand to meet the color\n

that doesn't beat our current best, which\n

to meet the core requirements, so expand,\n

and LCP value of one for this window range.\n

an LCP value of two we're getting closer to\n

have to shrink and like let go. Now expand.\n

We have a window RCP value of three which\n

saying that, the CDE our newfound, longest\n

of the same length, we keep both in the solution\n

interval because we meet the color requirement.\n

expand again, our LCP window value is zero.\n

value of one here, that's not good enough.\n

Okay, we might be getting closer, but we meet\n

to meet the color requirement. These two strings\n

now shrink. Now we've reached the end and\n

problem with a four strings and a k value\n

and shrinking, I want you to notice that each\n

I only ever moved one of the endpoints downwards.\n

know that the number of Windows has to be\n

that we have. And the number of suffixes that\n

come to the conclusion that there must be\n

which is really good. Because we want our\n

going to be on an efficient way to solve the\n

The longest repeated substring problem is\n

in computer science, lots of problems can\n

important that we have an efficient way of\n

squared time and lots of space. What we want\n

inside the longest common prefix array to\n

Let's do an example what is the longest repeated\n

free to pause the video and figure it out\n

which is the longest substring that appears\n

the longest repeated substring. Here you can\n

And now you can see the second repeated instance\n

are disjoint and do not overlap. In general,\n

substring. Now let's solve the problem using\n

generated on the right hand side. I'll give\n

the LCP array in case you notice anything\n

substring. Now that you already know what\n

for in the LCP array is the maximum value.\n

know that the suffixes are already sorted.\n

longest common prefix value, then they share\n

We also know that if the LCP value at a certain\n

shared between the two adjacent suffixes is\n

between two suffixes, each of which start\n

again, is Abracadabra. Since our LCP value\n

from the suffix abracadabra forms one part\n

the suffix above it which shares the LCP value\n

in that longest repeated substring. Now, I\n

can you find the longest repeated substring\n

you did, you will find out that you not only\n

longest repeated substrings. Since there can\n

for a single largest value, but all largest\n

you can see that we'll want the first three\n

ba, and for the second maximum, we'll want\n

ba, ba. Visually, for this first, longest\n

at the start, and then a BA again, closer\n

found using the second largest common prefix\n

and the second one just next to it. That is\n

the suffix array and the LCP array have already\n

on campus if you want to tackle a longest\n

you to have an efficient solution. Today,\n

most important types of trees in computer\n

trees. Balanced Binary search trees are very\n

tree because they not only conform to the\n

also balanced. What I mean by balanced is\n

logarithmic height in proportion to the number\n

because it keeps operations such as insertion\n

is much more squashed. In terms of complexity,\n

operations, which is quite good. However,\n

the tree could degrade into a chain for some\n

numbers. To avoid this linear complexity,\n

in which the worst case is logarithmic for\n

Central to how nearly all Balanced Binary\n

balanced is the concept of tree rotations,\n

video. Later, we'll actually look at some\n

to see how these rotations come into play.\n

binary search tree implementations is the\n

tree invariant and tree rotations. A tree\n

you impose on your tree, such that it must\n

that the invariant is always satisfied a series\n

get back to this concept and fitting variants\n

so much for now. Right now we're going to\n

invariant is not satisfied. And to fix it,\n

A. Assuming node A has a left child B, we\n

node A was and push node A down to become\n

this, in my undergrad, I was Mind blown. Literally,\n

of being illegal that we should be allowed\n

tree. But what I've realized since is that\n

Since we're not breaking the binary search\n

the left tree, you'll discover that in terms\n

than node B is less than E is less than a\n

tree and remark that well, this is also true.\n

is a valid operation. First, you have to remember\n

binary search trees, meaning that the binary\n

node and the values in the left subtree are\n

the right subtree are all greater than the\n

what the tree structure itself looks like.\n

binary search tree invariant holds. This means\n

rotate the values and nodes in our tree as\n

environment remains satisfied.

Now let's look at how these rotations are\n

the rotations are symmetric, or will only\n

to figure out the left rotation on your own.\n

Notice that there are directed edges pointing\n

may or may not exist. This is why there is\n

have a parent node p, then it is important\n

rotation. In either case, we start with a\n

arrow, then we'll want a pointer to node B.\n

to B's right child, then change B's right\n

done a right rotation. If we rearrange the\n

However, notice that there's a slight problem.\n

parents left or right pointer would still\n

B is A's successor after the rotation. So\n

step is usually done on the recursive call\n

function. We just finished looking at the\n

and the right child nodes. But in some Balanced\n

convenient for nodes to also have a reference\n

rotations because now instead of updating\n

Let's have a look. In this case, where we\n

a sense, doubly linked. We start off with\n

we'll want to do is also reference node B\n

around pointers. Next we'll adjust the left\n

B's right subtree. Of course, throughout this\n

you can add an extra if statement to check\n

mistake to assume B is right subtree is not\n

before setting B's right child's parent to\n

of me. So set meas right pointer to reference\n

be the last thing we need to do is adjust\n

these parent pointer a reference P. And now\n

left or right pointer reference the successor\n

is not now because it might not exist. This\n

readjust the tree, you will see that we correctly\n

in doing this right rotation. And it's a very\n

to do it in such detail. Today we're going\n

tree in great detail. We'll be making use\n

in the last video. So if you didn't watch\n

before we get too far, I shouldn't mention\n

of many types of balanced binary search trees,\n

and search operations. something really special\n

type of Balanced Binary Search Tree to be\ndiscovered.

Then, soon after a whole bunch of other types\n

emerge, including the two three tree, the\n

main rival the red black tree, what you need\n

the avielle tree balanced. And this is the\n

of a node is the difference between the height\n

I'm pretty sure the bounce factor can also\n

the right subtree height. But don't quote\n

what I'm about to say, and may also be the\n

about what way to do tree rotations on various\n

let's keep the bounce factor right subtree\n

because people get this wrong or define it\n

as the number of edges between x and the furthest\n

tree has height zero, not height one because\n

avielle tree that keeps it balanced is forcing\n

minus one zero or plus one. If the balance\n

to resolve that with tree rotations. In terms\n

to actually make the avielle tree work. What\n

stores. This value must be comparable. So\n

it goes to the tree. Then we'll also need\n

as well as the left and the right child pointers.\n

these values. So keep that in mind. So a slider\n

node must always be minus zero or plus one.\n

the case where this is not true? The answer\n

factor must be either be plus two or minus\n

rotations. The rotations we need to perform\n

be broken down into four distinct cases. The\n

call left heavy, and there are two left child\n

all we need to do is perform a right rotation\n

case is the left right case where you have\n

child. To fix this, you do a left rotation\n

the left most image, what happens then is\n

we just saw, which we can resolve with a right\n

right case, which is symmetric to the left\n

we do a left rotation about the green note.\n

which is symmetric to the left right case.\n

about the yellow node on the left most image\n

case, and then do a left rotation about the\n

Next, I want to show you some pseudocode for\n

not all that obvious or easy. This first method\n

method, which returns true or false depending\n

or not. For simplicity, we're going to ban\n

value already exists, or the value is no,\n

does not know, and it doesn't already exist\n

insert method, where we pass in a pointer\n

insert. The private recursive method is also\n

we simply return a new instance of the node\n

we get to compare to a value with the value\n

node to determine if we should go on the left\n

call back, we call the update method which\n

for this note, and lastly, we rebounds the\n

a look at the update enhance method. And what\n

updates the bounce factor and height values\n

the node, we get the maximum height of the\n

Notice that I initialize the left and the\n

this is because it will cancel out with a\n

the node has no sub trees giving the correct\n

the balance factor for this node. By finding\n

balanced method is slightly more involved\n

factor has an illegal value of minus two or\n

two, then we know that the node is left heavy,\n

To determine if we're dealing with a left\n

thing if the balance factor is plus two, except\n

right left case. If the bounce factor is not\n

bounce factor is going to be either plus one,\n

cases, we don't need to do anything inside\n

all we do here are calls to the left rotation\n

the last video. Also notice that the left\n

left and right Right right case methods respectively,\n

rotation. In the last video, we looked at\n

dealing with any vl tree In this video, we\n

the height and bounce rate values for the\n

this is a subtle detail you must not forget,\n

will be inconsistent with the left rotation\n

able to figure it out pretty easily. In this\n

elements from an avielle tree. And what you'll\n

avielle tree is almost identical to removing\n

So for the majority of this video, we're going\n

from a binary search tree in the very end\n

So let's get started. So just for review,\n

binary search tree in detail. So we can generally\n

In the find phase, you find the element you\n

and then replace it with a successor node,\n

maintain the binary search tree invariant.\n

we're searching for the element in the tree\n

in happen. First is we hit a null node, in\n

for doesn't exist. Our comparateur returns\n

we want to remove, the comparative value is\n

for, if it exists, is going to be found in\n

is greater than zero, in which case the value\n

let's do an example of finding nodes in a\n

for a 14, well, we should have a reference\n

So we compare 20 and 14, and we know 14 is\n

We know 14 is greater than 10. So we go on\n

15. So you're on the left subtree. 14 is greater\n

there we found it, the node we were looking\n

that doesn't exist. So let's try and find\n

we go to the right subtree, because 26 is\n

because 26 is less than 31. And once we're\n

then discovered that 26 does not exist in\n

it exists, we need to replace that node with\n

that if we just remove the node without finding\n

tree. And when we're looking for a successor\n

will happen. Either were a leaf node, in which\n

has no left subtree the node to remove has\n

both the left subtree and right subtree. We'll\n

first case where the node to remove is a leaf\n

side effects. The successor node in this case\n

a remove node eight from this tree, the first\n

the tree. So we'd go down the tree and then\n

Oh, it's a leaf node, so we can just remove\n

where there's only a left or a right subtree.\n

immediate child of that left or right subtree.\n

node down from the node we're removing is\n

than it the case right subtree or less than\n

do an example, suppose we want to remove node\n

nine is in the tree. So start the route and\n

want to remove, which is nine. And then we\n

a left subtree. So the successor node is its\n

so seven. So what we do is we get a reference\nto seven

and then get ready to remove nine. And then\n

by linking it back up to five. And if we rebalance\n

nine has been removed. So the last case, is\n

a left subtree and a right subtree. So the\n

will we find the successor of the node we're\n

surprisingly, the answer is both. The successor\n

subtree, or the smallest value in the right\n

found in either left or right subtree, we\n

a value in the successor node. However, the\n

to remove the duplicate value of the successor\n

strategy to resolve this is to recursively\n

to remove as the value in the successor node.\n

trivial. Let's remove node seven from this\n

start at the root node and discover that in\n

notice that it has two non empty sub trees,\n

successor we either pick the smallest value\n

in the left subtree. Let's find the smallest\n

you will go to the right ones, and then dig\n

the successor node 11, we will copy its value\n

is the root node seven. Notice that now there\n

want unique values in our tree. So to remove\n

recursively call our remove method, but on\n

always result in a case one two or three removal.\n

a right subtree. So its successor is its immediate\n

get ready to remove 11. So we remove 11 and\n

the tree, then we can see that the duplicate\n

we've been waiting for how do we augment the\n

trees. The solution is simple, you only need\n

tree remains balanced and that the bounce\n

On the recursive callback, you invoke the\n

insert video, which ensure that when the node\n

tree remains balanced. It's as easy as that.\n

of the source code for the avielle tree. The\n

in this video can be found on GitHub github.com\n

Make sure you have watched the last three\n

insertions and removals in avielle trees before\n

code I'm presenting. I don't normally do this,\n

avielle tree in action. So I'm here in my\n

of the Java code with avielle tree and then\n

a random tree with some values and notice\n

for the number of nodes that are in it. So\n

expect the tree to be a bit more sloppy if\n

But the avielle tree really keeps the tree\nquite rigid.

So I think we're ready to dive into the source\n

of a recursive avielle tree implementation\n

get started. If you look at the class definition\n

this class takes a generic type argument,\n

And this generic type I'm defining, basically\n

to be inserting inside the tree need to be\n

to be able to insert them and know how to\n

node, which I've created, you can see that\n

node is of type T. So it's a comparable. And\n

variables I'm storing inside the, the node\n

the bounce factor as an integer, the height\n

query the height of a node in constant time,\n

of course, there's going to be the left and\n

notice that this, this node class implements\n

And that's just an interface I have somewhere\n

tree I did on the terminal. So this isn't\n

an ACL tree. And nor are these overrides,\n

tree in the terminal, which is really handy\n

variables at the avielle tree class level,\n

be private, although I'm using it for testing,\n

keeping track of the number of nodes inside\n

Something else I'm also using for testing\n

good to just saying you check yourself to\n

relatively low. Then there are these methods\n

explanatory. This the display method I call\n

The set contains method to check if a certain\n

is the public facing method, which calls the\n

the initial node to start off with. So to\n

hit the base case, then we know that that\n

the current value to the value inside the\n

of either a value less than zero, which means\n

in the left subtree or comparateur is greater\n

is in the right subtree. Otherwise, the means\n

And that means we found the node inside the\n

to insert this value variable, if it's no,\n

just return false. And we return a Boolean\n

an insertion was successful or not. So if\n

tree, then we're going to call the private\n

the root. And also increment the node count,\n

insert something if we're inside this block,\n

Alright, let's have a look at the private\n

meaning we traverse all the way down our tree,\n

this is the position where we need to insert\n

it the value. Otherwise, we're searching for\n

comparator function, then do value compared\n

from the comparable interface at the class\n

dot compare to on a generic type here and\n

is less than zero, then insert in left subtree.\n

here is the extra two lines, you need to add\n

update method to update the bounce factor\n

rebalance the tree if necessary. Well rebalance\n

look at the update method. So this is to update\n

here are two variables that grab the height\n

Then I update the height for this note. So\n

the left subtree or the right subtree height.\n

left and right, we can of course update the\n

the right and the left subtree heights. Okay,\n

the balance method. And inside the balance\n

balance factors are either minus two or plus\n

that our tree is left heavy. And inside the\n

left case or the left right case. And inside\n

case and the right left case. And to identify\n

factor, but on either no dot left or no dot\n

factor of the node is not minus two or plus\n

is either zero plus one or minus one, which\n

We don't have to rebalance the tree if either\n

the note. So now we can look at the individual\n

we'll just perform a right rotation. The left\n

and then call the left left case. So we're\n

this case degrades to that case, after one\n

the right right case and the right left case,\n

one right rotation over here. then here are\n

methods. For the avielle tree. It's very important\n

the height and balance factor values after\n

those values will undoubtedly change. And\n

you do them and you can't Do them in inverse\n

node first to get the correct balance factor\n

now we're at the Remove method. So in this\n

or I should have called it value rather. But\n

it doesn't exist in the tree. So just return\n

in the tree, and then remove it by calling\n

node count and simply return true on the Remove\n

So let's look at this private remove method

where all the action is happening. So if we\n

then we get our comparative value. And we\n

is less than zero. And if so we dig into the\n

we're looking for is smaller than the current\n

method. But passing down no dot left, so we're\n

passing the element as well. Otherwise do\n

down the right subtree. Otherwise, if this\n

know that the comparative value is equal to\n

to remove. And we know from the slides that\n

dot left is equal to null, then we know that\n

right is null, meaning the right subtree is\n

the final tricky case, where we're trying\n

so the left subtree is there and the right\n

that node. And we can either pick the smallest\n

smallest value in the right subtree of the\n

using a heuristic right here to actually determine\n

it's a good heuristic. And here's what it\n

I want to remove nodes from that subtree.\n

larger height, than I want to remove nodes\n

I'm using to choose which subtree I remove\n

I think in general, it'll work pretty well.\n

the left subtree has larger height, than what\n

value by going down the left subtree once\n

to find the max value, and then swapping that\n

is the recursive part, we recurse. on removing\n

we passed in, or rather the element we passed\n

the element, but now we also have to remove\n

duplicate values in our tree, then we basically\n

If the condition goes the other way. Here's\n

you want to call the update and rebalance\n

so that the tree remains balanced even though\n

men and find max method I was calling right\n

depending on the case. And here's just an\n

I need to go over this. And here's another\n

search tree invariant, also not particularly\n

in the main function that will just randomly\n

it. So when I invoked this file on the terminal

this is what executed. So that is an ACL tree.\n

enjoyed writing it up. Today's data structure\n

to prove to be a very useful data structure\n

time ago. So just before we get started, this\n

priority queue videos, which simply go over\n

get by without watching all those videos,\n

those of you who want to know, priority queues\n

for links to those. So what exactly is an\n

priority queue variant, which on top of having\n

also supports quick updates and deletions\n

that the index party queue solves is being\n

the values in your priority queue on the fly,\n

an example. Suppose a hospital has a waiting\n

of attention. Each person in the waiting room\n

with. For instance, Mary is in labor. So she\n

cut, he has a priority of one. James has an\n

Naija stomach hurts, she gets priority of\n

priority is five. And lastly, Leah also has\n

patients by highest priority first. This means\n

by James. However, then something happens\n

she starts vomiting. Her priority needs to\n

served next once they're finished with James.\n

leaves he goes to another clinic down the\n

for. Further suppose that a car wash goes\n

and as a result cracks his head and needs\n

to 10. Once the EDA is dealt with a karsch\n

by layer. As we saw in the hospital example,\n

update the priority of certain people. The\n

lets us do this efficiently. The first step\n

index values to all the keys thus forming\n

persecute to track who should get served next\n

a unique key index value between zero and\n

intended to be bi directional. So I would\n

be able to flip back and forth between the\n

on the index party q will require the associated\n

wondering why I'm saying that we need to map\n

inclusive. The reason for this is that typically\n

under the hood are actually arrays. So we\n

those arrays this will become apparent shortly.\n

often, the keys themselves are already integers\n

to actually construct this bi directional\n

it is handy to be able to support any type\n

can think of an index party queue As an abstract\n

it to support here are about a dozen or so\n

These are deleting keys, getting the value\n

in the priority queue, getting the key index\n

value in the index Burcu, being able to insert\n

specialized update operations increase in\n

end. For all these operations, you need the\n

that you're dealing with. Throughout these\n

as the variable KPI to distinguish it from\n

that. And index party queue can be implemented\n

time complexity is using specialized heap\n

the binary heap implementation for simplicity,\n

all these operations are either constant or\n

party queue. The remove and update operations\n

a mapping to the position of where our values\n

the index party queue per se, I want to spend\n

priority queue data structure which only supports\n

barbecue. Still, both data structures are\n

them the same. Although there are key differences\n

to represent a binary heap is within array\n

If we were to represent the following binary\n

of values. If we know the index of node i,\n

child nodes are by using simple formulas,\n

the right child is two times i plus two, assuming\n

the children of the node at index four? Well,\n

I just gave you to obtain the indices, nine\n

math backwards and figure out with a parent\n

useful if you're either walking up or down\n

value into the priority queue, you insert\n

the bottom right of the binary tree. Suppose\n

violate the heap invariant, so we need to\n

met. So swap nodes five and 12. The heap invariant\n

nodes two and five, and now the tree is balanced.\n

a traditional priority queue. To remove items\n

and then swap it with the last node, perform\n

the swapped value. For this example, suppose\n

five, we don't know where the node value five\n

search for it. This is one of the major differences\n

queue. So start at node zero and process each\n

So we found a node with a value five to actually\n

right most bottom node. Once this is done,\n

node we swapped into five spoon position may\n

to either move it up or down the tree. In\n

of one, which is smaller than its children,\n

to move the node down. That was a quick recap\n

about a traditional party queue. Now let's\n

queue with a binary heap. For the following\n

with different priorities that we need to\n

a queue at a hospital, a waiting line at a\n

is, we'll assume that the values can dynamically\n

person with the lowest priority to figure\n

priority queue to sort by lowest value first.\n

assign each person a unique index value. between\n

index values in the second column beside each\n

person an initial value to place inside the\n

by the index priority queue once inserted,\n

value, you want not only integers as shown\n

or whatever type of data we want. If I was\n

of the key value pairs I have in the last\n

that unlike the previous example, we're sorting\n

with a min heap. If I want to access the value\n

out what its key indexes. And then you will\n

the index priority queue. Here's a good question,\n

index priority queue? Well, first, find Bella's\n

into the values array at position one to find\n

index partner queue. So Bella has a value\n

value for a particular key in the index priority\n

node for a particular key? To do that, we'll\n

namely a position map we can use to tell us\n

key index. For convenience, I will store the\n

the priority queue. As an example, let's find\n

find the key index for Dylan, which happens\n

position map to tell you where Dylan is in\n

and the index seven highlighted in orange.\n

George in the heap? I'll give you a quick\n

All right, so with just about every operation,\n

the key we care about, which is George, then\n

position map and find out the node for George,\n

know how to look up the node for a given key.\n

This inverse lookup will prove to be a very\n

key is associated with the root node at index\n

lookup to figure that out. To do the inverse\n

need to maintain an inverse lookup table.\n

for inverse map. Let's see if we can figure\n

at index two. To do that, simply do a lookup\n

us information about which key index is associated\n

us to retrieve the actual key by doing a lookup\n

case, the node at position two represents\n

make sure you're still paying attention. Which\n

position three. Same as before, find the key\n

key next, figure out the actual key from the\n

that the node at position three represents\n

an index party Q is structured internally\n

want to actually do some useful operations\n

new key value pairs, removing key value pairs\n

associated with a key. These are all possible\n

do it with a regular priority queue insertion\n

update the position map pm and the inverse\n

pairs. Suppose we want to insert the key marry\n

What we first have to do is assign marry a\n

insert the new key value pair at the insertion\n

our arrays at index 12. To reflect that the\n

the heap invariant is not satisfied since\n

than the one at node five. To resolve this,\n

upwards until the heap invariant is satisfied\n

map and the inverse map. by swapping the values\n

array does not need to be touched since it\n

get from the map and not the node index per\n

still not satisfied, so we need to keep swapping\nupwards.

Let's have a look at some pseudocode for insertions\n

needs to provide a valid key index k II, as\n

The first thing I do is store the value associated\n

update the position map and the inverse map\n

has been inserted into the priority queue.\n

the heap invariant is satisfied. Let's take\n

that happens. Here we are looking at the swim\n

functions swap, and let's swap is simply exchanges\n

if no AI has a value less than node j. The\n

It begins by finding the index of the parent\n

we walk up one layer in the tree. If the index\n

the value of the current node is less than\n

with a min heap, and want small values to\n

issue a node exchange simply call the swap\n

node and the parent node, and then update\n

values. I also want to talk about swapping\n

slightly different than a traditional party\n

moving around the values in the array, we're\n

that the values array is indexed by the key\n

the values array can remain constant while\n

map. First, we update the positions of where\n

queue. Remember what the position map is,\n

key index is found at. So we can do a straightforward\n

the key index values and swap indices i and\n

index values associated with nodes iMj and\n

a simple straightforward exchange. Next up,\n

elements from an indexed priority queue. Polling\n

removing is improved from a linear time complexity\n

position lookups are now constant time but\n

is why the heap invariant is still logarithmic.\n

want to pull the root node This is something\n

key value pair with the lowest value in the\n

node with the bottom right node. As we do\n

we can remove the read node from the tree.\n

store the key value pair we're removing so\n

Then clean up the Remove node. Finally, restore\n

node down. Since the left and the right child\n

Let's do a slightly more involved removal\n

party Q. And this example, let's remove the\n

get the key index for Laura, which is the\n

key index is equal to 11. Once we know the\n

locate the node within the heap by looking\n

we want to remove that is the node which contains\n

it with the bottom rightmost node. store the\n

clean up the Remove node. And finally restore\n

node up or down, we're going to make the purple\n

Alright, let's look at some pseudocode. for\n

very short only five lines of implementation\n

to do is exchange the position of the node\n

node, which is always at index position as\n

exchanged the nodes, the rightmost node is\n

to remove was. So we need to move it either\n

we don't know which it will be so we try to\n

swim. Lastly, I just clean up the values associated\n

return the key value pair being removed. But\n

look at the sync method. So we understand\n

select the child with the smallest value and\n

tie. In this next block, I tried to update\n

But first I need to check if the right child\n

and its value is actually less than the one\n

if we're outside the size of the heap, or\n

Lastly, we want to make sure we swap the current\n

value. Lastly, we want to make sure we swap\n

with the smallest value. The last core operation\n

key value pair updates similar to remove those\n

logarithmic time due to the constant time\n

logarithmic time to adjust where the key value\n

want to update the value of the key Carly\n

find the key index of the key we want to work\n

two, then we can use that key index value\n

Of course, the heap invariant may not be satisfied,\n

the pseudocode for updating the value of a\n

in the values array and move the node either\n

so there was nothing too special about updates,\n

increase and decrease key. In many applications\n

often useful to be able to update a given\n

or always larger. In the event that a worse\n

should not be updated. In such situations,\n

form of update operation called increased\n

on whether you want to increase the value\n

the value associated with the key. Both of\n

consist of doing an if statement before performing\n

or decreases the value associated with the\n

just convenience methods that wrap a get operation\n

we're going to look at some source code for\n

we get started, make sure you watch my video\n

the implementation details and why an index\n

All the source code for this video can be\n

slash wm fuzzer slash data structures, the\n

Here we are in the source code for a min indexed\n

in the Java programming language. To get started,\n

that we pass in a type of object which is\n

value pairs within the heap. You'll also notice\n

This is just to be more generic. And all I\n

this heap to have at most two children for\n

general and teach children. So let's look\n

the fun stuff is happening. So let's go over\n

is just the number of elements in the heap,\n

number of elements in the heap, D is the degree\n

number is two. The two arrays, child and parent\n

node, so we don't have to compute them dynamically.\n

maps, which we're going to use to track the\n

values array, which is the array that contains\n

Note that it's very important to notice that\n

not by the nodes, indices, per se. So in the\n

maximum size for our heap. Then we just initialize\n

size of the heap, then I initialize all our\n

parent indices should be. And I also initialize\n

negative one values, then we have a few straightforward\n

So you'll notice that for contains, we don't\n

we pass in the key index. And we're going\n

have a few convenience bounds checking methods\n

such as key has to be in the bounds or throw.\n

is valid. And after this check is done, we\n

by looking inside the position map and checking\n

Then we have things like peak min key index,\n

of the heap. And similarly, Paul min key index

and also peak min value and pull min value.\n

we want to just look at the value at the top\n

the pole version will actually remove it.\n

value pair, we need to make sure that that\n

heap. Otherwise, we're going to throw an exception\n

null. And if it is we throw an exception.\n

the position map and inverse map. Then we\n

we passed in. And then we swim up that node\n

we also increment the size variable so that\n

of pretty straightforward, just do a look\n

slightly more interesting. We make sure the\n

that key exists within the heap. we swap the\n

heap. Then we reposition the new node we swapped\n

or down the heap, we capture the value in\n

can return it later, we clean up the node\n

value. update is also pretty easy. Just make\n

not no, then we get the index for the node,\n

new value, then move it within the heap. And\n

and decrease are just short for decrease key\n

dr heap here. So make sure you take that into\n

sure the key exists and it's not know then\n

in the heap, the values array at the key index,\n

that I didn't call the update method here,\n

the update method, we sink and we swim. So\n

way the node will go whether it's going to\n

key method, we do. Same thing for the increased\n

the less competitor so that the values array\n

passed in is on the right. These are just\n

the slides, we can go over quickly. So to\n

i since we're working with a D reheat, we\n

the one with the least value, this is going\n

sure that i is equal to the value of j and\n

repeat this until we can't sink the node anymore.\n

find the parent of note I which we can just\n

I swap with the parent and keep doing this\n

just looks at all the children of Note II\n

returns its index. Also pretty straightforward.\n

swapped the indices and the position map and\n

have the last function which simply compares\n

convenience methods just because I didn't\n

exceptions everywhere. Just kind of wrap them\n

to make sure that our heat is in these a min\n

the air heap. I hope there wasn't too much\n

give this video a thumbs up if you learn something\n