A&DS S01E02. Data structures. Binary Heap. Heap sort

[Music] so this is the second lecture of our course today we will talk about data structures so our course is about

algorithm and data structures last time we talked about algorithms today we'll

talk about data structures so what is the data structure data structure

and according to its name data structure is some structure that contains some data so we have some i don't know something like this some some structure

something i don't know something like that and this structure contains some good data ah this structure may be very different

from the from one little structure genetic structure so they all are very different and uh what is the common thing that is um structured and it contains some data why do you need some structure for your

data why can't you just get all your data and put it in some big array but create a big array and just just encode your data in some form

and just put it in the beginning why you may need some structure uh that's basically because you want to access your data

so you want to perform some operations say operations for example if you want to build some database you may want to

uh to find some element in the database by your request or if you create some i don't know some application and you want to show

to your user some statistics like show me the average income for the last year so you you want you want to be able to get this statistics first so you want to

just look in your data structure and find these statistics so these operations may be very different and actually these operations define what data structure do you need

so before you uh want to choose what data structure do you need in your algorithm you want to decide which operations do you need so first you need decide what operations do you need

then you decide what data structure do you need no not not opposite and all data structures are like split in divided in some classes

and each class is specified by the operations uh that are possible to make in the data structures of this class for example let's say let's say very

simple let's say array array is a very simple data structure it's not exactly the structure but let's say it's a data structure right

and what operations can you do in array now in array you can like put element in some by index you have index i

you can put element by the index and you can get element by index let's say get element by index i and put element

z by uv so this iteration is simply return i this operation is

a i equal to so let's it's very simple data structure it's actually not exactly the structure it's more like a primitive but

good enough now when you want to create a data structure you specify the operations you need in your data structure and when you analyze

your data structure you want to analyze the time complexity of each operation so for each operation separately we will calculate the time complexity for

example in this case we have two operations gate element and put element and each operation actually is performed in constant time

so for both the separation the time complexity is big of one that's all that's the first data structure we show now data structures and algorithms are

strongly uh related to each other because when you create a data structure you want to make operations and when you make a operation you use some algorithm to make this first

operation and when you design the algorithm you may use some data structure just to make your algorithm faster so after this structure we will

uh learn them in parallel in because uh very closely related to each other good and today we will learn our first

data structure our first stretch will be binary heap

so what is a binary heap so hips ah let's say heat or sometimes it's called it's how it's called

[Music]

it has a second name is so heaps of priority queues are the

class of data structures that can perform the phone operations uh so it contains some set of elements

and you can do two operations sometimes three or four but today we'll learn only two operations just for simplicity sometimes you can make some additional

operations uh we'll learn two operations first operation is insert an element and the second operation will be remove

the minimal element from the hip so remove minimal element a minimal element means that you can compare two elements

so you have some comparator that can compare two elements and there is always one element which is minimal in this set okay so i want to make these two operations

any questions by now oh good now first before we learn how to make a right binary heap we will learn how to make uh like simple data structures which can

do these two operations uh first attempt will be to use the simple array so first attempt

let's use just a simple array uh and say let's say that this array is big enough so we always have enough room to to put all elements

of our set in this array uh so we use first let's see first first ln elements of this array took to

contain this elements of the set so these first n elements from 0 to n minus 1 contain the elements of this set now let's just implement these two operations so first operation is in

inserting elements so we need to insert a new element into our array uh easiest way to do this is just insert it in the last position so we will get this element x put it into the in

the last position here and increment the size of a ratio we'll say insert x like this

and put it into position m and then increment the size for it cool now the second operation second question we need to remove the minimal element remove the minimal element from array we

need to find this minimal element first so how to find the minimal element in the radius i hope you know how to do it so to find the minimal element let's just iterate or all

elements and find the minimal one so let's say let's say j is the index of the minimal element so first j equal to zero then we iterate on all elements from one

to n minus one and see if this element is less than this element

then update the memory okay it looks fine so now we found the the minimal element in

