1
00:00:06,080 --> 00:00:10,700
Everybody has gone this is Caleb with Dev slopes and in this video we're going to be talking about the

2
00:00:10,700 --> 00:00:15,560
heat data structure and we're also going to learn how to build one in swift which is pretty neat.

3
00:00:15,560 --> 00:00:20,680
So first I want to just kind of review what the heap is and how it works.

4
00:00:20,810 --> 00:00:23,870
Basically heaps can operate in two ways.

5
00:00:23,960 --> 00:00:24,160
Ms.

6
00:00:24,170 --> 00:00:31,160
Heap or max heap heap basically prioritises the smallest values at the very top and a max heap does

7
00:00:31,160 --> 00:00:35,380
exactly the opposite it prioritises the largest values at the very top.

8
00:00:35,390 --> 00:00:42,250
Now each heap starts with a parent node and then it can have two children nodes just like so.

9
00:00:42,260 --> 00:00:45,080
So this top one has two children.

10
00:00:45,170 --> 00:00:46,520
This one here is a parent.

11
00:00:46,520 --> 00:00:48,090
It has two children.

12
00:00:48,260 --> 00:00:53,780
So a node can act as both a parent and a child except for the very tippy top.

13
00:00:53,930 --> 00:01:00,860
So another thing to know is that the child nodes are always bigger than their parent nodes so here too

14
00:01:01,190 --> 00:01:03,200
is the parent and the children are 3 and 8.

15
00:01:03,200 --> 00:01:04,930
Both are bigger here.

16
00:01:04,970 --> 00:01:09,020
Three is a parent node and four and seven are both its children nodes which are both bigger.

17
00:01:09,020 --> 00:01:11,930
So that's how that works going down.

18
00:01:11,930 --> 00:01:18,710
Another thing to note is that the index of heape items start at zero just like an array and then go

19
00:01:18,800 --> 00:01:20,480
top to bottom and left to right.

20
00:01:20,480 --> 00:01:28,200
So we start with 0 then one two three four five six seven eight nine 10 et cetera et cetera.

21
00:01:28,490 --> 00:01:34,820
And what we need to be able to do in our heap is to be able to access the index of a parent node for

22
00:01:34,820 --> 00:01:35,810
a child node.

23
00:01:36,110 --> 00:01:41,570
We also need to be able to access the indices of both children from a parent node and we're going to

24
00:01:41,570 --> 00:01:47,840
write some code to do that but we also need to think if I add in a new item K like down here at the

25
00:01:47,840 --> 00:01:50,750
bottom maybe index 21 or something.

26
00:01:50,750 --> 00:01:58,040
It needs to be able to tell whether or not the parent node is larger than that value and if it is then

27
00:01:58,070 --> 00:02:01,910
we're going to switch it until it fits where it's supposed to be in the heap.

28
00:02:01,910 --> 00:02:05,560
Now you might be wondering why would a heap ever be useful in real life.

29
00:02:05,720 --> 00:02:12,350
Well think about this imagine that we are using a max heap where the largest values are prioritized

30
00:02:12,350 --> 00:02:16,340
and moved up to the top and the lower values are more down towards the bottom.

31
00:02:16,340 --> 00:02:23,270
Now of course you can tell it's not perfectly organized where it's going you know in numerical order

32
00:02:23,270 --> 00:02:26,520
like 2 3 4 7 8.

33
00:02:26,570 --> 00:02:27,900
It doesn't work that way.

34
00:02:28,370 --> 00:02:32,720
But generally speaking the largest values are at the top and they're prioritized that way.

35
00:02:32,720 --> 00:02:38,390
So obviously a heap gives you the minimum value at the top of max heap gives you the maximum value at

36
00:02:38,390 --> 00:02:39,380
the top.

37
00:02:39,440 --> 00:02:46,400
So imagine that you're working in a hospital and their intake system for new patients maybe at the emergency

38
00:02:46,400 --> 00:02:53,030
room is a max heap because they want to prioritize the oldest people who come in first they should receive

39
00:02:53,030 --> 00:02:54,280
care first.

40
00:02:54,470 --> 00:02:55,890
Maybe that's how it works.

41
00:02:55,940 --> 00:03:02,330
So let's say someone comes in there add it into the heap and maybe their age is you know 75 and we're

