WEBVTT 00:00.150 --> 00:03.510 Hello again! In this video, we are going to look at the priority queue. 00:05.310 --> 00:10.620 We were discussing at the end of the last video, that the standard queue has the element arranged 00:10.890 --> 00:11.910 in arrival time. 00:12.450 --> 00:16.230 And sometimes we need to be able to process some element before others. 00:16.800 --> 00:22.560 For example, if we have a restaurant, the customers who have a reservation will get seated first, and 00:22.560 --> 00:25.830 then we see if there are any seats for customers who do not have a reservation. 00:27.020 --> 00:32.180 If we have an event and some celebrities or VIPs turn up, they expect to go straight to the front of 00:32.180 --> 00:39.260 the queue and not have to stand behind the peasants. And in C++, we could implement this using a priority 00:39.260 --> 00:39.620 queue. 00:40.460 --> 00:45.500 So this is pretty much the same as the standard queue, except that the order of the element depends 00:45.500 --> 00:48.770 on their importance, and not their arrival time. 00:50.160 --> 00:55.200 So the most important element are going to be at the front, so they get processed first. And the least 00:55.200 --> 00:58.530 important element are going to be at the back, so they get processed last. 00:59.550 --> 01:05.030 And C++ has a priority queue, which is also in the queue header. By default, 01:05.040 --> 01:09.930 the less-than operator of the element's type is used for ordering the element in the queue. 01:10.920 --> 01:16.770 If two or more element have the same priority, then by default the queue does not take account of 01:16.770 --> 01:17.040 that. 01:17.430 --> 01:20.520 So there could be in any order, relative to each other. 01:24.430 --> 01:31.600 So our queue could look like this. We have our element. The most important element is at the front, and the 01:31.600 --> 01:33.370 least important element is at the back. 01:34.030 --> 01:37.060 These are ints, so they are ordered using the less-than operator. 01:38.990 --> 01:43.790 If we add a new element, it goes into the appropriate place for its priority. 01:44.180 --> 01:47.300 So 2 is greater than 1, but not greater than 3. 01:47.750 --> 01:49.280 So it goes between 3 and 1. 01:51.820 --> 01:56.800 When we remove an element, it is always the one with the highest priority. And then the element with 01:56.800 --> 01:59.680 the next highest priority moves to the front of the queue. 02:03.050 --> 02:07.520 The priority queue in the library can be implemented using a vector or a deque. 02:08.120 --> 02:14.210 The interface is similar to queue, but not quite the same. So we can use push() and pop() to add and remove 02:14.210 --> 02:14.660 element. 02:15.320 --> 02:20.570 When we add an element, it goes in front of all the element which have lower priority. When we call 02:20.570 --> 02:20.880 pop(), 02:20.900 --> 02:25.820 this removes the element from the front of the queue. And then the element with the next highest priority 02:26.010 --> 02:27.500 becomes the new front element. 02:28.990 --> 02:33.970 To get the element from the front of the queue, we call top(). So that returns the element with the highest 02:33.970 --> 02:34.480 priority. 02:35.140 --> 02:37.960 There is no function for getting the element at the back of the queue. 02:38.620 --> 02:40.060 And then we have empty() and size() again. 02:42.300 --> 02:46.590 So here is our example. We have our print() function again, for getting the details. 02:47.070 --> 02:50.100 We have to call top() instead of front(), because that is the name. 02:50.430 --> 02:52.200 And there is no back member function. 02:53.720 --> 02:55.740 Then we create a priority queue 02:55.760 --> 02:58.340 object. We call push() a few times. 02:58.910 --> 03:03.110 So we would expect that 5 is at the front of the queue, and 1 is at the back. 03:03.440 --> 03:05.660 So this is the same queue that we had on the slide. 03:07.180 --> 03:10.240 Then we call push(), to add in element with value 2. 03:10.870 --> 03:12.460 So that should go between 1 and 3. 03:13.720 --> 03:16.420 And then we call pop(), to get the top element. 03:17.290 --> 03:22.570 So that 5 has been removed from the queue, and now the element at the front is 4. 03:25.970 --> 03:32.780 So there we are. So the highest priority element is 5. Then we add the element. And then, after 03:32.780 --> 03:36.770 removing the top element, the highest priority element is now 4. 03:40.140 --> 03:45.480 Priority quese are useful for processing data which needs to be - well, prioritized! 03:46.500 --> 03:49.500 So, for example, if you are writing an operating system scheduler. 03:49.800 --> 03:54.450 So this will decide when the process gets time from the CPU processor. 03:54.460 --> 03:59.580 And if we have an important process, we can give it more time, more attention from the processor. 04:00.180 --> 04:02.640 And the less important processes gets less time. 04:04.260 --> 04:10.140 For networking, sometimes we need to have so-called "out of band" of communication. So we can send our 04:10.140 --> 04:12.270 data packets with a normal priority. 04:12.960 --> 04:17.610 And then if we have some important message: for example, we want to drop the connection immediately. 04:18.120 --> 04:23.250 We can send that with a higher priority and the receiving end will process that immediately. 04:23.880 --> 04:25.830 So that avoids having to wait for it to get through 04:25.830 --> 04:29.430 all the data it has already received, by which time it could be too late. 04:30.610 --> 04:36.100 And if we have a management system for bug reports, we could order the bugs by priority. So the serious bugs 04:36.430 --> 04:38.890 get fixed before the developers look at the minor bugs. 04:42.900 --> 04:47.940 In a priority queue, we can only access the top element. If you are going to need access to other 04:47.940 --> 04:49.710 elements, then you can use a map instead. 04:50.310 --> 04:55.650 The key for the map will be the priority of the element and the value will be the data. 04:56.890 --> 05:02.990 Elements which have the same priority are not necessarily in arrival order. If that is important, 05:03.070 --> 05:04.780 then are were a couple of things you can do. 05:05.410 --> 05:06.940 You could use a nested map. 05:07.210 --> 05:10.630 So this is a map whose key is the priority. 05:11.110 --> 05:14.560 And then the value is another map, which has the arrival 05:14.560 --> 05:17.320 time as key, and the data as value. 05:18.720 --> 05:23.040 If we are using a class of our own, then we could redefine the less-than operator. 05:23.340 --> 05:25.080 So it takes account of the arrival time. 05:26.220 --> 05:27.780 Okay, so that is it for this video. 05:28.170 --> 05:29.040 I will see you next time. 05:29.280 --> 05:31.260 But until then, keep coding!