1
00:00:01,290 --> 00:00:05,850
In the previous video we discussed distro and how it can be used to find the shortcuts.

2
00:00:05,880 --> 00:00:12,030
But the functionality of the algorithm relied heavily on the implementation of a priority queue so that

3
00:00:12,030 --> 00:00:14,340
we all is the node with the least cost.

4
00:00:15,210 --> 00:00:19,080
So this begs the question how exactly are we going to implement a bride to queue?

5
00:00:19,680 --> 00:00:25,260
The most suitable way, especially for design, is that is to implement it using heaps.

6
00:00:27,180 --> 00:00:31,260
So what are he and why did the first choice implementation of a prior.

7
00:00:32,250 --> 00:00:38,820
Well he's a specialized breeder structures that's satisfied that he property now he property is where

8
00:00:38,820 --> 00:00:45,510
the child node is less than or greater than spirit for a mean he this amounts to the GI node being greater

9
00:00:45,510 --> 00:00:47,340
than or equal to is greater.

10
00:00:47,760 --> 00:00:49,380
And this is opposite for Maxim.

11
00:00:50,250 --> 00:00:55,920
If we look on the right hand side, we have an example of a maxim where child is less than or equal

12
00:00:55,920 --> 00:00:56,550
to is better.

13
00:00:57,270 --> 00:01:01,860
This means that the top node or the root node will have the maximum value of the whole heap.

14
00:01:02,880 --> 00:01:05,590
This property is particularly useful for desktop.

15
00:01:06,120 --> 00:01:11,700
If all nodes represent the respective traversal goals, then the root node will have the least value

16
00:01:11,850 --> 00:01:16,440
and the highest priority customer is the first for the types of heap.

17
00:01:16,770 --> 00:01:21,990
There are many types that can be used to implement a priority group, but we'll be focusing on binaries

18
00:01:22,170 --> 00:01:22,620
for now.

19
00:01:25,180 --> 00:01:34,930
What are my critiques widely heaps agree that have at max two children so a binary tree and to satisfy

20
00:01:34,930 --> 00:01:36,280
the following two properties.

21
00:01:36,760 --> 00:01:43,270
Number one, they are complete, which means that all rules except possibly the last point is filled.

22
00:01:44,900 --> 00:01:45,500
For the last.

23
00:01:45,800 --> 00:01:48,890
All those are as leftmost as possible.

24
00:01:49,550 --> 00:01:54,820
So by this we can even see right here we have three levels in this binary.

25
00:01:55,190 --> 00:01:57,590
And for the first two row they are completely filled.

26
00:01:57,860 --> 00:02:03,170
But the last row is not filled, but all nodes are leftmost as possible.

27
00:02:03,710 --> 00:02:09,960
So this is a complete grid and there is a complete binary retreat in the second property because if,

28
00:02:09,960 --> 00:02:16,280
say, he is satisfied that he property, which means that it can be either a mini heap or a max heap.

29
00:02:17,580 --> 00:02:24,360
Now because of the complete poverty binary he is liberty was entered into an array of so this complete

30
00:02:24,360 --> 00:02:28,590
property becomes very useful in the presentation of a binary hit.

31
00:02:29,990 --> 00:02:35,120
And following are the rules which from which we can represent a binary heap into an array.

32
00:02:35,990 --> 00:02:41,060
The first rule is that the first element of the array is the root note of the binary heap.

33
00:02:42,020 --> 00:02:48,950
The second rule is that if nought is an index sign, then its left child would index a two plus one

34
00:02:49,100 --> 00:02:49,660
and write.

35
00:02:49,700 --> 00:02:56,540
I would have index II plus two and its parent will be at and minus one divided by two flawed.

36
00:02:57,960 --> 00:03:00,090
Let's see how this pans out in this example.

37
00:03:00,300 --> 00:03:08,400
So if we take the root node that is an index zero, the left child would be at two plus one that is

38
00:03:08,400 --> 00:03:14,010
two and two zero plus one that becomes one.

39
00:03:14,520 --> 00:03:16,980
And that is the correct answer for the left chart.

40
00:03:19,730 --> 00:03:20,210
Right here.

41
00:03:20,840 --> 00:03:27,830
And for the right time, we take the same formula for the right foot potato that is doing the zero plus

42
00:03:27,830 --> 00:03:29,480
two that becomes two.

43
00:03:29,930 --> 00:03:31,580
So that is the correct answer for the right.

44
00:03:32,660 --> 00:03:36,740
And if you want to find the pattern of the right chart, that is an index, too.