42
00:03:02,330 --> 00:03:04,960
we've got to think about this fliped because this is a min.

43
00:03:04,970 --> 00:03:11,060
But basically their value would be bumped up to the top and they would be put in priority number one

44
00:03:11,060 --> 00:03:12,780
because they are the oldest.

45
00:03:12,950 --> 00:03:18,500
As soon as maybe they have received care they can be removed from the heap and then the rest of it would

46
00:03:18,500 --> 00:03:22,180
bubble all the way up and so that the next oldest person would be at the top.

47
00:03:22,340 --> 00:03:24,710
That's how they work and that's how they could be useful.

48
00:03:24,710 --> 00:03:30,510
The same could go for maybe a pediatric clinic where the youngest children would be prioritized first.

49
00:03:30,590 --> 00:03:31,100
OK.

50
00:03:31,430 --> 00:03:35,930
So let's go ahead and let's pull up an X code and let's build a heap.

51
00:03:35,930 --> 00:03:41,540
So get started with a new playground and we're going to go ahead and just create a blank playground

52
00:03:41,660 --> 00:03:47,550
and let's just call this heap of find the cap'n just save it wherever you want.

53
00:03:47,630 --> 00:03:49,370
I put mine on my desktop.

54
00:03:49,470 --> 00:03:55,520
I want to make the window full screen here and get rid of all of that and just import foundation because

55
00:03:55,520 --> 00:03:58,920
we don't need any of the fancy kit stuff in the playground.

56
00:03:58,970 --> 00:04:01,600
For now we just need foundation because we're using Swift.

57
00:04:01,640 --> 00:04:07,580
So let's go ahead and let's create a struct K called a mean heap and that's what we're going to do.

58
00:04:07,580 --> 00:04:12,950
We're going to create a heap that is a mini heap we could create just a heap struct and then write all

59
00:04:12,950 --> 00:04:18,230
the functions for min and max and maybe use some type of enumeration to determine whether it's min or

60
00:04:18,230 --> 00:04:18,840
max.

61
00:04:18,980 --> 00:04:23,810
But for now let's just go ahead and focus on a min heap because a max heap is exactly the same just

62
00:04:23,840 --> 00:04:24,620
opposite.

63
00:04:24,890 --> 00:04:29,570
So we're going to write some functions in here that are going to be private that only the struct can

64
00:04:29,570 --> 00:04:34,950
access inside and they are important there are three groups of functions.

65
00:04:34,970 --> 00:04:40,520
The first group of functions is going to be for getting the index of a particular node get left child

66
00:04:40,520 --> 00:04:46,240
node get right child node and get parent node or I should say index rather than node.

67
00:04:46,370 --> 00:04:51,440
And so what we're going to need to do is to first write the function that's going to get us the index

68
00:04:51,530 --> 00:04:58,390
of the left child because let's imagine that I am a parent here and I want to know what the index is

69
00:04:58,680 --> 00:05:05,950
of maybe child on the right so I can do a formula and a function pass in my index end depending on my

70
00:05:05,950 --> 00:05:10,170
index I could basically tell you where it is and what index it's at.

71
00:05:10,180 --> 00:05:15,070
So we're going to start by writing a function to get the left child index and it's going to be a private

72
00:05:15,070 --> 00:05:18,730
function called Get Left child index.

73
00:05:18,910 --> 00:05:21,670
We're going to pass in the parent index here.

74
00:05:21,820 --> 00:05:28,010
And of course that's of type and because an array uses it as its way to manage indices.

75
00:05:28,240 --> 00:05:32,920
And because we're getting an index back we need to return an integer.

76
00:05:32,980 --> 00:05:40,240
So in order to actually get the index of the left child we're going to return to k times the parent

77
00:05:40,270 --> 00:05:44,470
index plus one can let me show you how that works.

78
00:05:44,470 --> 00:05:48,320
So this is our first item and it's at index 0.

79
00:05:48,430 --> 00:05:52,560
We're going to use an array actually to store our heap because the index format is the same.

80
00:05:52,570 --> 00:06:00,640
So index 0 is here so we're going to do two times zero which gets us 0 plus 1 gets us the left child

81
00:06:00,640 --> 00:06:01,330
node.

82
00:06:01,600 --> 00:06:02,400
Very very cool.

