1
00:00:06,130 --> 00:00:10,360
Everybody else is going this is Caleb with Dev's slopes we're going to continue learning about the heap

2
00:00:10,390 --> 00:00:16,630
in this video we're going to write our down keep up functions and we're also going to create an instance

3
00:00:16,930 --> 00:00:22,150
of our men heaps struct and actually play with it interact with it and printed out so we can see how

4
00:00:22,150 --> 00:00:23,350
everything is getting organized.

5
00:00:23,350 --> 00:00:28,280
So let's go ahead and let's continue this by writing our heap of five function.

6
00:00:28,420 --> 00:00:35,980
And these are both going to be mutating private functions so mutating private phunk OK because the heap

7
00:00:35,980 --> 00:00:40,690
of five function only really needs to be known by these functions here and inside of our struct.

8
00:00:40,690 --> 00:00:45,460
We're not going to actually call ify up or down when we're interacting with our heape that's not how

9
00:00:45,460 --> 00:00:46,490
it's supposed to work.

10
00:00:46,570 --> 00:00:52,770
So we're going to go ahead and create this function now heap of fi let's do up first.

11
00:00:52,780 --> 00:00:53,880
All righty.

12
00:00:54,040 --> 00:00:58,380
As you can see it kind of auto completes there which is cool but what we're going to do is we're going

13
00:00:58,390 --> 00:01:04,750
to go ahead and save the index of the last item in our items right.

14
00:01:04,810 --> 00:01:11,020
So var index equals items dot count minus 1.

15
00:01:11,080 --> 00:01:12,990
And what that's going to do.

16
00:01:14,680 --> 00:01:19,270
And what that's going to do is it's going to go ahead and save whatever item is at the very end because

17
00:01:19,270 --> 00:01:22,180
remember there's 18 items but the index is 17.

18
00:01:22,360 --> 00:01:25,050
So count it's the total number of items.

19
00:01:25,120 --> 00:01:27,780
And then we subtract 1 to get to the last index.

20
00:01:27,970 --> 00:01:33,820
So we have saved the index of the last item and now we're going to go ahead and use a while loop because

21
00:01:33,820 --> 00:01:39,970
we need to actually go through each item and Fi it either up or down depending on how the heap changes

22
00:01:40,000 --> 00:01:42,310
and rearrange things accordingly.

23
00:01:42,430 --> 00:01:49,420
So he is going to basically move an item up in the heap where it's supposed to go and we already got

24
00:01:49,420 --> 00:01:55,270
a reference here to the last item in our heape which is here at you know item number 17 I believe is

25
00:01:55,270 --> 00:01:56,310
the index.

26
00:01:56,320 --> 00:02:00,970
So basically what we're going to do is we're going to need to check the value of a certain number so

27
00:02:00,970 --> 00:02:04,560
let's say we we did add in three here at the index 18.

28
00:02:04,870 --> 00:02:10,840
So that would mean that 3 now is at index 18 and that is saved here.

29
00:02:10,840 --> 00:02:12,250
18 is the index.

30
00:02:12,250 --> 00:02:17,590
So what we're going to do is we're going to check while that item has a parent.

31
00:02:17,710 --> 00:02:24,880
OK so has parent at index 18 which it does right it would be connected to 9 here.

32
00:02:25,210 --> 00:02:36,640
While it has a parent K and K the value of the parent is greater than the number we're going to swap

33
00:02:36,640 --> 00:02:41,980
them so we're going to use the function here parent K because that is actually returning the numerical

34
00:02:41,980 --> 00:02:44,080
value in this place not the index.

35
00:02:44,090 --> 00:02:54,100
So if the parent at that index is greater than the item K at that index so we need to actually just

36
00:02:54,100 --> 00:02:55,630
stop for a second and think about what we're doing.

37
00:02:55,630 --> 00:02:59,220
So while an item has a parent so it has a parent.

38
00:02:59,230 --> 00:02:59,860
Yup.

