1
00:00:00,740 --> 00:00:03,170
Hi everyone, let's do this question.

2
00:00:03,170 --> 00:00:07,130
Implement a priority queue as a min binary heap.

3
00:00:07,130 --> 00:00:12,470
The priority queue class should support the following functions n queue to insert an element.

4
00:00:12,470 --> 00:00:16,130
D queue to extract the element with the highest priority.

5
00:00:16,130 --> 00:00:20,000
Lowest numerical priority is treated as highest priority.

6
00:00:20,000 --> 00:00:20,480
All right.

7
00:00:20,480 --> 00:00:22,550
So let's go ahead and do this question.

8
00:00:22,550 --> 00:00:28,010
Now notice over here it's mentioned we have to implement the priority queue as a min binary heap.

9
00:00:28,010 --> 00:00:29,870
And the same thing is mentioned over here.

10
00:00:29,870 --> 00:00:33,980
Lowest numerical priority is treated as the highest priority.

11
00:00:33,980 --> 00:00:35,420
All right so let's go ahead.

12
00:00:35,420 --> 00:00:40,310
Now remember priority one is the lowest numerical priority right.

13
00:00:40,310 --> 00:00:43,520
So let's treat it as let's treat this as like this.

14
00:00:43,520 --> 00:00:48,530
Now again it's unlikely that functionally we would say that something has a priority minus one.

15
00:00:48,530 --> 00:00:52,790
But again if that is taken in then we would treat that as lesser than one.

16
00:00:52,790 --> 00:00:56,660
But again, it depends on how we are on the use case.

17
00:00:56,660 --> 00:00:58,610
Right on why we are implementing this.

18
00:00:58,610 --> 00:01:01,730
So over here we are treating that priority one is the highest priority.

19
00:01:01,730 --> 00:01:07,610
So I'm just writing this over here to show that we are building a min priority queue or a min binary

20
00:01:07,640 --> 00:01:08,030
heap, right?

21
00:01:08,030 --> 00:01:11,840
We are using a min binary heap to implement this min priority queue.

22
00:01:11,840 --> 00:01:16,940
Now let's say we have first a job A so it can be any value.

23
00:01:16,940 --> 00:01:19,100
Now it has a priority three.

24
00:01:19,550 --> 00:01:25,760
Now the difference of this implementation from the implementation where we implemented the max binary

25
00:01:25,790 --> 00:01:28,280
heap is that there we only had the value.

26
00:01:28,280 --> 00:01:29,780
But over here we have a value.

27
00:01:29,780 --> 00:01:31,370
This is the value which is job A.

28
00:01:31,370 --> 00:01:33,710
So it can be a text or it can be something like that.

29
00:01:33,710 --> 00:01:35,390
And then we have a priority right.

30
00:01:35,390 --> 00:01:37,700
So there are two properties to each node.

31
00:01:37,700 --> 00:01:39,980
So we'll have a node class over here to implement this.

32
00:01:39,980 --> 00:01:46,280
Now let's say to the priority queue we insert another job which is job B and that has a priority one.

33
00:01:46,280 --> 00:01:46,640
All right.

34
00:01:46,640 --> 00:01:48,770
So again we insert at the end.

35
00:01:48,770 --> 00:01:50,090
So we have inserted this.

36
00:01:50,090 --> 00:01:55,130
And then now we need to shift it up or bubble it up to its correct position.

37
00:01:55,130 --> 00:01:55,400
Right.

38
00:01:55,400 --> 00:01:58,460
So we need elements with a lower priority up.

39
00:01:58,460 --> 00:02:01,010
So over here we will need to swap them right.

40
00:02:01,010 --> 00:02:02,660
So let's go ahead and swap them.

41
00:02:02,660 --> 00:02:06,140
And we will have job B over here at the root.

42
00:02:06,140 --> 00:02:08,150
And then job A comes over here.

43
00:02:08,150 --> 00:02:08,600
All right.

44
00:02:08,600 --> 00:02:09,470
So we have swapped them.

45
00:02:09,470 --> 00:02:13,010
Now let's say we insert another job which is job C over here.

46
00:02:13,550 --> 00:02:15,380
And let's say it has a priority two.

