1
00:00:00,150 --> 00:00:06,570
OK, so who to another lecture on heaps and this lecture, we're going to go over deleting a value from

2
00:00:06,570 --> 00:00:07,140
a heap.

3
00:00:07,560 --> 00:00:12,900
And we also have something that kind of goes along with that called heap of Phi, which is basically

4
00:00:12,900 --> 00:00:17,970
making sure that the heap maintains all of its properties for it to be called a heap price.

5
00:00:17,970 --> 00:00:22,680
So once we delete, if it misses the heap up, we have to kind of reheat it right.

6
00:00:23,220 --> 00:00:24,180
So let's get into it.

7
00:00:25,140 --> 00:00:27,480
So deletion from a heap.

8
00:00:27,510 --> 00:00:33,360
Well, if you think about deleting something, the simplest case is if you were to just delete the last

9
00:00:33,360 --> 00:00:34,680
value, it's very easy.

10
00:00:34,680 --> 00:00:37,350
So we're thinking about twenty one here.

11
00:00:37,350 --> 00:00:40,650
You see, it is the last thing in the array and also at the bottom right.

12
00:00:40,650 --> 00:00:44,140
Most last thing in the heap that's described as a tree here, right?

13
00:00:45,360 --> 00:00:47,260
So deleting that thing is simple.

14
00:00:47,280 --> 00:00:49,000
We just remove it, right?

15
00:00:49,020 --> 00:00:50,180
Take it out of the array.

16
00:00:50,430 --> 00:00:51,120
It's done.

17
00:00:51,630 --> 00:00:53,280
But what about a different position?

18
00:00:53,700 --> 00:00:59,240
So more specifically, let's look at the root, because that's kind of the one that has the most like

19
00:00:59,280 --> 00:01:01,010
dependent connections on it, right?

20
00:01:01,030 --> 00:01:06,150
It has all these children, these sub trees, the rest of the heap, if you will, sub heaps technically,

21
00:01:06,150 --> 00:01:06,420
right?

22
00:01:08,040 --> 00:01:12,960
So if we want to delete any other position in the last position, we have to kind of follow these steps

23
00:01:12,960 --> 00:01:13,530
right here.

24
00:01:13,740 --> 00:01:17,970
So we have to first swap it with the last position structurally.

25
00:01:19,050 --> 00:01:23,640
So that means the bottom right and of course, corresponding to the last position in the array.

26
00:01:24,330 --> 00:01:25,740
After that, we can delete it.

27
00:01:25,740 --> 00:01:30,750
So if we want to delete that three, we can move it down here, move the one here, delete that three.

28
00:01:31,710 --> 00:01:36,180
But then when we have to do is sift down that 21 to the correct position.

29
00:01:36,180 --> 00:01:39,900
So the heap still maintains that numerical property, right?

30
00:01:41,520 --> 00:01:43,200
So we go ahead and do that.

31
00:01:43,200 --> 00:01:44,940
We swap it with the last position.

32
00:01:45,690 --> 00:01:49,530
So you notice it got swapped down there and then we can go ahead and delete it.

33
00:01:50,370 --> 00:01:51,810
So now it's deleted.

34
00:01:52,530 --> 00:01:57,720
But now we have 21 here and you know, that's not OK to have five here and 21 as a parent.

35
00:01:58,020 --> 00:02:04,080
So we need to start doing the next part, which is 50 and down to the correct position.

36
00:02:04,620 --> 00:02:07,640
And this is what we actually call the heap of five part.

37
00:02:07,650 --> 00:02:10,050
This is this is the heap application process.

38
00:02:11,340 --> 00:02:15,540
So this process has its own steps to kind of sub steps, right?

39
00:02:15,870 --> 00:02:21,930
So what we want to do first is compare it to the left child and we will of course, compare it to the

40
00:02:21,930 --> 00:02:27,330
right if necessary, kind of get to one of those situations down here.

41
00:02:28,020 --> 00:02:32,370
But first, we compare to the left and then what we're interested in is comparing the left and the right

