1
00:00:00,660 --> 00:00:01,020
OK.

2
00:00:01,050 --> 00:00:08,340
Welcome to another lecture about heaps in this lecture, we are going to be using the hip affi algorithm

3
00:00:08,340 --> 00:00:13,850
that we have learned when we discuss deleting leading to actually build a heap and we're going to build

4
00:00:13,860 --> 00:00:14,730
a heap in place.

5
00:00:14,730 --> 00:00:20,820
So what we're talking about is you already having an array with values, but they do not represent a

6
00:00:20,820 --> 00:00:25,650
heap and we want to turn it into a heap by usage of this heap of AI algorithm.

7
00:00:26,640 --> 00:00:31,590
So let's say we already have an array and you won't be looking at this already and be like, well,

8
00:00:31,590 --> 00:00:34,650
you said that it wouldn't be in a heap, but it is in a heap.

9
00:00:35,460 --> 00:00:38,760
This isn't a previous example we've used, but it is a main heap.

10
00:00:39,030 --> 00:00:43,480
And what I'm proposing we do is turn it into a max heap.

11
00:00:43,500 --> 00:00:48,250
So that means that it would not be in the form that we want this in the mini heap, not a max heap.

12
00:00:48,270 --> 00:00:51,310
So let's go ahead and use simplified to turn this into a to.

13
00:00:54,440 --> 00:01:03,200
So what we do when we're trying to transform this into a mass heap using typify is to repeatedly use

14
00:01:03,200 --> 00:01:09,680
heap of fire starting at the last parent node in the heap and moving backwards.

15
00:01:09,680 --> 00:01:15,290
So that means moving from the bottom right to the left and up.

16
00:01:15,560 --> 00:01:17,240
So none of the complete bottom ranks.

17
00:01:17,240 --> 00:01:22,550
I said that we start at the last parent node, so we're not considering leaf nodes.

18
00:01:23,330 --> 00:01:27,950
That's like a big plus of the algorithm, and it makes it faster as far as time complexity.

19
00:01:29,100 --> 00:01:30,870
So let's start at 21 over here.

20
00:01:30,900 --> 00:01:33,150
You can find the last parent node in the heap.

21
00:01:33,390 --> 00:01:39,570
Add in over two minus one, where in is the number of nodes in the heap or number of values.

22
00:01:39,630 --> 00:01:45,510
Considering that as an array, so this will iterate through the heap backwards starting at this point

23
00:01:45,510 --> 00:01:47,120
and repeatedly do that heap of fire.

24
00:01:47,130 --> 00:01:51,510
There's no heap of fire for us to really do at this point because you notice, of course, there's only

25
00:01:51,510 --> 00:01:53,570
one node and it's equal to the parent node.

26
00:01:53,570 --> 00:01:57,390
And we already discussed that being equal is OK and requires no swapping.

27
00:01:59,120 --> 00:02:03,070
So we will move to the left on the same level, right.

28
00:02:04,070 --> 00:02:09,710
So we moved to the left and now we look at five, if you think back to your five, what we want to do

29
00:02:09,710 --> 00:02:14,210
is pick the bigger of the children and swap the parent node with the bigger of the children.

30
00:02:14,210 --> 00:02:15,950
So obviously that is twenty eight.

31
00:02:15,950 --> 00:02:19,130
So we will perform a swap and we swap five and twenty eight.

32
00:02:20,840 --> 00:02:22,760
You can see that swaps in the array as well.

33
00:02:23,810 --> 00:02:25,470
So we're actually done with this level now.

34
00:02:25,550 --> 00:02:31,820
This is a very small example, but it'll be useful to help us understand without going too deep with

35
00:02:31,820 --> 00:02:32,690
some massive heat.

36
00:02:33,470 --> 00:02:36,240
So since we're on this level, we go up to the next level.

37
00:02:36,260 --> 00:02:40,010
This is already the root level, so we would start at the rightmost node.

38
00:02:40,010 --> 00:02:42,770
But this is the right most node because there's only one, right?

39
00:02:43,520 --> 00:02:47,960
So you can see it's reflected in the array as well as the zeroth element at the first position.

40
00:02:48,740 --> 00:02:52,160
So let's go ahead and pick the bigger of the children.

41
00:02:52,160 --> 00:02:55,280
So we look like it looks like we have 28 and 21.

42
00:02:55,280 --> 00:02:56,660
So obviously 28 is bigger.

43
00:02:57,290 --> 00:03:04,400
So we will perform a swap and this is where we start the heap fi process of 15 down, right?

44
00:03:05,120 --> 00:03:10,700
So we've done that swap and we're not done yet because we still have to consider the children of this