the array so let's say it's somewhere here just somewhere here is the minimal element of the ring now we need to remove this element from

the right and when we remove this element there will be a hole here so so we want always uh to keep all elements close to each other so if we just remove this element

a little bit empty space here uh to fill this empty space we can for example swap this element with the last one so we

will smoke element j with the last element of the array and then remove the last element from the array let's say swap

a j of a n minus one

and then just remove the last element

let's see um and then return

looks fine so we found that first the minimal element then swap the minimal element the last element now the minimum last element is the minimal one

so we decrease n and return this last removed element good you can see something from time to time just to keep it live okay

so this is the first simple implementation of the by of the hip data structure so it is a correct hip data structure we can insert elements we can remove the minimal element

now let's calculate the time complexity of this data structure uh in this structure time complexity is different for these operations

so this operation costs your constant time why we return a n because we decrease that so let me show let me show here so we had

array a here we have element j and we had elements from zero to n minus one so this was the nimal element now we swapped this element with the

last one so we saw these two elements so now we have elements from zero to n minus one

and this is an email element we decrease n so we have this array and minimal element is here so in the end we want to return this

minimal element so minimal element has index n no no no it is this this need to be between spamming in the chat and be

quiet too much so so just don't spam but not to be very quiet there's not so many of you so

i hope it will be fine cool now what is time complexity of this separation in this in this operation you need uh to

make this side this for loop and this for loop it's erased over all elements of the array so the time complexity of this part of the desperation is linear so the

total time complexity of this operation will be bigger so this is the example of uh data

structure when you have two operations and they have different complexity so this this operation have some complexity because one and the inspiration have time connects to be called n sometimes it happens

okay let's try another one so if if we want to perform this separation first so if we want to remove the minimal element uh faster than just in linear time

what can we do ah for example we can maintain this sorted order in our array so if you keep the array sorted then it's easier to find the minimal element because

minimal element will be always in the end of the ring

let's try so second attempt will be to have not just array but the circuitry

cool so if we want to be able to remove the minimum uh it's better to to have sorted array in descending order

so we will have array a sorted in by in decreasing order so the minimum element will be the last one

from zero to n minus one minimal element will be always here now it's easier to make this remove mean because we can just skip

this part minimal element is always in the end so we just decrease m and return

uh huh now when i decrease no the minimal element

has index n minus 1 so after i decrease n the minimum element will have index m i have indices from 0 to n minus 1 so it

was n minus 1 then i decrease n now it is index m good so we can easily remove the minimal element from the

heap and now we need to be able to insert an element and this is complicated because we need to keep the array sorted so when we add element x here

we need to put it in the correct position so we need to put it in such position that the ray remains sorted ah let's say easiest way to do it is like

like we did in the previous lecture like when we had insertion sort we'll put it here and then we'll move it to the left until it reaches the correct position

let's say so we put it in the last position and then move it to the left so let's say i equal to m minus 1 so i is the index of

element x and now while i is greater than 0 and ah it is

it is greater than the previous element i just swapped them and decrease i again this procedure is the same as we used in previous lecture lecture when we had

insertion server we put the new element and then move it to the left until we have element this is greater than this element so after this after this while this

array will remain sorted good so what is time complexity here the time complexity of remove mean is obviously constant

but now the time complexion of this insertion is is is big because here you need to make this while and

the time complexion of this while is again linear so at least time complexity

okay now we have two options we can make fast insertion but slow remove or we can make fast remove but slow insertion

uh in the in real algorithm you can choose between these two structures but actually they are both pretty slow because in in real algorithm you

you have a big number of insertions and big number of removal so the total time complexity of the algorithm if you use this data crusher will be slow uh so now we will implement the third

version now the correct version correct binary heap uh and in the correct binary heap will have both these 10 complexities less than big o of n

and actually the time complexes here will be big o of logarithmic show it here so we have two versions let's see that

we have insert and remove first version uh this one we have insertion in constant time this second version is end here and one here

and now we'll make the correct binder here incorrect binary heap we have both the separation work and locally in logarithmic so we have a version this spoiler will