42
00:02:32,370 --> 00:02:34,680
child to see which one is smaller.

43
00:02:34,680 --> 00:02:37,470
And we will just swap with the smaller child, right?

44
00:02:37,480 --> 00:02:43,020
Because this process, unlike insertion insertion, was bubbling up, right?

45
00:02:43,050 --> 00:02:47,790
This process is sifting down, so we're swapping down rather than swapping up.

46
00:02:48,420 --> 00:02:56,220
So the 21 needs to go down and buy it, swapping the it'll basically grab whatever is smaller than it

47
00:02:56,220 --> 00:02:57,150
and move it up.

48
00:02:57,150 --> 00:02:59,070
So it maintains the key property, right?

49
00:02:59,070 --> 00:03:02,280
But we're not going to continually move the smaller values up.

50
00:03:02,790 --> 00:03:08,970
What we're continually doing is trying to move the twenty one down right, the bigger values down in

51
00:03:08,970 --> 00:03:09,630
this case.

52
00:03:11,150 --> 00:03:14,790
So we compare it to the left child, right.

53
00:03:14,840 --> 00:03:16,070
Twenty one and five.

54
00:03:17,450 --> 00:03:20,090
So five is definitely less than 21.

55
00:03:20,600 --> 00:03:26,780
The next thing we're going to do is compare five and the right child retinol, also 21 five, as we've

56
00:03:26,780 --> 00:03:28,280
already said, is less than 21.

57
00:03:28,310 --> 00:03:28,490
Right.

58
00:03:28,490 --> 00:03:30,230
So it's less than the right child.

59
00:03:31,100 --> 00:03:33,220
And then we want to swap with the smaller child.

60
00:03:33,440 --> 00:03:36,560
So we go ahead and swap the 21 with the five like that.

61
00:03:37,760 --> 00:03:39,590
We start the process over again.

62
00:03:39,620 --> 00:03:48,380
Let's go ahead and check the left child of where twenty one is now twenty eight bigger than twenty one.

63
00:03:48,950 --> 00:03:49,700
No, it's not.

64
00:03:49,700 --> 00:03:55,640
So we're actually going to have to consider the right child in this situation.

65
00:03:56,060 --> 00:04:00,630
So what we want to do, though, is compare the left and the right child.

66
00:04:01,220 --> 00:04:05,090
So we want to see, OK, well, which one is smaller?

67
00:04:05,480 --> 00:04:08,570
So 18 is smaller than twenty eight, right?

68
00:04:09,020 --> 00:04:10,790
So that's the one we want to swap with.

69
00:04:11,150 --> 00:04:19,370
But we also have to make sure that we compared 21 with 18 to make sure that the value down here was

70
00:04:19,370 --> 00:04:20,330
in fact smaller.

71
00:04:20,330 --> 00:04:23,740
So we could do the swap kind of like we already did with the left child right.

72
00:04:23,750 --> 00:04:26,180
So that's where that right, if necessary thing comes in.

73
00:04:26,930 --> 00:04:31,370
So we'll go ahead and swap with the smaller one of the children, which was 18.

74
00:04:32,810 --> 00:04:34,580
So we go ahead and do that.

75
00:04:35,570 --> 00:04:39,680
And then at this point, we have arrived with a normal heap, right?

76
00:04:39,680 --> 00:04:46,610
And we can check that because everything, all the children of the parents should be larger values,

77
00:04:47,030 --> 00:04:47,360
right?

78
00:04:47,690 --> 00:04:50,000
So let's check out five.

79
00:04:50,030 --> 00:04:51,320
Are its children larger?

80
00:04:51,320 --> 00:04:51,560
Yeah.

81
00:04:51,560 --> 00:04:52,730
Eighteen and five.

82
00:04:52,730 --> 00:04:53,900
Twenty one thousand five.

83
00:04:54,320 --> 00:04:55,550
Let's look at 18.

84
00:04:56,180 --> 00:04:59,060
Yeah, eighteen left child is twenty eight.

85
00:04:59,060 --> 00:04:59,780
That's bigger.