45
00:03:10,700 --> 00:03:14,090
node, so have to continue heap refining until we cannot go anymore.

46
00:03:15,500 --> 00:03:21,920
So we pick the bigger of the children now, and 25 is definitely bigger, so we go ahead and swap three

47
00:03:21,920 --> 00:03:22,700
with 25.

48
00:03:24,100 --> 00:03:27,370
You can see that reflected in updated in the array as well.

49
00:03:28,570 --> 00:03:32,350
And now we notice that we actually have a max he already.

50
00:03:33,620 --> 00:03:38,960
So not too many steps, it was a small example, but it's not too many steps in general because it's

51
00:03:38,960 --> 00:03:44,360
a very efficient algorithm to transform an array into a heap.

52
00:03:45,860 --> 00:03:49,210
So you notice let's check the property right to make sure everything is OK.

53
00:03:49,220 --> 00:03:53,360
So structurally from the beginning, it was totally fine.

54
00:03:53,390 --> 00:04:01,010
Of course, any ray, you know is going to be fine, but we noticed that if we were to build out a heap,

55
00:04:01,010 --> 00:04:05,000
we would want it to apply to apply the structural property.

56
00:04:05,510 --> 00:04:08,130
But the numerical property is OK as well, too.

57
00:04:08,240 --> 00:04:12,170
So 28 inch children are 25 and 21.

58
00:04:12,170 --> 00:04:13,510
Those are less than we could.

59
00:04:13,520 --> 00:04:15,410
25 inch children are five and three.

60
00:04:15,410 --> 00:04:16,160
Those are less.

61
00:04:16,580 --> 00:04:18,800
And of course, 21 and 21.

62
00:04:18,800 --> 00:04:21,350
Being equal is fine as well, like we talked about before.

63
00:04:22,940 --> 00:04:28,550
So in terms of efficiency and time complexity, we haven't really covered formal analysis of algorithms

64
00:04:28,550 --> 00:04:29,270
yet in this course.

65
00:04:29,280 --> 00:04:35,870
So you're going to have to just trust me that this bill heap with heap of fire runs in linear time so

66
00:04:36,230 --> 00:04:36,800
of in.

67
00:04:37,250 --> 00:04:44,360
And you can even claim type bound state of in if you're familiar with that, and you can check that

68
00:04:44,360 --> 00:04:45,590
out at this link here.

69
00:04:45,770 --> 00:04:48,740
But it depends on how you implement the algorithm, of course.

70
00:04:49,400 --> 00:04:53,450
So after you're comfortable with the algorithm analysis portion of this course or you already understand

71
00:04:53,450 --> 00:04:59,690
how to analyze algorithms formally, you may wish to read about the informal analysis of this algorithm

72
00:04:59,690 --> 00:05:00,500
at the following links.

73
00:05:00,500 --> 00:05:03,980
So this link right here I will put in the resources section as well.

74
00:05:04,730 --> 00:05:11,330
It talks about heap sort, but it also has this build heap with heap of fire and in the initial section

75
00:05:11,330 --> 00:05:19,010
of the paper, and they do a good job explaining why it runs in linear time.

76
00:05:19,010 --> 00:05:25,700
And they compare it to the other build heap that we discussed, which I believe is in log in time.

77
00:05:25,700 --> 00:05:28,270
So that would be worse than just in time, right?

78
00:05:28,280 --> 00:05:28,970
Linear time.

79
00:05:30,380 --> 00:05:36,350
So I am not going to go over the code for these heap algorithms.

80
00:05:36,620 --> 00:05:42,310
They are just implemented with an array, but I encourage you to attempt to implement them, right?

81
00:05:42,320 --> 00:05:47,570
You can just use an array and use the properties we discussed to show where the parents and children

82
00:05:47,570 --> 00:05:47,870
are.

83
00:05:48,500 --> 00:05:52,850
And it should be pretty simple for you to come up with an abstract data type.

84
00:05:53,300 --> 00:05:53,580
Right?

85
00:05:53,600 --> 00:05:59,870
You could make an abstract data type, have a data member as an array, and then you could just go over

86
00:05:59,870 --> 00:06:05,090
what I showed you in the theoretical lectures to implement these algorithms to be able to build a heap.

87
00:06:06,340 --> 00:06:14,230
So with that, we will conclude our discussion about heaps we might later on mention them in the algorithm

88
00:06:14,230 --> 00:06:21,670
analysis section or if you feel comfortable now or after that section, it might be good to check out

89
00:06:21,670 --> 00:06:28,240
this link to see why heaps are so great and efficient and why this specific build heap algorithm is

90
00:06:28,240 --> 00:06:28,960
very efficient.

91
00:06:30,040 --> 00:06:32,400
OK, so with that, I will see you in the next election.