83
00:06:02,410 --> 00:06:03,780
That's at index 1.

84
00:06:03,790 --> 00:06:07,630
Now getting the right child is going to be basically the same.

85
00:06:07,660 --> 00:06:09,540
We're going to add two instead of one.

86
00:06:09,550 --> 00:06:12,760
So private phunk get right.

87
00:06:12,760 --> 00:06:22,480
Child index like so we're going to pass in the parent index of type int and we're going to return an

88
00:06:22,480 --> 00:06:25,150
integer because of course we're getting the index.

89
00:06:25,390 --> 00:06:29,670
So return to Time's parent index plus 2.

90
00:06:29,920 --> 00:06:31,450
And that works the same way.

91
00:06:31,450 --> 00:06:36,210
This is index 0 2 times 0 0 plus 2 gets us to.

92
00:06:36,220 --> 00:06:40,850
So index 2 is where the right child is so we go 0 1 2.

93
00:06:40,870 --> 00:06:43,460
There's our right child and it works for any of these.

94
00:06:43,480 --> 00:06:47,190
This is index 1 2 0 1 2 3 4.

95
00:06:47,200 --> 00:06:52,810
So if we wanted to know the right child index we would take four times two which is 8 and then plus

96
00:06:52,810 --> 00:06:54,440
2 which is 10.

97
00:06:54,460 --> 00:07:00,100
So 0 1 2 3 4 5 6 7 8 9 10 gets us the index of the right child.

98
00:07:00,190 --> 00:07:01,450
It's pretty cool.

99
00:07:01,450 --> 00:07:05,760
So let's go ahead and let's write the function in order to get the parent index.

100
00:07:05,800 --> 00:07:08,050
That's also going to be a private function.

101
00:07:08,230 --> 00:07:11,250
Get parents index.

102
00:07:11,290 --> 00:07:13,750
And we need to pass in the index of a child.

103
00:07:13,780 --> 00:07:17,090
So child index of type int.

104
00:07:17,680 --> 00:07:23,930
And we're going to go ahead and return an integer and the function for this is we're going to return

105
00:07:23,930 --> 00:07:27,760
a child index minus one.

106
00:07:27,760 --> 00:07:28,390
All right.

107
00:07:28,480 --> 00:07:31,210
And then that whole thing is going to be divided by two.

108
00:07:31,210 --> 00:07:32,320
Let me show you how that works.

109
00:07:32,320 --> 00:07:39,860
So this is well let's see we're getting the parent index of this so we should get the index too.

110
00:07:39,880 --> 00:07:45,370
So what we're going to do is we're going to take the index of this node 0 1 2 3 4 5.

111
00:07:45,550 --> 00:07:47,170
And what we're going to do is we're going to minus one.

112
00:07:47,170 --> 00:07:51,840
So five minus one is four and then we divide that by two which is two.

113
00:07:52,060 --> 00:07:56,040
So 0 1 2 The index is 2 for the parent node.

114
00:07:56,050 --> 00:08:00,970
So now we have the functions we need in order to actually interface with our heap and that's cool and

115
00:08:00,970 --> 00:08:03,370
all but let's go ahead and let's compile these together.

116
00:08:03,370 --> 00:08:06,850
These are functions for getting the index.

117
00:08:07,300 --> 00:08:08,170
And that's great.

118
00:08:08,530 --> 00:08:10,740
So let's go ahead and let's move on.

119
00:08:10,840 --> 00:08:11,390
Oh that's weird.

120
00:08:11,380 --> 00:08:16,030
It looks like that curly bracket turned dark on me there for a second.

121
00:08:16,030 --> 00:08:20,280
Now we need to go ahead and basically write some boolean check functions.

122
00:08:20,560 --> 00:08:27,070
And these are going to check whether or not an item has a left index or right index because in some

123
00:08:27,070 --> 00:08:28,470
cases it might not.

124
00:08:28,480 --> 00:08:29,000
Right.

125
00:08:29,050 --> 00:08:32,700
This parent has a left child but does not have a right child.

126
00:08:32,830 --> 00:08:35,770
And so that would tell us that's where that item needs to go.

127
00:08:35,950 --> 00:08:36,410
Pretty cool.

128
00:08:36,430 --> 00:08:39,580
So we're going to write some functions to determine those different things.