39
00:03:00,220 --> 00:03:06,910
And the value of that parent is greater than the value of the item at that index.

40
00:03:06,910 --> 00:03:14,380
So 3 basically we're saying hey if three is greater than nine do nothing.

41
00:03:14,410 --> 00:03:15,800
But that's not the case.

42
00:03:15,970 --> 00:03:21,490
So we need to go ahead and call swap and what we need to do is we need to go ahead and say hey we need

43
00:03:21,490 --> 00:03:27,630
to swap the parent of that item and so we're going to call get parent index for the child index.

44
00:03:27,640 --> 00:03:31,170
And this is actually returning the index value not the numerical value.

45
00:03:31,240 --> 00:03:37,300
So we're going to swap the items at the parent index and at the just the index right because that's

46
00:03:37,300 --> 00:03:38,070
the child.

47
00:03:38,230 --> 00:03:45,310
And so once we have successfully swapped those We're going to set the index to be equal to the parent

48
00:03:45,340 --> 00:03:46,630
index of that item.

49
00:03:46,630 --> 00:03:48,890
So let's talk about that in just a second.

50
00:03:48,940 --> 00:03:51,550
We have successfully swapped the two items.

51
00:03:51,550 --> 00:03:56,560
So now we're going to go ahead and set the index to this item OK which was the parent.

52
00:03:56,590 --> 00:04:00,670
And so now we're going to go ahead and have three in this place at this index.

53
00:04:00,670 --> 00:04:01,510
We're going to do it again.

54
00:04:01,510 --> 00:04:05,350
So while it has a parent check it has a Parent OK.

55
00:04:05,410 --> 00:04:12,070
And the value of that parent is greater than the number so three four K four is greater than three.

56
00:04:12,070 --> 00:04:13,510
So we swap them.

57
00:04:13,510 --> 00:04:15,880
Now this is for and this is three.

58
00:04:15,910 --> 00:04:18,810
So now what we're going to do we're going to do it again.

59
00:04:18,820 --> 00:04:20,710
So while it has a parent Yep.

60
00:04:21,010 --> 00:04:23,680
While the value is greater then no it's the same.

61
00:04:23,680 --> 00:04:26,140
So we're going to just go ahead and stop it.

62
00:04:26,230 --> 00:04:27,430
That is how it's going to work.

63
00:04:27,430 --> 00:04:29,580
That is how we keep ify up.

64
00:04:29,590 --> 00:04:33,910
Now we need to learn how to keep the five down and this one is a bit more complex but we're going to

65
00:04:33,910 --> 00:04:34,610
get through it together.

66
00:04:34,630 --> 00:04:42,610
So mutating private phunk heap of phi down.

67
00:04:42,940 --> 00:04:43,810
OK.

68
00:04:43,810 --> 00:04:46,300
So just like before we're going to store an index.

69
00:04:46,330 --> 00:04:52,450
But since the top always is going to be the same index we're just going to set our index to be equal

70
00:04:52,450 --> 00:04:53,300
to zero.

71
00:04:53,470 --> 00:04:54,050
OK.

72
00:04:54,460 --> 00:05:01,290
And what we need to do is we basically need to check if a node has a child.

73
00:05:01,370 --> 00:05:07,160
OK we need to keep ify them down but the only one that we need to care about is the left child because

74
00:05:07,250 --> 00:05:11,740
if a parent does not have a left child then it definitely does not have a right child.

75
00:05:11,750 --> 00:05:17,210
So while has left the child we're going to pass in the index here.

76
00:05:17,210 --> 00:05:18,080
So let's see.

77
00:05:18,080 --> 00:05:18,770
Index zero.

78
00:05:18,770 --> 00:05:19,870
Does it have a left child.

79
00:05:19,880 --> 00:05:20,950
Yes.

80
00:05:20,950 --> 00:05:27,470
OK while it has a left child we're going to create a variable called smaller child index and we're going