we will discuss it now so both this operation will have logan time uh it's hard to compare to data structures so for example if you compare these today

structures so this operation is faster but this operation is slower that's usually what happens when you compare to this structure but when you decide what the structure you can use in your algorithm

you need to calculate the number of operations you need to accept if you want to make an operation let's say let's say we have some data some algorithm and we need to perform

like n insertions and removals that what we will will be the time complexity

so in in these two in this case we have n insertions it cost you end time and then you have n removals each cost you end time so total tank of this will be n plus n square

and here you have n insertions so we have n square here plus m and here we have n log n plus n log n and now you see that this data structure is better than this of this function

because here we have n log n time complexes here and here we have n squared and complexity so if you have this number of operations you can compare in and see which data structure is

better usually you have like situation like this so this is the common situation usually you have uh about equal number of insertions and removals so the that's usually what happens so

usually this date rush is better than these two because when you insert the element in the hip you usually you need to remove it at some point so usually you have the same number of

insertions and removals okay no questions by now okay let's go

so now we'll discuss the binary heap

the binary heap looks like like this you have a binary tree

that's enough you have a binary tree what is a binary tree it is the set of nodes so each node have

at most two children nodes so we have one child is left child and another child is right child and this binary tree for for the for the binary heap will always look like this it will be

almost complete so all layers of the binary tree will be full except maybe the last layer in the last layer

you have some elements from the left but maybe not all elements to the right just because you don't have enough elements so for example if you have one

two three four seven if you have ten elements in your hip the binary 3 will always look like this so the structure of binary 3 is fixed by

this number n if you have 10 elements you will always have binary 3 like this now each node of these three contain one element of the set so you have ten elements in the set you

have these three and each node contains one element it did may be hard if you don't know how to program problems

so if you are new to programming maybe first thing you need to do is to learn some programming language and just learn how to how to get the simple algorithms like and let's learn

how to solve some simple problems go so now each node of the tree should contain one element of the set and we want to be able to find the

minimum so to be able to find the minimum we will keep this tree in some

almost sorted order um uh this is called the hip uh property so the property of the heap is that each element

is less or equal than it is children elements so these elements are less than this element and this element and this element and this one and this is which programming language should they

begin with it's this doesn't matter actually you can choose any programming language and just start learning this it's more than enough information in the internet how to learn programming

languages go so now we want to put our elements in this tree so that for each pair of nodes

these elements will be less or equal than this one for example let's put some elements here let's say we have 2 5

10 i don't know 7 9 uh 13

8 26 and 15 here and 19 here

so this is the correct binary heap we have all 10 elements in this nodes of the binary team and for each node it is greater or equal

than the parent node nice okay now how can we store this element in our programming language

there are different ways to store the binary tree in the programming language usually when you have binary three you have something like this you have like class note and you have

like pointers to the left child and the right child so have some some some complicated data structure but

in our case uh this structure of the tree is fixed so the tree of size 10 is always look like this so we don't need to just remember which element

is the sum of which element because we always have this three looks like this so instead of having some complicated structure of nodes we will just

uh enumerate all the nodes in right order so we'll enumerate all the nodes from top to bottom from left to right so this node will have index 0 1

2 three four five six seven eight and nine and now we'll just simply create an array of size 10

and put these elements in in this array

are using these indices so let's have this array and we have

elements 2 5 10.

7 30 15 90

9 6 nine and ten switch well it doesn't matter so we only need

uh the the relation between element and its parent so these two elements have no relation so they they must may be in

in any order and like any other so this element in this element made going different over and so on so we only need to maintain the relation between the element and its

parent sorry okay now to uh start saying this three in in the programming language

we'll have this one array uh let's call it array h

from the heap and to access the element of the tree we just get its index so for example we need we want to access this element

it has index 4 so we go into this array find the fourth element with this element linux form we just take this index go into into to array find the element

of this index and this is the element of this node good now we will need two traverse listings so we need to move to the parent or move to the child nodes