129
00:08:40,000 --> 00:08:46,300
Private funk has left child care and we're going to just pass in an index.

130
00:08:46,630 --> 00:08:47,820
OK.

131
00:08:47,830 --> 00:08:51,390
We're going to return a boolean.

132
00:08:51,440 --> 00:08:52,640
All righty.

133
00:08:52,690 --> 00:09:00,570
And in order to do this we're going to go ahead and say return get left child get left child index already

134
00:09:01,360 --> 00:09:03,790
and we're going to pass in whatever index we have.

135
00:09:03,790 --> 00:09:09,790
So let's say you know it's a parent at index four and we're going to get the left child of that parent

136
00:09:09,820 --> 00:09:10,920
index.

137
00:09:10,990 --> 00:09:20,080
But what we're going to say is if that index is less than the total amount of items in our heap.

138
00:09:20,080 --> 00:09:24,960
So let's think about this if our help here is well let's see this.

139
00:09:24,970 --> 00:09:35,470
If this was the 20th item so 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 what that means is that there

140
00:09:35,470 --> 00:09:37,380
are really 18 items.

141
00:09:37,420 --> 00:09:44,980
So if the index here is 17 and if that is less then the total number of items right the index is 17

142
00:09:44,980 --> 00:09:46,970
the total number is 18 right.

143
00:09:46,990 --> 00:09:48,670
So if that is left.

144
00:09:48,880 --> 00:09:53,570
Sorry if that is less then that means that there is a left child index.

145
00:09:53,710 --> 00:09:54,370
OK.

146
00:09:54,370 --> 00:09:59,560
So what we're going to do is we need to actually create the array that is going to hold all of our heape

147
00:09:59,560 --> 00:10:00,010
items.

148
00:10:00,010 --> 00:10:08,320
So go ahead and create an array called items WIPs items and it's going to an array of type int if only

149
00:10:08,320 --> 00:10:13,960
I could type and we're going to go ahead and just initialize it as an empty array here and we're going

150
00:10:13,960 --> 00:10:19,080
to say if it is less then items don't count.

151
00:10:19,790 --> 00:10:23,270
Ok if that's true it'll return true if it's false.

152
00:10:23,290 --> 00:10:27,610
For instance index 0 1 2 3 4 5 6 7 8 9.

153
00:10:27,640 --> 00:10:28,100
OK.

154
00:10:28,420 --> 00:10:37,390
So we pass in the left child index of 9 K and we get what the child index should be which in this case

155
00:10:37,390 --> 00:10:43,350
would be 19 it 19 is not less than 18 so therefore it knows it does not have a love child.

156
00:10:43,480 --> 00:10:44,770
That's how it works.

157
00:10:44,770 --> 00:10:48,970
So we're going to do it again but do it for the right child which is actually going to be the exact

158
00:10:48,970 --> 00:10:49,630
same function.

159
00:10:49,630 --> 00:10:56,610
So for time's sake I'm just going to copy and paste it and just change the wording so it has right child.

160
00:10:56,620 --> 00:10:57,830
We're going to use the function.

161
00:10:57,850 --> 00:10:58,660
Get right.

162
00:10:58,660 --> 00:10:59,860
Child index.

163
00:10:59,860 --> 00:11:01,760
And if it's less than items that count.

164
00:11:01,780 --> 00:11:04,320
We know that we are not doing the right thing.

165
00:11:04,360 --> 00:11:08,660
So now we need to write the function to check if a node has a parent.

166
00:11:08,680 --> 00:11:09,000
OK.

167
00:11:09,040 --> 00:11:19,070
So private phunk has parent and we're going to pass in the child in the well let's just say in next

168
00:11:19,420 --> 00:11:22,690
gen has a parent.

169
00:11:22,690 --> 00:11:25,620
We're going to check and return a boolean.

170
00:11:26,000 --> 00:11:26,830
OK.

171
00:11:26,980 --> 00:11:27,940
Mix some more space.

172
00:11:27,940 --> 00:11:29,790
You can see what I'm doing here.

173
00:11:30,340 --> 00:11:38,750
And so basically what we're going to do is we're going to return get parent index all ready.

174
00:11:38,830 --> 00:11:45,340
We're going to pass in the index and if that index is greater than or equal to zero.

175
00:11:45,380 --> 00:11:45,970
Right.