81
00:05:27,470 --> 00:05:33,470
to set it to the left child so get left child index for the parent which is index.

82
00:05:33,470 --> 00:05:39,290
And so what we're going to do now is we're going to check to see hey if it has a right child and the

83
00:05:39,290 --> 00:05:45,550
right child's value is less than the left child's value we're going to go ahead and change the index

84
00:05:45,560 --> 00:05:57,170
so if it has right child for the parent index and the right child at that index k is less then the left

85
00:05:57,170 --> 00:06:00,310
child at a particular index.

86
00:06:00,500 --> 00:06:06,890
If that's the case we're going to go ahead and set smaller child index to be equal to get right child

87
00:06:06,890 --> 00:06:08,370
Index index.

88
00:06:08,480 --> 00:06:09,280
OK.

89
00:06:09,470 --> 00:06:17,420
So basically we're just checking to see if there's a love child great if there's a right child and that

90
00:06:17,420 --> 00:06:19,220
right child the value of it.

91
00:06:19,220 --> 00:06:24,030
So 8 8 is less than the left child.

92
00:06:24,140 --> 00:06:32,330
We're going to set the smaller child index to be the right child because the smaller item basically

93
00:06:32,330 --> 00:06:36,830
is prioritize near the top and then the index changes.

94
00:06:36,830 --> 00:06:43,670
So that basically this is then set as the smaller child and future branches are going to be prioritized

95
00:06:43,670 --> 00:06:45,150
and built upon the smaller branch.

96
00:06:45,170 --> 00:06:48,620
So there's that but we're not done just yet.

97
00:06:48,620 --> 00:06:55,400
So while it's still the while still inside the while loop we're going to say if items at the index of

98
00:06:55,400 --> 00:07:10,580
the parent K is less then items and let's say the smaller child index here k if the item.

99
00:07:10,790 --> 00:07:13,700
So like the actual number at the index of the parent.

100
00:07:13,800 --> 00:07:22,080
So two if two is less then the smaller child index which it is then we're going to go ahead and break

101
00:07:22,110 --> 00:07:28,110
because it's not really important for us to continue because it's already in its place however else

102
00:07:29,090 --> 00:07:30,000
is bigger.

103
00:07:30,000 --> 00:07:35,820
So if this is for some reason 10 we need to swap it until it gets to its rightful place so we're going

104
00:07:35,820 --> 00:07:41,760
to go ahead and call swap and we're going to go ahead and swap the index of the parent with the smaller

105
00:07:41,760 --> 00:07:43,140
child index.

106
00:07:43,190 --> 00:07:46,040
All righty then at the very very end.

107
00:07:46,170 --> 00:07:53,700
We're going to set index to be equal to the smaller child index because basically every single time

108
00:07:53,730 --> 00:07:59,550
we go through this we're going to go ahead and pass in a new value so let's say that we we add in a

109
00:07:59,550 --> 00:08:02,950
new value here 10 right now 10.

110
00:08:02,970 --> 00:08:05,180
In this instance needs to keep ify up.

111
00:08:05,310 --> 00:08:10,180
But then let's say that we keep a five 10 up and it moves some things out of the way and maybe four

112
00:08:10,200 --> 00:08:11,440
gets placed here.

113
00:08:11,610 --> 00:08:17,220
If we basically need to keep that back down to where it needs to go we're going to go ahead and run

114
00:08:17,220 --> 00:08:24,480
this while loop and it's going to go ahead and basically take the index of the smaller child K and it's

115
00:08:24,480 --> 00:08:29,400
going to go ahead and flip it and then reorganize it and then set the index at the very end to the smaller

116
00:08:29,400 --> 00:08:34,740
child so we can keep going down and down and down and down through the process which is really cool.

117
00:08:34,800 --> 00:08:37,670
And at this point we are now ready to play with our heap.

118
00:08:37,680 --> 00:08:42,180
So let's go ahead and let's just create an instance of heap.