so how can we move uh around the three using this array that's quite simple so for example if we stay in some nodes so we stay in

some node i and we want to move to the left child of this node to this node ah we don't have the link so we don't

have the pointer from this node to this node so instead of having pointers we just calculate the index of this node if we stay in node i the index of the left child will

always be equal to 2 i plus 1.

and the index of the right child will always be equal to 2 to i plus 2.

you can prove it using mathematical induction i will not do it but if you if you want just for for the exercise you you can try to just to prove it that for any node i

the left child always have index to l plus one and the right shell will always have index to i plus two uh this is true because the three is complete because all layers of the three are complete from from left to right so you have two

in power of i elements on the layer i so so this one

for example if you stay in note let's say let's say you'll stay in note one so you stay you're staying here this is life and you want to move from this node to

this node so you only know the index of the node so you know the index is one so you stay here and you want to move to the left note of this

element so you calculate 2 i plus 1 it will be 2 multiplied by 1 plus 1 it will be free so you know that the index of the left child is 3 so you move from this node

to this node and this node will be the left child of this node good and sometimes we want to move to the parent node

so let's see what is the index of the parent node of the node i basically if it is the left node we need to calculate i minus 1 divided by 2 and if it is

right node it is i minus 2 divided by 2.

it can be simplified like this we'll say that the index of the parent is i minus 1 divided by 2 and round it down

so if this even then we'll have uh around down to 2i if if it is odd again we'll have i minus 2 divided by 2 will be equal to i

so from here you you will have i plus 0.5 so it will round down to i from here you will have i so it will be rounded down to i so this is the correct formula for both

cases okay any more questions by now don't see any questions okay i think that's all preparations now we now now we're ready to make operations

first let's learn how to insert elements so when we need to insert new element in the binary heap

let's see you you insert some new element uh it's floor so so it's rounded down

cool so let's say you want to insert new elements in the binary heap let's say you insert new like elements let's see insert four so we want we want to insert new element

four in in binary heap so what is what is the easiest place to insert a new node in the binary tree to insert new element in the binary tree

the easiest way to do is insert it here so we'll create a new node in the last layer which is not full

in the leftmost position we'll sort it here so it has index tab now we have a good binary tree so again we have

all layers full except the last layer last layer have some full elements from left and some empty elements to the right and now we just need to maintain this property because

this property that each element is greater or equal transparent is broken here so for this element we have element which is less

than than its current so here is the problem and we need to fix it let me just write the code here so let's see we have insert

x so first we put element in the last position uh last position has index n so again we'll say h and equal to x

and plus plus h this is m this is h this is h this is now we put this element here and now we

need to fix this broken property because for this two elements we have lower elements less than than experiment

how can we fix this property very easily we just will swap these two elements and we so we if we swap these two elements when we move

these 13 down move four up now what happens this property is satisfied because we have a big element here now

we have smaller element here so this property is still satisfied this property now satisfied because we moved the smaller element

up so this property now is satisfied here so now the only broken property may be in this node so for these two nodes we may have the

broken property of the heap so now we have this element less than the sum so this is the only place in the hip where we can

have a problem all other edges are satisfied cool now again we need to fix the property for these two elements again we'll just

swap these two elements so 5 goes down

this 4 goes up now we have this property satisfied this property is identified the only property that may break is for

these two nodes so this is the only place we have a broken property we check the property for these two nodes see that this node is greater equal than its parent so here

satisfied here is just five here this file so for all nodes the property is satisfied so we have the correct binary heap that's all that's how you insert new node in the binary heap you insert in

the last in in the last layer and then move it up until you have the satisfied property for this element in its parent so let's just write the code ah let's

say let's say again i is the index of the element x so first to import n increase n i equal to n minus one so

now i is the position of the element x of the new added element in environment here and now we just move it up so while while we can move it up we can move it

up if it is not the first element so if i is greater than zero and it is less than the its parent

less than its firm and parent have index i minus y power if it is less than apparent then we swap