86
00:05:00,140 --> 00:05:01,670
Eighteen right child is twenty one.

87
00:05:01,670 --> 00:05:02,450
That's bigger.

88
00:05:02,960 --> 00:05:10,130
So this satisfies the heap numerical property and the structural property in the fact that it has only

89
00:05:10,130 --> 00:05:12,140
been building out from the left right.

90
00:05:12,170 --> 00:05:17,150
So this is we could consider this a complete proper heap.

91
00:05:19,580 --> 00:05:24,290
So what is the time complexity of this?

92
00:05:24,320 --> 00:05:31,520
Well, we can safely say that the worst case time complexity of delete slash heap of pie is, oh bigo

93
00:05:31,520 --> 00:05:32,810
of log in.

94
00:05:33,560 --> 00:05:34,580
Why is that?

95
00:05:35,750 --> 00:05:44,030
Well, the reason why is because in the worst case, what we have to do is sit down that value all of

96
00:05:44,030 --> 00:05:46,760
the levels of the heap, right?

97
00:05:47,480 --> 00:05:53,540
So basically, when we're talking about 50 and down all the levels of the heap.

98
00:05:55,320 --> 00:06:02,660
If the reason that it becomes law in time complexity is because a heap has long in levels and that is

99
00:06:02,660 --> 00:06:04,280
where a. the number of values.

100
00:06:04,310 --> 00:06:09,650
So if you check this out, we have one two three four five.

101
00:06:10,160 --> 00:06:15,440
So we have five nodes in the three or five values in the array, respectively.

102
00:06:16,760 --> 00:06:22,020
And we have we have, let's see, one two.

103
00:06:22,040 --> 00:06:24,410
So it will be like zero one two, right?

104
00:06:24,890 --> 00:06:27,470
The number of levels that we would consider it.

105
00:06:27,500 --> 00:06:35,640
So what you can say is basically if you did a log of five, you notice that it would be two point seventeen.

106
00:06:36,200 --> 00:06:43,700
And we would kind of round that down and that would end up being the levels of how many levels are in

107
00:06:44,030 --> 00:06:44,660
our heap.

108
00:06:45,480 --> 00:06:53,400
So the reason that that works out well is because let's say we have some more nodes in here, so right

109
00:06:53,400 --> 00:06:54,930
now we've got five, right?

110
00:06:55,320 --> 00:07:02,160
But if we were to add one here, we would have six right and it would still have the same number of

111
00:07:02,160 --> 00:07:03,780
levels, right?

112
00:07:04,830 --> 00:07:07,380
So this is like, you know, one two.

113
00:07:08,230 --> 00:07:12,940
If we add another note off to the right, like a right child here, it would still have the same number

114
00:07:12,940 --> 00:07:14,670
of levels right now would be seven.

115
00:07:14,680 --> 00:07:18,640
And so if you look that up, you know, like log five and log of six.

116
00:07:18,910 --> 00:07:20,740
And we're talking about log base two, right?

117
00:07:21,160 --> 00:07:24,670
So log a five log of six, log of seven and those are two point seventeen.

118
00:07:24,670 --> 00:07:28,840
So we can write that down, you know, it equals the level, the number of levels in the heap.

119
00:07:29,770 --> 00:07:37,630
So that's how we can safely say that the worst case time complexity would be Bigo of log of it for the

120
00:07:37,630 --> 00:07:38,560
delete heap of fire.

121
00:07:39,490 --> 00:07:45,310
And we'll talk some more about the time complexity of the other operations on the heap in the next lectures

122
00:07:45,310 --> 00:07:48,700
when we talk about those operations in specific.

123
00:07:48,730 --> 00:07:55,480
We'll get back to the insertion and how the time complexity of that insertion we already looked at is

124
00:07:55,660 --> 00:07:59,290
when we compare it to kind of another way to build a heap.

125
00:07:59,980 --> 00:08:00,310
All right.

126
00:08:00,310 --> 00:08:02,310
So with that, I will see you in the next lecture.