119
00:08:42,390 --> 00:08:46,230
So my heape is going to be equal to men heap.

120
00:08:46,240 --> 00:08:47,040
All righty.

121
00:08:47,430 --> 00:08:55,120
And now if we call my heap and we can access the items we can access and peek and poll.

122
00:08:55,200 --> 00:08:55,910
OK.

123
00:08:56,070 --> 00:08:59,030
So let's go ahead let's add some items here let's actually do this.

124
00:08:59,070 --> 00:09:01,990
Similarly to this one let's add in two.

125
00:09:02,010 --> 00:09:03,100
All righty.

126
00:09:03,330 --> 00:09:03,720
Cool.

127
00:09:03,730 --> 00:09:04,830
We two.

128
00:09:05,120 --> 00:09:06,420
Let's just do this a bunch of times.

129
00:09:06,430 --> 00:09:08,830
Let's make this three.

130
00:09:09,570 --> 00:09:11,920
Let's make this eight.

131
00:09:12,300 --> 00:09:13,890
Let's make this one.

132
00:09:13,950 --> 00:09:14,470
Let's do.

133
00:09:14,510 --> 00:09:14,670
No.

134
00:09:14,670 --> 00:09:21,200
4 7 12 13 whatever.

135
00:09:21,210 --> 00:09:21,950
18.

136
00:09:22,170 --> 00:09:22,730
OK.

137
00:09:22,950 --> 00:09:27,420
So we added some items here and now I want to see what they actually look like when we print them out.

138
00:09:27,420 --> 00:09:33,210
So there's a handy dandy function similar to print but basically it dumps an object's contents using

139
00:09:33,210 --> 00:09:35,020
its mirror to standard output.

140
00:09:35,040 --> 00:09:39,120
So we're going to go ahead and dump my heap items.

141
00:09:39,420 --> 00:09:42,380
And what it's going to do is going to print them from top to bottom.

142
00:09:42,480 --> 00:09:45,830
And as you can see our heape is organize.

143
00:09:45,870 --> 00:09:52,770
We have to at the very top its children are three and eight then four and seven then 13 and 18.

144
00:09:52,770 --> 00:09:54,950
So this is actually not organized super well.

145
00:09:55,100 --> 00:09:57,340
The 10 to nine year should be switched anyway.

146
00:09:57,630 --> 00:10:03,760
So now what I want to show you is if I go ahead and type my heape dot peak what that's going to do is

147
00:10:03,760 --> 00:10:06,210
it's going to print out the top item over here.

148
00:10:06,450 --> 00:10:15,840
But if I if I do pull poll is going to go ahead and if you remember poll basically removes the top item

149
00:10:16,230 --> 00:10:24,330
and then sets the last item to be the front and then fi's everything down so that it finds its rightful

150
00:10:24,330 --> 00:10:29,670
place and he profile down is going to take all of the indices into account and compare them to keep

151
00:10:29,670 --> 00:10:37,950
it in its rightful place so if we go ahead and do dump my items after this we'll see a second item and

152
00:10:37,950 --> 00:10:38,490
look at this.

153
00:10:38,490 --> 00:10:41,070
Now our heape is three.

154
00:10:41,070 --> 00:10:42,190
As the parent node.

155
00:10:42,400 --> 00:10:44,690
OK four than 8.

156
00:10:44,880 --> 00:10:50,400
And then for the 4 node the next item is going to be 18 and 7 13 and 8.

157
00:10:50,400 --> 00:10:58,020
So as you can see things are things are organized but they are not exactly in a numerical order like

158
00:10:58,020 --> 00:10:58,770
you might expect.

159
00:10:58,770 --> 00:11:06,330
And so if we continue doing this a few times what we're going to see as we go down is we have to hear

160
00:11:06,330 --> 00:11:07,090
that's the minimum.

161
00:11:07,110 --> 00:11:12,930
Then the next smallest then the next smallest then the next smallest then the next smallest and so of