these two elements so a i and a pi minus one

and continue to the new position y equal to i minus one

yeah that's all let's insert let's insert another element so let's insert another element for example insert two we only have element two well you you might have equal elements

that's not a big problem let's insert one more length uh let's insert one more element so new element must be the next element in the last layer so next element will

be the left l left child of this 15 so we insert new element here it will be the left child of now that's

not enough room here so let's uh just move to left 26 let's insert more element here so we

insert new element like 2 here now look on this property it's broken so we

swap these two elements move 15 down move two up now we say i

so i was here now we swap element i and element i i minus 1 over 2. swap

these two elements and say i equal to i minus 1 so i moved here now again we compare element i and its

parent this element is less than parent element

so again we swap these two elements and is here two is here and move i to the parent so i now is here

and now again we compare element i that this parent see it is greater or equal because they are equal so this property is satisfied everything is satisfied so it's fine

now again we have the correct binary heap so for for any element we see that it is greater equal than its parent element so we have a correct binary heap

that's all now let's calculate time complexity of this algorithm so what is the complexity time complexity will be equal to the number of

uh iterations of this while so we need to complete the number of iterations here here on on every iteration we move to the next layer of the tree

so we start on the bottom layer of the tree and then each time we move to the next layer of the tree the number of layers of this tree will be equal to logarithm of n

so we have at most logarithm of n number of iterations here so total time complexity of this function will be big o of logan as expected

cool so that's how we insert new element in binary heap in logarithmic time and now we need to learn how to remove elements let me check if you have any

questions now i don't see any questions good now let's see how remove elements from the binary here

first again we need to remove the minimal element from the binary heap how to find the minimal element of the binary heap that's quite easy because for each

element we know it is less wrinkle than its children so the minimal element of the binary heap must be in the root so minimal element is always here so we don't need to spend any more

additional time to find the minimal element we always know that minimal element is in the root of the tree and root of the tree have position zero in the array

so just this first element of the ray will always contain the minimal element of the binary heat good so now we located the minimal element it was easy

now we need to remove this minimal element and that's little bit more complicated if you just remove the root element from the tree the tree will break into two parts it

will have left subtree right subtree and we need somehow combine these two suppressing one big tree that's not as if they think so instead of just removing this node tree so we just we

need to remove this node so let's remove this when you remove the road node you have two independent subtrees let's open the right subtree and to combine in the one big three we'll do the phone we'll take the last

element of the tree this is 15 and put this 15 as new root of the tree just remove it from here and move

so this is new element uh we just remove everything unnecessary just move everything just to keep the picture

simple so we removed the minimal element it was in the root of the tree and replace it with last element we take this last element from the bottom layer

and put it in the place where the roof was good now we have the correct binary tree so we have again we have all layers filled

except the last layer and so on and now instead the only problem we have that that we have this property of the hip is not satisfied uh it is not satisfied with these two

nodes so here we have less and here we have less so these two nodes are broken so here

for these two nodes we have elements which is less than the parent element

good so how can we fix this property to fix the property for both these nodes at the same time we'll do the following we'll take one of the children actually the minimum

of the children so we will look on both children see which child is minimal and swap this route with the minimum of the children

so this two is less than four so we swap this 15 of these two so 15 goes here two goes and 15 goes here so again we had two children one was

four another was two and we need to satisfy these two notes at the same time to do this we take the minimum of two children and swap our element with this

meme okay now these two properties are satisfied so here we have a lesser equal here we have a lesson

and now we may have these two properties broken so so now we have for example this property work on

this properties now we have zero columns no matter which element we put these new

roots along the both of the right sides yes but yes it does not matter which element moves to the root but it's easier to move the last element because when you remove the last element you

have the correct binary tree so if if you move element from from the middle of the tree you have hole here so the it will be not correct binary tree so the easiest way to remove element

from the tree so keep it uh the correct balance binary three like we want we want all layers to be filled except the last layer so this element is just easier to remove you you can move any element to the root