176
00:11:46,030 --> 00:11:49,080
We know that there is a parent because.

177
00:11:49,190 --> 00:11:49,450
Yes.

178
00:11:49,450 --> 00:11:54,150
So if let's say we pass in you know index one here.

179
00:11:54,220 --> 00:11:57,660
If one is greater than or equal to zero it has a parent here.

180
00:11:57,760 --> 00:12:00,040
If it's greater than or equal to zero it has a parent.

181
00:12:00,040 --> 00:12:05,320
So basically everything will have a parent node because this index 0 is equal to zero.

182
00:12:05,320 --> 00:12:11,940
And so this node is a parent obviously and it is its own parent which is kind of weird to think about.

183
00:12:11,950 --> 00:12:13,600
But anyway that's how it's going to work.

184
00:12:13,600 --> 00:12:14,460
Code wise.

185
00:12:14,500 --> 00:12:22,980
So now what we need to do is we need to be able to return a certain item from the heap.

186
00:12:22,990 --> 00:12:23,260
Right.

187
00:12:23,260 --> 00:12:26,520
So we have our array of items we need to be able to return an item.

188
00:12:26,530 --> 00:12:33,100
So this is our third section of functions and it's going to just be functions that return an item from

189
00:12:33,100 --> 00:12:34,050
the heap.

190
00:12:34,120 --> 00:12:39,850
So we're going to write three more private functions here private funk and this one is going to be to

191
00:12:39,850 --> 00:12:49,380
return the left child K at a particular index and what it's going to do is it's going to return an int.

192
00:12:50,230 --> 00:12:57,070
So in order to get it we're going to return something and it's going to come from the items array and

193
00:12:57,070 --> 00:13:04,510
all we need to do is to get the left child index wups get left child index.

194
00:13:04,690 --> 00:13:07,120
And for you know a particular index.

195
00:13:07,240 --> 00:13:12,520
So that will return the item at the index that we set.

196
00:13:12,520 --> 00:13:13,160
Right.

197
00:13:13,180 --> 00:13:19,390
So let's say that we're talking about a parent node and we want to get the left child we can actually

198
00:13:19,390 --> 00:13:24,130
just call the index from the parent and it will return the love child for that parent.

199
00:13:24,280 --> 00:13:28,300
So we're going to do the same thing here for right child and I'm going to just copy and paste it for

200
00:13:28,300 --> 00:13:32,030
time because it's the same exact thing right child.

201
00:13:32,050 --> 00:13:35,350
But we're going to use our right child function.

202
00:13:35,350 --> 00:13:41,100
Next we need to be able to get the parents so private phunk parent.

203
00:13:41,210 --> 00:13:41,550
All right.

204
00:13:41,560 --> 00:13:47,490
And we're going to you pass in an index here of type int and we're going to return an int.

205
00:13:47,530 --> 00:13:50,190
Now we're going to return items.

206
00:13:50,570 --> 00:13:57,940
OK I'm going to pass in get parent index for index so if we pass in the index of maybe a left child

207
00:13:58,270 --> 00:14:01,650
this will tell us what its parent is which is pretty cool.

208
00:14:01,660 --> 00:14:07,980
So now this is where we're actually going to write out the operations for our heat.

209
00:14:08,320 --> 00:14:15,040
And like I said when we're dealing with a heap if we added a new value say three here we need to be

210
00:14:15,040 --> 00:14:22,250
able to check to see if this value and its parent are in a good relationship and right now they're not

211
00:14:22,300 --> 00:14:26,310
because 3 is smaller than 9 so it should be in this place.

212
00:14:26,320 --> 00:14:30,490
So what we're going to do is we're going to swap these two and then we're going to check it again.

213
00:14:30,490 --> 00:14:37,270
So we're going to swap the index of three and nine and then we're going to check OK three is still smaller

214
00:14:37,270 --> 00:14:39,630
than four so we need to swap three and four.

215
00:14:39,940 --> 00:14:44,770
And then obviously three and three are equal so they can be in the same place here and that's fine.

216
00:14:45,040 --> 00:14:47,250
But we're going to move on.

217
00:14:47,260 --> 00:14:52,200
So we're going to go ahead and write the swap function which is going to swap two items.

218
00:14:52,200 --> 00:15:00,040
And so let's go ahead and just call this heape operations and this function is going to be private as