162
00:11:12,930 --> 00:11:18,480
course we are you know confusing things we're adding things in that are not there.

163
00:11:18,880 --> 00:11:23,220
Oh you know what it looks like it's not actually getting removed which is funny.

164
00:11:23,280 --> 00:11:30,140
So we are running into a problem where our older indexes here are not actually they're not getting removed.

165
00:11:30,150 --> 00:11:32,750
They're kind of getting duplicated and moved around.

166
00:11:32,970 --> 00:11:37,260
So I think we're going to need to do something differently here.

167
00:11:37,260 --> 00:11:37,710
All right.

168
00:11:37,710 --> 00:11:41,170
So I realize what we were doing wrong.

169
00:11:41,220 --> 00:11:43,060
We are going through here.

170
00:11:43,110 --> 00:11:46,150
We're organizing everything the way that it's supposed to be done.

171
00:11:46,200 --> 00:11:51,600
But if you remember in our poll function here we save an instance of the first item then we set the

172
00:11:51,600 --> 00:11:56,590
last item to be the first item then we keep ify everything down and return that item.

173
00:11:56,700 --> 00:11:57,610
Fatal flaw.

174
00:11:57,630 --> 00:12:00,840
We're not removing the last item that we moved into the front.

175
00:12:00,840 --> 00:12:04,040
So we need to call items not remove last.

176
00:12:04,200 --> 00:12:07,540
And now if we look at how this printed it it's going to make a lot more sense.

177
00:12:07,540 --> 00:12:14,260
So here's our initial print which has our full stack two is the parent node 3 and eight are children

178
00:12:14,260 --> 00:12:20,040
nodes four and seven are nodes of three and 13 and 18 are nodes of eight.

179
00:12:20,050 --> 00:12:26,130
So then we remove the one because we call poll and then it reorganizes everything.

180
00:12:26,250 --> 00:12:33,920
Three is a parent node 4 and 8 are its children nodes 17 and 18 are the nodes for 4.

181
00:12:33,970 --> 00:12:38,870
They both are bigger and below and then 13 is the singular node for number 8.

182
00:12:38,950 --> 00:12:46,360
Then we remove 3 and 4 becomes the top parent node with 7 and 8 as children nodes and 18 and 13 as the

183
00:12:46,360 --> 00:12:47,510
nodes for 7.

184
00:12:47,530 --> 00:12:49,340
Then we get seven.

185
00:12:49,510 --> 00:12:55,300
As a parent node 13 and 8 or it's parent or children nodes an 18 is the node of 13.

186
00:12:55,300 --> 00:12:56,480
Then we remove it again.

187
00:12:56,620 --> 00:13:00,380
And of course are our peers getting smaller.

188
00:13:00,490 --> 00:13:03,670
Eight is the parent node and 13 and 18 are its children.

189
00:13:03,670 --> 00:13:08,590
So as you can see it is working we had a little bit of a bug there when we were not shrinking our array

190
00:13:08,590 --> 00:13:10,080
the way we were supposed to.

191
00:13:10,090 --> 00:13:11,310
My bad.

192
00:13:11,410 --> 00:13:13,760
And so this is our heape it works.

193
00:13:13,750 --> 00:13:18,710
It organize itself depending on the minimum value and the maximum value.

194
00:13:18,730 --> 00:13:23,650
We could also set up a max heap by basically you know writing the functions a little bit differently

195
00:13:23,650 --> 00:13:25,080
basically the opposite.

196
00:13:25,120 --> 00:13:27,350
But yes this is our heape.

197
00:13:27,370 --> 00:13:33,520
We can add items we can peek at items we can pull items and when we print it we get them all printed

198
00:13:33,520 --> 00:13:36,760
out in a nice organized way it's doing all the thinking for us.

199
00:13:36,760 --> 00:13:37,990
Very very cool stuff.

200
00:13:37,990 --> 00:13:41,140
This is how you create a heap in Iowa with swift.