47
00:02:15,380 --> 00:02:18,920
Now we have to check whether we do need to shift up.

48
00:02:18,920 --> 00:02:20,990
And over here we see that we don't need to.

49
00:02:20,990 --> 00:02:21,170
Right.

50
00:02:21,170 --> 00:02:25,370
Because the priority is the children priorities are, uh lower.

51
00:02:25,370 --> 00:02:28,640
So with higher priority, I mean, numerically it has to be lower.

52
00:02:28,640 --> 00:02:30,860
So three and two are greater than one.

53
00:02:30,860 --> 00:02:32,420
So they are in the correct position.

54
00:02:32,420 --> 00:02:32,960
All right.

55
00:02:32,960 --> 00:02:35,270
So again we will be storing these as nodes.

56
00:02:35,270 --> 00:02:36,800
So let's say this is node b.

57
00:02:36,800 --> 00:02:38,660
This is node A and this is node c.

58
00:02:38,660 --> 00:02:40,310
So the array will look like this.

59
00:02:40,310 --> 00:02:43,730
So this is node b node a and node c in our array.

60
00:02:43,730 --> 00:02:48,110
So when we implement the min binary heap we will still implement it as an array.

61
00:02:48,110 --> 00:02:51,800
But then in the array instead of just a value we will have nodes over here.

62
00:02:51,800 --> 00:02:54,680
And each node has a value and a priority.

63
00:02:54,710 --> 00:02:58,340
Now let's say we insert one more element again which is job D.

64
00:02:58,340 --> 00:03:00,020
Again we insert it at the end.

65
00:03:00,020 --> 00:03:00,470
All right.

66
00:03:00,470 --> 00:03:05,420
So that's similar to what we discussed when we discussed the max binary heap implementation.

67
00:03:05,420 --> 00:03:07,040
So we inserted over here.

68
00:03:07,040 --> 00:03:10,130
And then we shift up or we bubble up to the correct position.

69
00:03:10,130 --> 00:03:10,520
Right.

70
00:03:10,520 --> 00:03:14,750
So again adding over here can is visually that's how we see it visually.

71
00:03:14,750 --> 00:03:17,480
But when it comes to the array we are storing it as an array.

72
00:03:17,480 --> 00:03:17,660
Right.

73
00:03:17,660 --> 00:03:19,550
So we will be just pushing to the array.

74
00:03:19,550 --> 00:03:21,170
That is we are just adding over here.

75
00:03:21,170 --> 00:03:22,340
And then we bubble up.

76
00:03:22,340 --> 00:03:24,020
So let's check these two.

77
00:03:24,050 --> 00:03:25,460
This one and its parent right.

78
00:03:25,460 --> 00:03:26,750
So A is the parent of D.

79
00:03:26,780 --> 00:03:29,780
Now you can see that three is greater than two right.

80
00:03:29,780 --> 00:03:32,570
So this is not following the min heap property.

81
00:03:32,570 --> 00:03:33,770
So we have to swap them.

82
00:03:33,770 --> 00:03:34,880
So let's swap them.

83
00:03:36,160 --> 00:03:36,490
All right.

84
00:03:36,490 --> 00:03:39,700
So we swap them and we have D over here and a over here.

85
00:03:39,700 --> 00:03:42,850
And now this is how it looks like we have B.

86
00:03:42,850 --> 00:03:44,980
Then we have d and C and then we have a.

87
00:03:44,980 --> 00:03:46,030
So this is how it looks.

88
00:03:46,030 --> 00:03:49,780
So this is how the enqueue function of this priority queue works.

89
00:03:49,780 --> 00:03:54,490
So it's pretty similar to the case where we discussed the max binary heap.

90
00:03:54,490 --> 00:03:59,110
The difference is that over here we have nodes and each node has a value and a priority.

91
00:03:59,110 --> 00:04:02,650
And then of course we are implementing a min binary heap over here.

92
00:04:02,650 --> 00:04:04,480
Earlier we did a max binary heap.

93
00:04:04,480 --> 00:04:06,940
Now let's see how d queue works.

94
00:04:06,940 --> 00:04:12,100
Or removing or extracting the uh the job with the highest priority.

95
00:04:12,130 --> 00:04:18,310
Now priority one is the highest priority or numerically we want to extract the job with the numerically