219
00:15:00,040 --> 00:15:04,590
well because it just needs to happen on an internal level private function.

220
00:15:04,600 --> 00:15:05,660
So WAP.

221
00:15:05,740 --> 00:15:06,290
OK.

222
00:15:06,430 --> 00:15:12,420
Index one of type int and index to of type int.

223
00:15:12,670 --> 00:15:17,260
And this is not going to return anything we're just passing in values and mutating them so we're going

224
00:15:17,260 --> 00:15:20,000
to basically save one as a placeholder set.

225
00:15:20,080 --> 00:15:26,010
The other one and then set the first one back to whatever we stored in the placeholder so let placeholder

226
00:15:26,110 --> 00:15:30,520
equals items at index 1.

227
00:15:30,520 --> 00:15:33,590
All right so we're going to save that in that little constant there.

228
00:15:33,970 --> 00:15:44,800
Then we're going to say items index 2 is equal to items at index 1 like that.

229
00:15:45,520 --> 00:15:48,340
And then oh wait no I'm doing this backwards.

230
00:15:48,430 --> 00:15:52,480
Index 1 is supposed to be set to the item at index 2.

231
00:15:52,480 --> 00:15:56,240
All righty then we're going to go ahead and set items.

232
00:15:56,650 --> 00:16:02,680
Index two to be equal to the placeholder text we are.

233
00:16:02,680 --> 00:16:05,200
We changed the value of index 1.

234
00:16:05,290 --> 00:16:08,200
We just stored it in memory there which is pretty cool.

235
00:16:08,470 --> 00:16:14,110
And then all that's doing is just swapping the place the index of two variables or two values I mean

236
00:16:14,470 --> 00:16:15,580
in our function.

237
00:16:15,580 --> 00:16:20,230
Now we are getting yelled at because it's saying that this function inside of a struct needs to be marked

238
00:16:20,260 --> 00:16:24,700
as mutating because it's actually mutating the way that items is lined up.

239
00:16:24,700 --> 00:16:30,580
So let's go ahead and add the mutating keyword there and our little error message will go away because

240
00:16:30,580 --> 00:16:33,610
it can then have the permission to mutate the items right.

241
00:16:34,000 --> 00:16:44,130
So a heap has three functions very similar to a stack we have peak Paul P O L L and add so add is like

242
00:16:44,140 --> 00:16:48,560
push pull is like pop and peak is just like peak.

243
00:16:48,670 --> 00:16:50,630
So we're going to write those three functions now.

244
00:16:50,800 --> 00:16:53,950
These ones peak pull and add are all public.

245
00:16:53,950 --> 00:16:59,410
They're ones that we actually want to interface with because Peake allows us to look at the very top

246
00:16:59,410 --> 00:17:02,880
item of our nodes so we could check you know what patient is in that spot.

247
00:17:02,880 --> 00:17:09,060
Were talking about our hospital metaphor pool is going to remove the top item and return it.

248
00:17:09,140 --> 00:17:09,780
Okay.

249
00:17:09,880 --> 00:17:12,100
And then add is going to push a new item in.

250
00:17:12,130 --> 00:17:21,760
So let's go ahead and write this one public phunk peak already and it's going to return an integer to

251
00:17:21,760 --> 00:17:22,610
us.

252
00:17:22,660 --> 00:17:28,160
And so if items that count is not equal to zero.

253
00:17:28,180 --> 00:17:28,590
All righty.

254
00:17:28,630 --> 00:17:34,760
We're going to go ahead and return item at index 0 because that's the top item in our right.

255
00:17:35,050 --> 00:17:40,790
But if that is not the case if if items that count is equal to zero we're going to call fatal error.

256
00:17:40,900 --> 00:17:41,980
Ok cause that would be a problem.

257
00:17:41,980 --> 00:17:43,440
There's nothing in our right.

258
00:17:43,690 --> 00:17:47,040
So that's how peak works it's going to return the top item.

259
00:17:47,050 --> 00:17:53,980
Now we're going to go ahead and do another public function here called Paul and Paul is actually going

260
00:17:53,980 --> 00:17:57,550
to return an integer as well like so.

261
00:17:57,730 --> 00:18:03,610
But we are going to be modifying the array because if we remove an item and then return it.