but if you remove like this element you have hold here and we don't want to have any empty spaces in our binocular

yeah but we can take any element and put it in the in the root and now now we have problem here we have this element less than this element so again if we have problem like this we

just swap these two elements like we did before so big

fingers here these temples so now this is satisfied this is satisfied so we have the correct binder here

space in this part so i need to erase this hope you don't have any questions

hope your daughter hears that so i i

will just erase this awesome

go so let's write the code i need to remove the minimal elements uh first again we we take the root

elements remove it and replace the last element how can we do it let's just simply swap these two elements just yeah let's just swap these two

elements like first element and the last element it was not a it was h

let us swap the first element of the last element and now remove the last one okay now we have this last element in the root of the tree and we just move it down

that's a little bit more complicated than before because uh in the previous operation when when the third element we on this we only swapped the parent and we have only one parent

when we look on the children we may have zero children we might have one child we have two children so the quote will be a little bit more complicated but

i'll try to make it as simple as possible uh let's see so i is the index of the new element so again like before i is the index of the broken element so this broken

element may have incorrect property for these two children notes let's see so each time

we will find the minimal of these two children and try to swap this minimal minimal challenge we will build sorting algorithm but later we are talking about binary tips

right now we will create a sort algorithm let's go so we will look on both

children let's say well let's just see well two

now um let's see what why i have it most at least one chair so let's move element down until i reach the bottom layer so

when i have at most at at least one child uh uh uh when so if i have left child left childhood in this two i plus one

so while two i plus 1 is less than n so it means i have at most one chapter

at least now we need to take minimum of these two children um let's say j is the is the minimum so say

j equal to uh 2i plus one if the right child is less than left child

so if if i have the right child so if two i plus two is less than m

and this child is less than this child and not a but h h 2 i plus 2 is

less than h okay then it does change so now j is the index of the minimum of the child two children so okay this shall tell

this also now let's see if uh this if this minimum is greater than the element i it means that both children are greater

or equal than the element i it means that this both properties are satisfied so if h j is greater or equal than h i

it means that both children are correct so we just can return here let's break here we can just break from this cycle and

now if it is less then we make the swap and make scope

h h g and say looks fine

yeah yeah this lecture is full of jokes about parents and child and children yeah um cool

i think that's fine so sorry again we find meaning of these two children so we have we take the left child if we have right child and right child is less than left child

then j equal to right child now j is the index of the minimal child we just see if if it is correct we break if it is not correct we swap with the minimal channel and then

move to the middle chart looks fine now in the end we need to return the this removes minimal elements so in the end we just return

h whoo looks fine uh while the while two because we need to make this while only until we reach the bottom layer so if

2i plus 1 greater or equal to m it means the left child is outside of the tree so we don't have the left child if we don't have left child we don't have the right child because

right child have bigger bigger index so it means we have at least one child here if we don't have any children then all properties are satisfied because property is only broken when we

have element i and its children

yes it is the index of the left child if the left child is less than n it means

left child exists uh now we already discussed this that this three represent the memory like in

the big ray so we have index of each element from here and so on

and we just put these elements using these indices in array h we have this array h contain all these elements uh using this indices

you don't use linked lists here so that link list is nothing in linked list you can't access element by its index in one operation so we use like normal

normal arrays instead of not any lists or something but just let's just erase okay now let's calculate time complexity time complexity here will

also be logarithmic because again each on each iteration of this cycle we move one to the next layer of the tree we have at most logarithmic number of

layers so the total time complexity here also will be again oh that's basically all now we have both operations we can insert elements in logarithmic time and we can remove minimal elements in algorithmic

cool cool now now what we will do we will use this binary heap to create a sorting algorithm

like i said in the beginning lecture you can use data structure to make some fast algorithms and now we'll make the sourcing algorithm using this data structure

let's so this sorting algorithm is just called hip sort because you sort

array using heap um let's see let's see you have

a function sort which takes away so how can you sort array using binary heap actually very easily you take all elements of your array

