1
00:00:06,080 --> 00:00:11,150
Everybody what's going on says Caleb with Deb sloes dot com and in this video we're going to be talking

2
00:00:11,150 --> 00:00:15,380
about two very important data structures that you need to know about.

3
00:00:15,380 --> 00:00:19,630
One is called the heap and the other one is called the stack.

4
00:00:19,710 --> 00:00:24,670
Now they're very similar in some ways but they're also very different in other ways.

5
00:00:24,680 --> 00:00:26,260
So we're going to learn the key differences.

6
00:00:26,330 --> 00:00:31,460
What makes them sort of similar what makes them very different and you need to know the distinction

7
00:00:31,460 --> 00:00:33,050
between the two of these is really important.

8
00:00:33,050 --> 00:00:35,860
So let's begin with the heap.

9
00:00:35,900 --> 00:00:39,630
Now you can think of the heap like a giant pile of values.

10
00:00:39,710 --> 00:00:41,030
You can see it here.

11
00:00:41,360 --> 00:00:43,110
There are two kinds of heap.

12
00:00:43,220 --> 00:00:46,150
There is what's called a mini heap and a max heap.

13
00:00:46,280 --> 00:00:53,150
And so we're going to be focusing on a min or minimum heap in this video because the max heap is literally

14
00:00:53,300 --> 00:00:55,060
identical just the opposite.

15
00:00:55,220 --> 00:01:01,730
So what you see in this video for the heap you can just flip the concepts and the same thing applies.

16
00:01:01,730 --> 00:01:02,490
Pretty cool.

17
00:01:02,780 --> 00:01:07,740
So a mini heap is organized from least to greatest from top to bottom.

18
00:01:07,910 --> 00:01:10,500
You can see the smallest values are at the top.

19
00:01:10,550 --> 00:01:13,940
They branch out and they begin getting a little bit larger.

20
00:01:13,940 --> 00:01:18,340
They continue to branch and get larger and larger and larger all the way down.

21
00:01:18,350 --> 00:01:21,630
As you branch down the heap those values increase.

22
00:01:21,700 --> 00:01:22,210
OK.

23
00:01:22,490 --> 00:01:25,320
So each level down has bigger and bigger values.

24
00:01:25,350 --> 00:01:27,140
That's why it's called a heap.

25
00:01:27,140 --> 00:01:31,420
We have the big things on the bottom as foundation and a build up and up and up and up.

26
00:01:31,430 --> 00:01:36,700
Now it's also structured like a heap it's like a big pile of data and a maxi.

27
00:01:36,710 --> 00:01:40,570
Like I said would have the greatest values at the top and the lowest at the bottom.

28
00:01:40,580 --> 00:01:49,560
So basically a heap consists of parents K parent nodes and children on the left and right of that node.

29
00:01:49,610 --> 00:01:57,950
Now every node can have one or two children and each node in and of itself is a parent unless of course

30
00:01:57,950 --> 00:02:03,470
it doesn't have nodes if it doesn't have a left or right child node sort of like like like a family

31
00:02:03,470 --> 00:02:03,980
tree.

32
00:02:03,980 --> 00:02:07,700
But it's kind of actually kind of weird if you really think about it too much so just think of it sort

33
00:02:07,700 --> 00:02:08,860
of like a family tree.

34
00:02:08,930 --> 00:02:10,140
They're all connected.

35
00:02:10,250 --> 00:02:14,880
Now each node in our stack has a particular index.

36
00:02:14,890 --> 00:02:15,350
OK.

37
00:02:15,650 --> 00:02:19,650
And it's going to go from top to bottom from left to right.

38
00:02:19,700 --> 00:02:22,940
And what that means is that we're going to start with zero.

39
00:02:22,940 --> 00:02:29,810
Of course at the top of our heap and then the left child node is going to be one the second the right

40
00:02:29,810 --> 00:02:34,790
child though is going to be two three four or five all the way through the entire heap top to bottom

41
00:02:34,790 --> 00:02:35,880
left to right.

42
00:02:35,990 --> 00:02:42,310
And because of that order we can easily use an array to house a heap which is pretty cool.

43
00:02:42,320 --> 00:02:50,030
Now we can easily access any of the nodes in our heap by just doing a simple calculation on whatever

44
00:02:50,090 --> 00:02:53,330
index the know that we're working with has.

45
00:02:53,330 --> 00:02:59,930
So for instance if we were working with the index for and we wanted to know which node was its parent

46
00:03:00,200 --> 00:03:06,170
we would take the index minus 2 and then we would divide all of that by 2 and that's going to get us