262
00:18:03,610 --> 00:18:06,770
So we need to set this to mutating.

263
00:18:06,790 --> 00:18:14,260
Now what we're going to do is we're going to check again if items that count is not equal to zero.

264
00:18:14,500 --> 00:18:20,350
We're going to do stuff like modifying the function and removing it then we're going to go ahead and

265
00:18:20,350 --> 00:18:25,390
say else if there is zero items we're going to call fatal error.

266
00:18:25,390 --> 00:18:26,950
So here we go.

267
00:18:27,040 --> 00:18:34,360
What we need to do is we basically need to store the item at the first index so let item equal items

268
00:18:34,420 --> 00:18:35,760
at index 0.

269
00:18:35,950 --> 00:18:36,190
All right.

270
00:18:36,220 --> 00:18:40,570
We're going to just save that in its place then we're going to do is we're going to go ahead and set

271
00:18:40,570 --> 00:18:49,810
items at index 0 to be equal to the very last item which is the new one that we have added or most recently.

272
00:18:49,810 --> 00:18:50,100
All right.

273
00:18:50,110 --> 00:18:57,490
So we're going to call items items dot dot count minus 1.

274
00:18:57,520 --> 00:19:03,110
So we're going to go ahead and move the last item in our heap K all the way up to the front.

275
00:19:03,670 --> 00:19:04,030
Okay.

276
00:19:04,030 --> 00:19:11,380
And then what we're going to do is we're going to go ahead and call a function called heap of FY down.

277
00:19:11,500 --> 00:19:17,740
We haven't written that yet but then basically what we're going to do is lie down is going to basically

278
00:19:17,740 --> 00:19:22,740
check the indexes and say okay 18 that is bigger than both of these and needs to go down.

279
00:19:22,930 --> 00:19:27,580
Okay 18 still bigger than both of these needs to go down 18 still bigger than both of these it needs

280
00:19:27,580 --> 00:19:29,010
to go down 18.

281
00:19:29,080 --> 00:19:33,880
So and it's basically going to help it go all the way down to where it needs to be.

282
00:19:33,910 --> 00:19:38,350
This is what we're doing is we're removing the first item and then we're here refining everything so

283
00:19:38,350 --> 00:19:40,630
that everything knows where it should be.

284
00:19:40,660 --> 00:19:44,030
Now what we're going to write the function down in just a second.

285
00:19:44,140 --> 00:19:49,270
But then at the very end after we reorganize everything we're going to return the item that we initially

286
00:19:49,270 --> 00:19:50,640
saved and removed.

287
00:19:50,770 --> 00:19:51,430
Okay.

288
00:19:51,670 --> 00:19:56,050
So that's Paul that's going to remove the first item and then return it.

289
00:19:56,140 --> 00:19:58,980
And now we need to go ahead and create the add function.

290
00:19:58,990 --> 00:20:05,810
So it's going to be a mutating function and it's going to be public and we're going to go ahead and

291
00:20:05,810 --> 00:20:13,540
just say add and it's going to be an item of type int because that's the type that our function is.

292
00:20:13,540 --> 00:20:16,670
And so we're going to go ahead and do that.

293
00:20:16,730 --> 00:20:24,870
We're going to say items append add the new item and then we're going to need to heap ify up.

294
00:20:25,010 --> 00:20:29,870
OK because if we add a new item down here at the bottom like it let's say it's three that should be

295
00:20:29,870 --> 00:20:32,870
switched with this so we're going to keep it up goes there.

296
00:20:33,010 --> 00:20:35,190
We're going to fly up again and it'll stay there.

297
00:20:35,210 --> 00:20:35,800
OK.

298
00:20:35,870 --> 00:20:38,870
So that's where people fye up comes in handy.

299
00:20:38,900 --> 00:20:41,570
So this video is getting a bit longer than I had anticipated.

300
00:20:41,630 --> 00:20:45,680
So we're going to go ahead and cut this one short and head over to the next video where we're going

301
00:20:45,680 --> 00:20:51,440
to actually write it down and he picks up functions in order to rearrange our heap and then we're going

302
00:20:51,440 --> 00:20:55,580
to actually create an instance of it and play around with it so you can see it visualized.

303
00:20:55,700 --> 00:20:58,090
Let's head over to the next video and let's keep learning about the heap.