insert them in into the heap and then return remove elements from the hip wide one by one so first you will remove the minimal element then you remove the second minimal

element and so on so you remove the elements of the array in increasing order so we'll just put all

elements in the binary here and then remove all elements from the binary heap [Music]

that's all so so when when you have the correct data structure some algorithms may be very simple just add all elements and remove all elements

and in the end you have the sorted array nice what is the time complexity of this sorting algorithm now it's quite easy to complete so each

operation costs you log on time we have any direction here an operation here so we have total two end operations each operation costs you log in time so total time complexity

will be illuminated so time complexity is the same as in the merchant operating we discussed in the previous lecture my questions now let's make some improvements so this

is the correct sorting algorithm we can we can use it now let's try to improve it a little bit uh the improvement will be the following so let's try

now if we implement it like this we need to have two arrays so imagine we have some array yes you can do the same using binary search tree yes that's correct but

binary search three is a little bit more complicated than structure we'll discuss it in the next semester but yes you can do the same using any binary search tree yeah

um now uh what kind what what's happening we have array a

and we need another array h so if you want to sort the array of size n you need to create another area size n just to put all

to use it as binary heap now you take all elements of your array move them to the binary heap and when you move all elements by the hip you need to move them back to array

a so you need to create another array of the same size that may be too much because sometimes you have not enough memory because something if your array is big

and feels almost all your memory you don't want to create another array so how can we do heap sort without creating a new array of the same size

let's see what what's happening so we have array a now i still need it ah so what's happening you have array a you move from left to right and take

elements from array a and insert them into array h so you already inserted this element into ray h and now you have only these elements

remaining in array h you have this only only this part of our edge is filled so the number of elements in array h is the same as the number of elements you removed from

array a so here you have this so that's what happened so you take one element from array a insert it into ray h using binary heap

algorithm now take this next element move it here and so on

now what will how can we improve it let's see we use only this part of ray a and only this part of ray h now let's combine these two parts in the

ones in in this the same array so instead of having two arrays we will have only one array the same array we take for the source so we take this

array a and use its left part as a binary heap so we'll split it into two parts here we'll have binary heap

and here we'll have the rest of the ray so now on each iteration what happens you need to take the next element from array a and insert into binary heap

so how to insert new elements a binary hip you put it in in the last position of the binary heap and then move it up to the three it's called sift up operation so when you have the element in the

bottom layer and then move it up using the insertion insertion procedure the separation calls sift up in the binder key and this this progression called shift down in the

binder here so when you add this new element in the binary heap you add it in the last position in the last layer of the binary heap

and then shift it up to the root uh so how how can if we use the single array we just look on this element we need to put in this position of rate h but it's already in the correct position

so we just take this element from this position here uh imagine it is now in the binary here so we just increase the size of a binary

heap to here and sift it up to the root of the binary chain all so in the end

you will have the whole array a as as the array of the binary heap

so we'll go from left to right then take each element and shift it up to the root point of the binary here shift sift up is again a sift up is this this part of the

insert operation when you have while and move element up to the root now in the end you will have the whole array be the array of the binary heap

uh and now you need to remove elements so when you remove the element from the binary what happens let's show it in dynamic so so first you have array a

now you add elements one by one so you have heap here and each time you add one more element to the binary pencil so in the end you will have whole array

equal to binary so whole element whole array is a binary heap and now you remove elements from the binary heap so each time you remove element

and put it in the end of the array so first you remove the first element i put in the last position then you remove the next element put it here remove the next element and so on so you

remove elements in increasing order so this element will be put here in some decreasing also something like this again this is the first elementary move

this is second elementary movement so so in the end you will have the array sorted in decreasing order uh then you can just reverse the array

or you can modify your binary heap to remove not the minimal element but the maximal element if you want to sort array in increasing order you can just remove not the minimal element but the maximal element

now let's go so what we do we just go from right to left two zero and say that a i equal to remove me right i i don't know

you see i want to use only this part of them is this the sieve down precision so i'll just swap this element to the last element so i