47
00:03:06,170 --> 00:03:07,850
the index of its parent.

48
00:03:07,850 --> 00:03:09,050
Pretty cool.

49
00:03:09,080 --> 00:03:14,990
Now if we are dealing with a parent node like let's say that 4 for instance is a parent node if we want

50
00:03:14,990 --> 00:03:22,010
to get the index of the left child node all we have to do is do index times two plus one to get the

51
00:03:22,010 --> 00:03:25,890
right child node we need to do index times two plus two.

52
00:03:25,940 --> 00:03:27,050
Pretty cool.

53
00:03:27,050 --> 00:03:28,330
That's how we're going to do it.

54
00:03:28,430 --> 00:03:34,430
And that will get you the index of whichever child node you are trying to find as well as the parent

55
00:03:34,430 --> 00:03:34,940
nodes.

56
00:03:35,060 --> 00:03:36,200
Very very cool stuff.

57
00:03:36,200 --> 00:03:38,600
But this heape already has values in it.

58
00:03:38,600 --> 00:03:40,810
What happens if we add a new value.

59
00:03:41,030 --> 00:03:45,920
Well if we're using an array when we add a new value it's going to append it to the very end of our

60
00:03:45,920 --> 00:03:48,680
heap which in this case would be down at the very bottom.

61
00:03:48,680 --> 00:03:51,680
Now of course this value is too small.

62
00:03:51,680 --> 00:03:53,860
It doesn't fit in the heap.

63
00:03:54,380 --> 00:04:00,050
But what we're going to do is basically using a couple of functions you can bounce it up to the top

64
00:04:00,050 --> 00:04:02,960
by comparing it to the nodes around it.

65
00:04:03,110 --> 00:04:09,260
It'll be out of order and in order to fix that we're going to go ahead and basically well see does it

66
00:04:09,260 --> 00:04:09,680
fit.

67
00:04:09,680 --> 00:04:11,380
Is it less than it's parent.

68
00:04:11,380 --> 00:04:13,030
Cause we can get that index right.

69
00:04:13,100 --> 00:04:18,830
If it's not less than its parent then we're going to flip it with its parent and then we'll compare

70
00:04:18,980 --> 00:04:22,620
that node to its parent above if it's less than the parent.

71
00:04:22,640 --> 00:04:28,100
We're going to flip it again until we get to a place where it fits where the one above it is less the

72
00:04:28,100 --> 00:04:30,050
one below it is greater.

73
00:04:30,110 --> 00:04:35,570
And we can access all those indices using our little functions there that we talked about index minus

74
00:04:35,570 --> 00:04:36,030
2.

75
00:04:36,080 --> 00:04:41,840
Divided by 2 and x times 2 plus 1 et cetera et cetera we can access all of it and determine its place.

76
00:04:41,840 --> 00:04:43,420
Very very cool stuff.

77
00:04:43,460 --> 00:04:44,680
That's how a heap works.

78
00:04:44,690 --> 00:04:48,330
In essence like I said a max heap is the opposite.

79
00:04:48,350 --> 00:04:50,140
So let's move on to the stack now.

80
00:04:50,210 --> 00:04:56,530
Another very important data structure and you can think of a stack like well a stack.

81
00:04:56,570 --> 00:04:57,210
OK.

82
00:04:57,230 --> 00:05:03,530
Think of a stack of plates a stack of boxes a stack of laptops a stack of cans of spray cheese don't

83
00:05:03,530 --> 00:05:04,630
actually try that it's pretty messy.

84
00:05:05,510 --> 00:05:07,130
Don't try this at home folks.

85
00:05:07,130 --> 00:05:09,710
But you can think of it as a stack.

86
00:05:09,710 --> 00:05:15,560
That's why it's called a stack and something important that you need to know about a stack is that it

87
00:05:15,560 --> 00:05:17,650
is a leaf no data structure.

88
00:05:17,660 --> 00:05:22,000
L I F O that stands for last in first out.

89
00:05:22,160 --> 00:05:25,680
And what that means is exactly what it sounds like.

90
00:05:25,700 --> 00:05:29,930
The last item you put in is going to be the last item you take out.

91
00:05:29,930 --> 00:05:35,120
Think of a stack of plates if you had a stack of 100 plates you wouldn't try to pull out the 99th plate

92
00:05:35,120 --> 00:05:36,020
on the bottom.

93
00:05:36,020 --> 00:05:40,440
You'd pull off the top because that's easiest need break your way down through the stack.

