1 00:00:00,590 --> 00:00:01,550 Hi everyone. 2 00:00:01,550 --> 00:00:06,440 In this video, let's get introduced to a new data structure called Priority Queue. 3 00:00:06,440 --> 00:00:12,080 Now a priority queue is a data structure where each element has a priority. 4 00:00:12,080 --> 00:00:12,650 All right. 5 00:00:12,680 --> 00:00:18,350 Now typically a priority queue is implemented with a heap though you can do it in different ways. 6 00:00:18,350 --> 00:00:20,960 Implementing it with a heap is more efficient. 7 00:00:20,960 --> 00:00:24,710 And that's why we will go ahead in this manner in this section. 8 00:00:24,710 --> 00:00:30,290 Now, in a priority queue, every node has a value as well as a priority. 9 00:00:30,320 --> 00:00:35,840 Now earlier when we discussed a binary heap, we epiphyte based on the value. 10 00:00:35,840 --> 00:00:40,610 But in the case of a priority queue we will heapify based on the priority. 11 00:00:40,610 --> 00:00:40,970 All right. 12 00:00:40,970 --> 00:00:42,230 So that's the only difference. 13 00:00:42,230 --> 00:00:47,390 So over here we will need a node class because every node will have a value and a priority. 14 00:00:47,390 --> 00:00:49,580 And then if you want we can store it as an array. 15 00:00:49,580 --> 00:00:52,130 But then every element will be a node in the array. 16 00:00:52,220 --> 00:00:52,790 All right. 17 00:00:52,820 --> 00:00:55,370 Now we will have two types of priority queues. 18 00:00:55,370 --> 00:00:57,170 One is a max priority queue. 19 00:00:57,170 --> 00:01:03,140 In this case the top element or the first element which would be returned or removed will be the element 20 00:01:03,140 --> 00:01:04,760 with the maximum priority. 21 00:01:04,760 --> 00:01:05,180 All right. 22 00:01:05,180 --> 00:01:10,640 And similarly, in the case of a min priority queue, the first element which would be returned would 23 00:01:10,640 --> 00:01:12,710 be the element with a minimum priority. 24 00:01:12,710 --> 00:01:14,630 Again, it depends on how you define it. 25 00:01:14,630 --> 00:01:20,180 Let's say you define that some something that is of priority one is most important. 26 00:01:20,180 --> 00:01:24,080 In that case you would ideally implement a min priority queue. 27 00:01:24,080 --> 00:01:29,720 But then if you implement something where you say that as high the priority, let's say you have a priority 28 00:01:29,720 --> 00:01:32,450 100 greater than priority five. 29 00:01:32,450 --> 00:01:35,090 In that case you would implement a max priority queue. 30 00:01:35,090 --> 00:01:37,760 So again it depends on how you want to do it. 31 00:01:37,760 --> 00:01:42,560 Now let's quickly take a look at a common Big-O operations operations of a priority queue. 32 00:01:42,590 --> 00:01:47,390 You can see that removal and insertion is O of log n time complexity. 33 00:01:47,390 --> 00:01:51,260 That's because we are implementing the priority queue as a binary heap. 34 00:01:51,260 --> 00:01:54,230 So you will see that it's the same for a binary heap as well. 35 00:01:54,230 --> 00:01:57,860 That's because we have to do just one comparison per level. 36 00:01:57,860 --> 00:02:03,200 And because a binary heap is a complete binary tree, the height of the binary heap will be log n, 37 00:02:03,200 --> 00:02:03,500 right. 38 00:02:03,500 --> 00:02:08,360 So the number of comparisons would be the maximum depth of the tree, or the height of the tree, which 39 00:02:08,360 --> 00:02:14,270 is log n and then peaking at the maximum or minimum priority element, depending on whether you have 40 00:02:14,270 --> 00:02:18,500 a max binary heap or a min binary heap is going to be constant time and space. 41 00:02:18,500 --> 00:02:24,500 Again, that's because you know that the value with the maximum priority in the case of a max binary 42 00:02:24,530 --> 00:02:26,060 heap would be the topmost element. 43 00:02:26,060 --> 00:02:31,280 And similarly, in a min binary heap, the value with the minimum priority would be the top element, 44 00:02:31,280 --> 00:02:32,480 so you know where it is. 45 00:02:32,480 --> 00:02:35,540 So you can directly go ahead and peek at that element. 46 00:02:35,540 --> 00:02:39,470 So that's why the time and space complexity of this operation is o of one.