96
00:04:18,310 --> 00:04:20,410
lowest priority, which is one over here.

97
00:04:20,410 --> 00:04:22,300
Now let's say we extract this.

98
00:04:22,300 --> 00:04:23,980
That is we are returning this value.

99
00:04:23,980 --> 00:04:24,160
Right.

100
00:04:24,160 --> 00:04:29,950
So we return or serve the job B serve job B when we call the dequeue function.

101
00:04:29,950 --> 00:04:31,870
And then what we do is.

102
00:04:32,630 --> 00:04:34,700
So again look at the scenario.

103
00:04:34,700 --> 00:04:37,520
We are taking this element over here which is the first element.

104
00:04:37,520 --> 00:04:38,900
So that is served first right.

105
00:04:38,900 --> 00:04:40,790
So we remove from the beginning.

106
00:04:40,790 --> 00:04:43,700
And then what we do is so this is just served.

107
00:04:43,700 --> 00:04:49,370
And then we pop the last node from the array and we place it at the zeroth index.

108
00:04:49,370 --> 00:04:50,750
So we put this over here.

109
00:04:50,750 --> 00:04:54,260
And after we do this we just sift down or bubble down.

110
00:04:54,260 --> 00:04:56,480
So this is the same thing that we discussed previously.

111
00:04:56,480 --> 00:04:58,250
So let's see how this looks now.

112
00:04:58,250 --> 00:05:00,470
Now right A is now at the root node.

113
00:05:00,470 --> 00:05:02,900
And then we have D and C over here.

114
00:05:02,900 --> 00:05:04,520
And then we bubble down.

115
00:05:04,520 --> 00:05:06,560
Now let's check over here.

116
00:05:06,560 --> 00:05:09,260
The children both have the same priority right.

117
00:05:09,260 --> 00:05:11,540
So we can just swap with this one over here.

118
00:05:12,020 --> 00:05:15,980
So we swap and we need to swap because three is greater than two right.

119
00:05:15,980 --> 00:05:20,300
So we swap and we have D over here and A and C over here.

120
00:05:20,300 --> 00:05:21,290
And that's that.

121
00:05:21,290 --> 00:05:27,650
So that is how enqueue and dequeue work in the priority queue where we have implemented the priority

122
00:05:27,650 --> 00:05:29,690
queue as a min binary heap.

123
00:05:29,690 --> 00:05:35,180
Now let's quickly look at the complexity analysis of the enqueue and dequeue functions which we just

124
00:05:35,180 --> 00:05:35,900
now discussed.

125
00:05:35,900 --> 00:05:41,810
You will see that the time complexity of both of this is O of log n in the best average and worst case,

126
00:05:41,810 --> 00:05:45,380
and the space complexity is the same is is constant.

127
00:05:45,380 --> 00:05:48,110
So it runs in constant space, which is O of one.

128
00:05:48,110 --> 00:05:53,360
You can see that because we implemented the priority queue as a min binary heap, the time and space

129
00:05:53,360 --> 00:05:59,630
complexity is the same as that for a binary heap, which is O of log n and O of one space.

130
00:05:59,630 --> 00:06:03,140
And again, this is because of the bubble up and bubble down which is happening.

131
00:06:03,140 --> 00:06:03,410
Right?

132
00:06:03,410 --> 00:06:08,900
So when we enqueue something, when we insert something, we insert at the end, and then what we do

133
00:06:08,900 --> 00:06:09,860
is we bubble up, right?

134
00:06:09,860 --> 00:06:10,700
So we bubble up.

135
00:06:10,700 --> 00:06:14,510
And we have seen that the time complexity of the bubble up function is O of log n.

136
00:06:14,510 --> 00:06:16,310
So the same logic appears over here.

137
00:06:16,310 --> 00:06:20,270
And when we dequeue we uh serve the first element.

138
00:06:20,270 --> 00:06:23,480
And then we take the last element and put it at the root node.

139
00:06:23,480 --> 00:06:25,940
And then we bubble down right or sift down.

140
00:06:25,940 --> 00:06:31,970
And again, we have seen previously already that the time complexity of the bubble down function is

141
00:06:31,970 --> 00:06:33,110
O of log n.