45
00:03:37,070 --> 00:03:41,360
So we can do that by using the rerun formula that is flawed.

46
00:03:42,690 --> 00:03:45,600
And minus one that is two minus one.

47
00:03:46,820 --> 00:03:53,090
Divide by two, that becomes one and a half point five and floating equals to approximately zero.

48
00:03:53,900 --> 00:03:56,780
So that is the correct answer for the parent.

49
00:03:57,260 --> 00:04:00,020
So this is how we represent a binary heap into an array.

50
00:04:01,720 --> 00:04:04,290
There is no risk because some of the important functions all bind.

51
00:04:05,230 --> 00:04:08,560
The first and the most important function is known as extract.

52
00:04:09,490 --> 00:04:13,630
Now this function returns the root element of the binding domain.

53
00:04:14,290 --> 00:04:16,960
This means the element with the least value.

54
00:04:17,950 --> 00:04:21,370
Now just getting to the top alone happens in constant time.

55
00:04:21,490 --> 00:04:25,990
But because we're in a priority group, we need we will need to remove the root node.

56
00:04:26,200 --> 00:04:27,970
So this disturbs the heap property.

57
00:04:28,090 --> 00:04:29,440
So it needs to be here before.

58
00:04:29,830 --> 00:04:34,300
So a total time complexity now becomes or log in.

59
00:04:35,790 --> 00:04:39,450
And following are the three steps necessary to perform the external function.

60
00:04:40,050 --> 00:04:40,680
Number one.

61
00:04:42,300 --> 00:04:44,790
Remove the root node and keep it separate.

62
00:04:46,000 --> 00:04:48,580
Number two, move the last note.

63
00:04:49,680 --> 00:04:50,190
To the top.

64
00:04:51,250 --> 00:04:52,030
And number three.

65
00:04:53,480 --> 00:04:58,790
He'd be fine now because we have moved a lot more to stop this disturbed he property.

66
00:04:59,090 --> 00:05:01,840
So now we will need to keep it part of the heap.

67
00:05:01,900 --> 00:05:07,910
Five Is that because we have moved the last note to top it needs to be compared with the side note and

68
00:05:07,910 --> 00:05:10,100
gets trapped with the least of a side note.

69
00:05:10,490 --> 00:05:13,160
So too goes to a top and six goes to the bottom.

70
00:05:13,700 --> 00:05:16,030
Now same step repeats for the remaining notes.

71
00:05:16,550 --> 00:05:22,250
For example, six gets replaced with four, four goes to the top and six goes to the bottom.

72
00:05:23,060 --> 00:05:26,240
Here the heap five stops and the effect on function finishes.

73
00:05:27,590 --> 00:05:31,280
Now, the second most important function of this job is known as decrease.

74
00:05:32,140 --> 00:05:35,330
Now, this function happens when we are found shorter role.

75
00:05:36,380 --> 00:05:38,870
So we decrease a squeeze on node value.

76
00:05:39,680 --> 00:05:45,890
So just updating nodes value happens in constant time, but because this might disturb the heap property.

77
00:05:46,190 --> 00:05:48,310
So this needs to be typified.

78
00:05:48,650 --> 00:05:51,980
So the total time complexity now becomes of log in.

79
00:05:53,060 --> 00:05:54,760
Are two steps necessary for decrease.

80
00:05:55,370 --> 00:05:58,940
Number one is updating the nose value and number to keep five.

81
00:06:00,160 --> 00:06:05,860
For example, if you look right here, if we have a node that has a value of five and gets decreased

82
00:06:05,860 --> 00:06:06,340
to one.

83
00:06:07,300 --> 00:06:12,280
So we will now need to compare it for disappearance because one is less than two.

84
00:06:12,400 --> 00:06:13,570
So it needs to be swept.

85
00:06:15,030 --> 00:06:21,220
And this step repeats for the remaining top notes because one and one of same value.

86
00:06:21,240 --> 00:06:22,910
So stripping these to be stopped.

87
00:06:23,160 --> 00:06:25,840
So five stops right here for a decrease.

88
00:06:26,010 --> 00:06:27,360
The function finishes.

89
00:06:28,340 --> 00:06:32,100
Now there are definite few advantage of using heaps as a priority queue.

90
00:06:32,900 --> 00:06:40,580
The first of them is the faster insertion and deletion, which is all again as compared to orphan list

91
00:06:40,580 --> 00:06:41,390
implementation.

92
00:06:42,170 --> 00:06:48,260
And number two, the key property which gives us the smallest value note always in top to task, providing

93
00:06:48,260 --> 00:06:49,340
us easier access.