take this element slope of this element this is the minimal element i swap them and then sift down this element

um that's all that's how you make the heap sort without creating this additional ray so you only use the array that is giving you

a as array a so you take this array a make this rate a array of the binary heap and then remove these elements from the binary heaps and put them in the same

array to create a sort oh that's

basically all any more questions by now okay nice um

yes but it may be a little bit more complicated a little bit too complicated if it's the first algorithm you learn but i think it's quite clear so

now uh the final thing i want to discuss is how to create a binary heap inc in

linear time so now

and now oh

let's change let's let's try try one more time

okay take two so what i want to do i want to improve this part of the algorithm i want to create the binary heap from the given elements in linear time

uh what happens now now we add elements to the binary heap one by one so first we add this root element when we add these two elements and these four elements and so on how much time does it take to add

element it depends on the height of the tree so this first element we can add in one iteration so we just add this element and we don't seat it up because it is the root of the tree

so we spend like zero time to sift this element now for these two elements we may want to sift it up to the root so for each of this element we spend one

operation to sift it up to the root now for these elements we spend two operations for these elements with specific preparations and so on so if we have more layers

in the last layer we spend logan operations to sift it up to the root so the total time complexity will be

something like this it will be the sum uh for all layers let's say we have k is the number of the layer uh from zero to logan

and for layer k we have two in power key elements and for each element we need to spend k operations to sift it

this sum is big why the sum is big because uh basically because on the bottom layer of the tree we have

big number of nodes and for each node we need to spend log n operations to shift it up so in the worst case we have all elements all small elements in the bottom of the string

and we need like to sift all these elements in the bottom layer to the root one by one so each this shift up operation goes to log n time and half n

over two elements in the bottom layer so this this is this is only your handlebar how can we improve this part this one simple uh we will try to move elements not up to

the tree but down so instead of shift up operation we'll use sieve down operation how can we go from bottom to top and each time we have some something

like this so so this bottom part is correct so here we have all properties are satisfied now we take the next element

take the next element and try to satisfy these two properties to do this we make this same operation as when we remove the minimal element so we make the sieve down operation we just seep this element down to the

bottom of the tree so this element will be again this will be correct so after each iteration we have this part this bottom part will contain the

correct part of the binary heap what will be the difference difference will be the following so now we have many elements in the bottom layer but it's easier to sift down these elements

because they are already in the bottom so we have different situation here so in the bottom layer let's see let's say we only have this number of layers so

so for these elements when you sift down them uh you just spend zero operations for this element you spend one operation for this element span two operations

and three and so on so for the root you spend logan operations okay so we will not sift elements up to the root but down to the bottom

what will be the time complexity if we do it this way that's it uh time complexity will be it will be

the sum for k from 0 to log n so again in layer k we have um what is the easiest way to calculate this

let's say it's 2 in power k elements on layer k and the number of operations is

let's say log n minus k mm-hmm now let's show this this function is bigger how to show this uh let's calculate this

this sum in different way let's calculate for each layer the number of swaps we need to make to sift all elements from the bottom so

let's see let's say if we have layer key let's calculate number of swaps you need

to make to sift all elements from this layer down in in the layer more than k so each element from this top part

will be shifted down to this part at most once so for for for layer k we need to make at most twin power case slopes

from layer k to k plus one we make no more than twin power of caseworks so the total number of swaps in all sift

down operations will be the sum of k from 0 to logan and this sum is the sum of geometrical progression so this sum

equal to the power of k plus one minus one uh to the power of not log n power of log n plus one minus one [Music]

and this equal to two multiplied by n minus one this is bigger again what is the idea that is we have a big number of elements in the bottom of the tree and small number of elements in the

in the top of the tree so we try to make first operations for the for this big number of nodes and some small operations for this top part of the tree

so so we have big number of elements here but they are fast to sit down and we have uh slower sieve down here but but there are small number of elements here so the total time

complexity will be linear okay that's basically all i wanted to talk to today

any more questions

[Music]

do

[Music] do

[Music] you