94
00:05:40,580 --> 00:05:42,950
That's how a stack is going to work.

95
00:05:42,980 --> 00:05:47,240
The last item in is the first item you remove.

96
00:05:47,240 --> 00:05:52,250
Just like a stack of any physical object so a stack has a few different functions that can be performed

97
00:05:52,280 --> 00:05:53,900
to interact with the data.

98
00:05:53,900 --> 00:05:55,770
Push is one of them.

99
00:05:55,880 --> 00:05:58,950
Pop is another one and peek is a third one.

100
00:05:59,150 --> 00:06:06,060
So push push is a function that's going to push a new element onto the top of our stack.

101
00:06:06,110 --> 00:06:11,870
So if we begin with zero items we would call push once to push in the first item if we wanted to stack

102
00:06:11,870 --> 00:06:14,840
another one on top we would call push again and add in that item.

103
00:06:14,840 --> 00:06:15,790
So that's how it works.

104
00:06:15,790 --> 00:06:18,780
Push is going to add an item to our stack.

105
00:06:18,940 --> 00:06:25,490
OK pop the function what it's going to do is it's going to remove the top item from our stack and then

106
00:06:25,490 --> 00:06:27,680
return that to wherever we call the function.

107
00:06:27,680 --> 00:06:34,070
So if we wanted to basically remove an item and then access whatever value it had we would call pop

108
00:06:34,070 --> 00:06:37,760
because it's going to pull it off and it's going to give us the value which would be really helpful

109
00:06:37,790 --> 00:06:43,610
if you know maybe you deleted something in an app but you wanted to give a user the ability to undo

110
00:06:43,610 --> 00:06:50,900
it within 15 seconds it would pop that off and you would still have reference to the data in memory.

111
00:06:50,900 --> 00:06:56,950
And then if they decided not to get rid of it you could just let that expire and get removed from memory.

112
00:06:56,960 --> 00:06:58,620
That's just one potential use.

113
00:06:58,790 --> 00:07:05,360
Furthermore peak is the last function and peak is going to allow you to essentially look at the top

114
00:07:05,360 --> 00:07:06,140
item.

115
00:07:06,320 --> 00:07:12,080
But the cool thing is that peek doesn't actually modify the stack what it's going to do is it's going

116
00:07:12,080 --> 00:07:16,630
to let you see what the value is it returns the value but it's not going to remove it or add it.

117
00:07:16,640 --> 00:07:20,120
It just allows you to look at it in view only mode if you will.

118
00:07:20,300 --> 00:07:21,200
That's what Peke does.

119
00:07:21,200 --> 00:07:28,430
So since a stack is so linear in nature it's perfect to use with arrays in code so you don't need to

120
00:07:28,430 --> 00:07:33,500
build your own fancy data type or or you know way to hold all of the stack data.

121
00:07:33,500 --> 00:07:37,610
You can just use an array because it's a very very linear data type.

122
00:07:37,700 --> 00:07:42,020
So this is in essence how a heap and a stack work.

123
00:07:42,020 --> 00:07:45,990
They're very different but they're similar in a few ways.

124
00:07:46,100 --> 00:07:51,940
I'd be surprised if in a coding interview you weren't asked about a heap and a stack those things together.

125
00:07:52,070 --> 00:07:54,100
I would be surprised if you were not asked about that.

126
00:07:54,100 --> 00:08:00,440
So to recap the heap and the stack are both data structures very common programming data structures

127
00:08:00,890 --> 00:08:06,940
the heap is a hierarchy of values going either from least to greatest.

128
00:08:06,950 --> 00:08:15,170
Each node has children or can have children and each child node has a parent node and the parent node

129
00:08:15,170 --> 00:08:22,250
is always less or greater depending on whether it's a least the greatest heap or a greatest to least

130
00:08:22,250 --> 00:08:26,860
keep the stack is a last in first out data structure.

131
00:08:26,860 --> 00:08:32,070
That means every item we add on is going to be the first item that we take off.

132
00:08:32,130 --> 00:08:35,300
K we can peek to see what's on the top.

133
00:08:35,390 --> 00:08:41,390
We can pop values to remove them and we can push new values on the heap and the stack.

134
00:08:41,390 --> 00:08:46,730
They're both very important data structures so study up make sure you understand these concepts so that

135
00:08:46,730 --> 00:08:48,340
you could create them yourself in code.

136
00:08:48,350 --> 00:08:50,460
It's very very important to know about.

137
00:08:50,570 --> 00:08:52,850
This is Calleigh with Debb slopes dot.com.