در این مطلب، ویدئو پشته های باینری (حداقل/حداکثر هیپ) در پایتون برای مبتدیان اجرای یک صف اولویت با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:33:34
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,160 –> 00:00:02,720
بچه ها چه خبر، پاتریک اینجا
2
00:00:02,720 –> 00:00:04,960
از newcoder.com است
3
00:00:04,960 –> 00:00:06,879
و در این آموزش قصد داریم در
4
00:00:06,879 –> 00:00:08,800
مورد پشته های باینری در پایتون صحبت کنیم،
5
00:00:08,800 –> 00:00:11,679
بنابراین تا به حال
6
00:00:11,679 –> 00:00:12,559
فقط با
7
00:00:12,559 –> 00:00:15,679
ساختارهای داده خطی مانند یک آرایه
8
00:00:15,679 –> 00:00:16,880
یا یک لیست پیوندی کار می کردیم
9
00:00:16,880 –> 00:00:19,039
اما اکنون ما در حال کار با اولین
10
00:00:19,039 –> 00:00:21,039
ساختار داده غیرخطی خود
11
00:00:21,039 –> 00:00:24,320
به نام هیپ باینری هستیم، بنابراین این یک ساختار داده درختی
12
00:00:24,320 –> 00:00:25,039
است،
13
00:00:25,039 –> 00:00:27,760
بنابراین دو نوع هپ باینری وجود دارد، یک
14
00:00:27,760 –> 00:00:28,080
15
00:00:28,080 –> 00:00:31,199
پشته کوچک و یک هیپ حداکثر در این ویدیو،
16
00:00:31,199 –> 00:00:33,280
ما در مورد نحوه پیاده سازی
17
00:00:33,280 –> 00:00:34,719
min heap با استفاده از
18
00:00:34,719 –> 00:00:38,640
یک آرایه بنابراین برای شروع یک پشته باینری
19
00:00:38,640 –> 00:00:40,160
باید دارای ویژگی های زیر باشد
20
00:00:40,160 –> 00:00:43,120
، اول اینکه یک گره والد
21
00:00:43,120 –> 00:00:43,680
22
00:00:43,680 –> 00:00:47,039
باید حداکثر دو فرزند داشته باشد
23
00:00:47,039 –> 00:00:49,360
، دومین ویژگی این است که یک
24
00:00:49,360 –> 00:00:51,600
پشته باینری باید یک درخت کامل باشد
25
00:00:51,600 –> 00:00:53,760
به این معنی که باید پر شود. از چپ
26
00:00:53,760 –> 00:00:55,680
به راست و هر سطح
27
00:00:55,680 –> 00:00:57,840
باید پر باشد به استثنای
28
00:00:57,840 –> 00:00:59,600
آخرین سطح که نیازی به
29
00:00:59,600 –> 00:01:02,239
پر بودن ندارد، بنابراین در اینجا یک مثال از یک
30
00:01:02,239 –> 00:01:02,960
درخت کامل است
31
00:01:02,960 –> 00:01:05,040
که می توانید ببینید که هر سه سطح پر هستند
32
00:01:05,040 –> 00:01:06,159
33
00:01:06,159 –> 00:01:08,479
و در اینجا یک مثال دیگر از یک کامل است.
34
00:01:08,479 –> 00:01:09,200
درخت
35
00:01:09,200 –> 00:01:11,680
، دو سطح اول پر است و سطح
36
00:01:11,680 –> 00:01:12,400
37
00:01:12,400 –> 00:01:15,040
آخر پر نیست، اما از چپ به راست پر شده است،
38
00:01:15,040 –> 00:01:15,600
39
00:01:15,600 –> 00:01:18,640
بنابراین این نیز معتبر است، این
40
00:01:18,640 –> 00:01:20,400
نمونه ای از درخت
41
00:01:20,400 –> 00:01:22,960
کامل نیست زیرا سطح یک
42
00:01:22,960 –> 00:01:25,119
قبل از رفتن به سطح دو کاملاً پر نیست
43
00:01:25,119 –> 00:01:27,759
و یک بار دیگر در اینجا مثال دیگری
44
00:01:27,759 –> 00:01:29,840
از درختی است که یک درخت کامل
45
00:01:29,840 –> 00:01:32,000
نیست و این یک درخت کامل نیست زیرا
46
00:01:32,000 –> 00:01:32,960
در سطح
47
00:01:32,960 –> 00:01:35,600
دو شروع به پر کردن درخت خود از سمت راست می
48
00:01:35,600 –> 00:01:37,280
کنیم، باید از چپ شروع می کردیم
49
00:01:37,280 –> 00:01:39,439
و به راست می رفتیم تا سطح
50
00:01:39,439 –> 00:01:40,320
51
00:01:40,320 –> 00:01:42,960
بعدی تکمیل شود. بیایید به ویژگی سوم برویم
52
00:01:42,960 –> 00:01:45,280
، ویژگی سوم به این بستگی دارد که
53
00:01:45,280 –> 00:01:46,560
آیا شما یک heap min را پیاده سازی می کنید
54
00:01:46,560 –> 00:01:49,759
یا یک max heap برای min heap،
55
00:01:49,759 –> 00:01:52,640
هر کلید والدین باید کوچکتر از
56
00:01:52,640 –> 00:01:54,079
گره های فرزند خود باشد.
57
00:01:54,079 –> 00:01:56,079
58
00:01:56,079 –> 00:01:57,920
کلید
59
00:01:57,920 –> 00:02:00,719
در داخل پشته برای یک پشته حداکثر
60
00:02:00,719 –> 00:02:02,079
برعکس درست
61
00:02:02,079 –> 00:02:04,320
است. کلید هر والدین باید بزرگتر از
62
00:02:04,320 –> 00:02:05,119
63
00:02:05,119 –> 00:02:08,080
گره های فرزندش باشد.
64
00:02:08,080 –> 00:02:09,598
65
00:02:09,598 –> 00:02:11,680
66
00:02:11,680 –> 00:02:13,120
67
00:02:13,120 –> 00:02:15,360
بیایید در مورد درج داده ها در پشته min صحبت کنیم،
68
00:02:15,360 –> 00:02:17,680
بنابراین فرض کنید که من می خواهم 10 را وارد کنم، به
69
00:02:17,680 –> 00:02:18,239
70
00:02:18,239 –> 00:02:21,440
عنوان مثال چون پشته ما خالی است،
71
00:02:21,440 –> 00:02:24,160
10 تبدیل به گره ریشه می شود، حالا بیایید 20 را وارد کنیم،
72
00:02:24,160 –> 00:02:25,120
73
00:02:25,120 –> 00:02:28,000
بنابراین به یاد داشته باشید که همیشه پشته خود را از
74
00:02:28,000 –> 00:02:28,560
سمت چپ
75
00:02:28,560 –> 00:02:31,680
ترین موقعیت پر می کنیم، بنابراین 20 تبدیل به گره اصلی می شود. فرزند باقی مانده
76
00:02:31,680 –> 00:02:32,720
از 10.
77
00:02:32,720 –> 00:02:35,360
پس از درج 20، باید ویژگی
78
00:02:35,360 –> 00:02:36,000
min heap
79
00:02:36,000 –> 00:02:38,160
را حفظ کنیم که گره والد
80
00:02:38,160 –> 00:02:39,360
همیشه باید کمتر
81
00:02:39,360 –> 00:02:41,599
از فرزند باشد.
82
00:02:41,599 –> 00:02:43,120
83
00:02:43,120 –> 00:02:45,680
84
00:02:45,680 –> 00:02:47,920
85
00:02:47,920 –> 00:02:48,480
86
00:02:48,480 –> 00:02:50,959
تا گره ریشه، بنابراین از آنجایی که 20
87
00:02:50,959 –> 00:02:52,160
بزرگتر از
88
00:02:52,160 –> 00:02:54,319
10 است، کاری برای ما وجود ندارد و
89
00:02:54,319 –> 00:02:56,239
خاصیت heap ما دست نخورده باقی می ماند و
90
00:02:56,239 –> 00:02:59,200
5 را در پشته درج می کنیم که در
91
00:02:59,200 –> 00:03:00,720
سمت چپ ترین موقعیت قرار می دهیم،
92
00:03:00,720 –> 00:03:03,599
بنابراین 5 تبدیل به فرزند راست 10 می شود. اما
93
00:03:03,599 –> 00:03:04,000
اکنون
94
00:03:04,000 –> 00:03:06,640
ویژگی heap ما این است. شکسته شده است زیرا 5
95
00:03:06,640 –> 00:03:07,680
کمتر از 10 است.
96
00:03:07,680 –> 00:03:10,159
برای رفع این مشکل فقط بین دو گره مبادله می
97
00:03:10,159 –> 00:03:10,720
کنیم و
98
00:03:10,720 –> 00:03:12,800
این خاصیت min heap را حفظ می کند
99
00:03:12,800 –> 00:03:15,040
که گره والد همیشه باید کمتر
100
00:03:15,040 –> 00:03:16,000
از فرزندی باشد که
101
00:03:16,000 –> 00:03:18,879
30 را در پشته ای که ما وارد می کنیم قرار می دهد. در
102
00:03:18,879 –> 00:03:20,480
سمت چپ ترین موقعیت،
103
00:03:20,480 –> 00:03:23,040
بنابراین فرزند سمت چپ 20 می شود.
104
00:03:23,040 –> 00:03:24,080
30 کمتر از
105
00:03:24,080 –> 00:03:26,560
20 است، بنابراین کاری برای انجام دادن باقی نمانده
106
00:03:26,560 –> 00:03:27,440
است.
107
00:03:27,440 –> 00:03:30,400
درج 15 اکنون در
108
00:03:30,400 –> 00:03:31,760
سمت چپ ترین موقعیت
109
00:03:31,760 –> 00:03:34,560
قرار می دهیم، بنابراین فرزند سمت راست 20 می شود.
110
00:03:34,560 –> 00:03:35,200
15
111
00:03:35,200 –> 00:03:37,920
کمتر از 20 است. بله، برای حفظ خاصیت حرارتی، اینطور است،
112
00:03:37,920 –> 00:03:39,680
113
00:03:39,680 –> 00:03:42,159
ما آن را با هم عوض می کنیم، سپس به بالا رفتن از درخت ادامه
114
00:03:42,159 –> 00:03:43,840
می دهیم تا مطمئن شویم که خاصیت گرمایی
115
00:03:43,840 –> 00:03:44,640
حفظ شده است،
116
00:03:44,640 –> 00:03:47,120
بنابراین بررسی می کنیم که آیا 15 کمتر از
117
00:03:47,120 –> 00:03:47,680
5
118
00:03:47,680 –> 00:03:50,239
است، بنابراین کاری برای
119
00:03:50,239 –> 00:03:52,239
درج سه در آن باقی نمانده است. پشته ای را
120
00:03:52,239 –> 00:03:55,040
که در سمت چپ ترین موقعیت قرار
121
00:03:55,040 –> 00:03:56,480
می دهیم، به فرزند سمت چپ ده تبدیل می شود،
122
00:03:56,480 –> 00:03:59,599
اکنون زمان آن رسیده که درخت ما
123
00:03:59,599 –> 00:04:02,799
سه تا کمتر از ده باشد، بنابراین ما
124
00:04:02,799 –> 00:04:03,599
125
00:04:03,599 –> 00:04:06,879
سه تا کمتر از پنج را عوض می کنیم، بنابراین یک بار
126
00:04:06,879 –> 00:04:07,439
دیگر
127
00:04:07,439 –> 00:04:10,799
مثال نهایی را با درج صفر عوض می کنیم.
128
00:04:10,799 –> 00:04:11,599
در پشتهای که
129
00:04:11,599 –> 00:04:14,480
در سمت چپترین موقعیت قرار میدهیم
130
00:04:14,480 –> 00:04:16,399
، به فرزند راست پنج
131
00:04:16,399 –> 00:04:19,600
تبدیل میشود درخت ما صفر کمتر از
132
00:04:19,600 –> 00:04:20,320
پنج است
133
00:04:20,320 –> 00:04:23,199
بله، بنابراین ما ادامه میدهیم و مبادله
134
00:04:23,199 –> 00:04:23,759
صفر
135
00:04:23,759 –> 00:04:26,639
کمتر از سه است بله، بنابراین ما
136
00:04:26,639 –> 00:04:27,120
اینجا
137
00:04:27,120 –> 00:04:30,639
را نیز عوض میکنیم، بنابراین اکنون بیایید در مورد چگونگی ما صحبت کنیم
138
00:04:30,639 –> 00:04:32,880
139
00:04:32,880 –> 00:04:34,400
140
00:04:34,400 –> 00:04:37,120
141
00:04:37,120 –> 00:04:38,960
142
00:04:38,960 –> 00:04:40,080
143
00:04:40,080 –> 00:04:42,320
144
00:04:42,320 –> 00:04:43,759
145
00:04:43,759 –> 00:04:46,720
میتوانیم کوچکترین عنصر را در پشتهی خود حذف کنیم، زیرا این یک پشته کوچک است، گره ریشه ما همیشه تضمین میکند که کوچکترین عنصر را در داخل گرما نگه دارد، بنابراین حذف کوچکترین عنصر بیاهمیت است، ما فقط صفر را از پشته حذف میکنیم، اما
146
00:04:46,720 –> 00:04:47,360
اکنون
147
00:04:47,360 –> 00:04:49,440
هیپ ما دارای یک ریشه خالی است، بنابراین ما به
148
00:04:49,440 –> 00:04:50,960
چیزی برای
149
00:04:50,960 –> 00:04:53,520
جایگزینی آن نیاز داریم، بنابراین آن را با عنصر در
150
00:04:53,520 –> 00:04:54,479
پایان گرما جایگزین می کنیم،
151
00:04:54,479 –> 00:04:57,440
بنابراین در این مورد، اکنون پنج است، درست مانند
152
00:04:57,440 –> 00:04:59,520
زمانی که آن را در پشته خود قرار می دهیم،
153
00:04:59,520 –> 00:05:02,080
هنگام برداشتن، باید مطمئن شویم که
154
00:05:02,080 –> 00:05:03,360
خاصیت گرمایی ما
155
00:05:03,360 –> 00:05:06,080
باقی می ماند. دست نخورده است که هر گره والد
156
00:05:06,080 –> 00:05:07,680
کوچکتر از فرزند خود است،
157
00:05:07,680 –> 00:05:10,240
بنابراین ما آنقدر پایین می آوریم تا زمانی که گره دیگری وجود نداشته باشد،
158
00:05:10,240 –> 00:05:11,199
159
00:05:11,199 –> 00:05:13,360
بررسی می کنیم تا کوچکترین گره بین دو فرزند را ببینیم،
160
00:05:13,360 –> 00:05:14,400
161
00:05:14,400 –> 00:05:16,479
بنابراین فرزند مناسب تنها فرزند
162
00:05:16,479 –> 00:05:17,600
کوچکتر از پنج است،
163
00:05:17,600 –> 00:05:20,639
بنابراین ما بین این دو قرار می دهیم و اکنون بررسی می کنیم.
164
00:05:20,639 –> 00:05:21,759
برای اینکه ببینیم
165
00:05:21,759 –> 00:05:24,320
ده کمتر از پنج است، اینطور نیست، بنابراین
166
00:05:24,320 –> 00:05:25,600
کاری برای
167
00:05:25,600 –> 00:05:28,080
168
00:05:28,080 –> 00:05:29,600
169
00:05:29,600 –> 00:05:31,840
170
00:05:31,840 –> 00:05:34,080
انجام دادن باقی نمانده است.
171
00:05:34,080 –> 00:05:35,199
در داخل پشته ما
172
00:05:35,199 –> 00:05:38,479
که ده زمان برای انباشته شدن است، بنابراین
173
00:05:38,479 –> 00:05:40,639
ما بین دو فرزند
174
00:05:40,639 –> 00:05:41,840
کوچکترین عنصر را بررسی می کنیم
175
00:05:41,840 –> 00:05:44,479
زیرا 5 تنها فرزند کوچکتر از
176
00:05:44,479 –> 00:05:45,039
10 است
177
00:05:45,039 –> 00:05:48,479
که با 5 تعویض می کنیم. مثال آخر ما ادامه می دهیم
178
00:05:48,479 –> 00:05:50,320
و حداقل عنصر را حذف می
179
00:05:50,320 –> 00:05:52,639
کنیم و سپس آن را با آن جایگزین می کنیم. آخرین عنصر
180
00:05:52,639 –> 00:05:53,680
درون پشته،
181
00:05:53,680 –> 00:05:56,720
20 را با دو فرزند آن مقایسه می کنیم
182
00:05:56,720 –> 00:05:58,960
و کوچکترین آن دو را می گیریم، بنابراین
183
00:05:58,960 –> 00:06:00,319
آن را با 10 تعویض می کنیم.
184
00:06:00,319 –> 00:06:02,160
بنابراین حالا بیایید در مورد اینکه چگونه می
185
00:06:02,160 –> 00:06:03,759
خواهیم یک پشته را
186
00:06:03,759 –> 00:06:06,160
با استفاده از یک آرایه به منظور انجام این کار نشان دهیم، صحبت کنیم.
187
00:06:06,160 –> 00:06:08,080
188
00:06:08,080 –> 00:06:10,639
برای محاسبه شاخص والد یک گره معین به چند فرمول نیاز
189
00:06:10,639 –> 00:06:11,360
190
00:06:11,360 –> 00:06:14,160
داریم، کف شاخص منهای 1 را
191
00:06:14,160 –> 00:06:15,520
تقسیم بر 2
192
00:06:15,520 –> 00:06:17,759
193
00:06:17,759 –> 00:06:18,639
می
194
00:06:18,639 –> 00:06:21,600
کنیم.
195
00:06:21,600 –> 00:06:23,280
برای محاسبه شاخص فرزند مناسب
196
00:06:23,280 –> 00:06:26,319
، دو برابر شاخص بعلاوه دو می گیریم،
197
00:06:26,319 –> 00:06:27,039
198
00:06:27,039 –> 00:06:29,840
بنابراین با توجه به پشته کوچک زیر، اجازه دهید به
199
00:06:29,840 –> 00:06:31,680
جلو برویم و آن را به یک آرایه تبدیل کنیم،
200
00:06:31,680 –> 00:06:34,800
مرحله اول ریشه همیشه در
201
00:06:34,800 –> 00:06:37,199
شاخص صفر است، پس بیایید ادامه دهیم و
202
00:06:37,199 –> 00:06:39,199
یک را در اندیس صفر ذخیره
203
00:06:39,199 –> 00:06:41,280
کنیم. ریشه را محاسبه کنید بچه گره ها
204
00:06:41,280 –> 00:06:43,280
با استفاده از فرمول فرزند چپ
205
00:06:43,280 –> 00:06:45,919
ما از شاخص ریشه استفاده می کنیم که
206
00:06:45,919 –> 00:06:46,639
صفر است،
207
00:06:46,639 –> 00:06:49,120
بنابراین دو برابر صفر به علاوه یک
208
00:06:49,120 –> 00:06:50,000
شاخص
209
00:06:50,000 –> 00:06:53,199
یک را به ما می دهد، بنابراین ما دو را در شاخص یک ذخیره
210
00:06:53,199 –> 00:06:55,680
211
00:06:55,680 –> 00:06:56,639
212
00:06:56,639 –> 00:06:59,520
می کنیم. شاخص دو،
213
00:06:59,520 –> 00:07:00,639
بنابراین ما سه را
214
00:07:00,639 –> 00:07:03,599
در شاخص دو ذخیره کردیم، ادامه می دهیم و
215
00:07:03,599 –> 00:07:05,520
فرزندان دو را
216
00:07:05,520 –> 00:07:08,479
217
00:07:08,479 –> 00:07:10,880
218
00:07:10,880 –> 00:07:13,199
219
00:07:13,199 –> 00:07:14,080
220
00:07:14,080 –> 00:07:16,400
محاسبه می کنیم. فرزند مناسب
221
00:07:16,400 –> 00:07:17,919
ما دو برابر
222
00:07:17,919 –> 00:07:20,960
یک به علاوه دو می گیریم که به ما چهار می دهد، بنابراین
223
00:07:20,960 –> 00:07:21,520
224
00:07:21,520 –> 00:07:24,240
پنج را در شاخص چهار ذخیره می کنیم و
225
00:07:24,240 –> 00:07:25,199
بقیه آرایه را پر می
226
00:07:25,199 –> 00:07:27,680
کنیم، اکنون که آرایه ما پر است باید موارد زیر را بدست آوریم
227
00:07:27,680 –> 00:07:28,960
،
228
00:07:28,960 –> 00:07:31,039
بیایید جلو برویم و آزمایش کنیم تا ببینیم آیا
229
00:07:31,039 –> 00:07:32,639
والد فرمول ایندکس
230
00:07:32,639 –> 00:07:35,120
کار می کند، بنابراین فرض کنید من می خواهم شاخص والد 4 را محاسبه کنم، به
231
00:07:35,120 –> 00:07:36,720
232
00:07:36,720 –> 00:07:40,160
عنوان مثال 4 در شاخص 3 است،
233
00:07:40,160 –> 00:07:43,759
بنابراین 3 منهای 1 به دست می آوریم که
234
00:07:43,759 –> 00:07:46,960
دو تقسیم بر دو به ما می دهد، به ما یک می دهد و
235
00:07:46,960 –> 00:07:48,479
اگر کف یکی
236
00:07:48,479 –> 00:07:50,879
را بگیرید، فقط به دست می آورید. یکی پس اگر بخواهیم
237
00:07:50,879 –> 00:07:52,000
نمایه یک را بررسی
238
00:07:52,000 –> 00:07:54,319
کنید، میبینید که فرمول واقعاً
239
00:07:54,319 –> 00:07:55,840
کار میکند و گره
240
00:07:55,840 –> 00:07:58,720
دو را به عنوان گره والد دریافت میکنیم، بنابراین از
241
00:07:58,720 –> 00:07:59,280
اینجا
242
00:07:59,280 –> 00:08:01,360
به کد وارد میشویم و
243
00:08:01,360 –> 00:08:02,479
کلاسی
244
00:08:02,479 –> 00:08:04,960
به نام min heap ایجاد میکنیم و در min heap
245
00:08:04,960 –> 00:08:05,680
246
00:08:05,680 –> 00:08:08,400
خود، شبکه خود را تعریف میکنیم. روش روش بافتنی ما
247
00:08:08,400 –> 00:08:09,520
دو پارامتر خواهد داشت پارامتر
248
00:08:09,520 –> 00:08:12,160
خودمان و ظرفیت
249
00:08:12,160 –> 00:08:14,240
ظرفیت حداکثر تعداد
250
00:08:14,240 –> 00:08:16,080
عناصری است که می خواهید
251
00:08:16,080 –> 00:08:18,400
در مرحله اول پشته ذخیره کنید، ما
252
00:08:18,400 –> 00:08:20,639
به مکانی برای ذخیره این داده ها نیاز داریم
253
00:08:20,639 –> 00:08:22,800
و همانطور که قبلاً توضیح دادیم.
254
00:08:22,800 –> 00:08:24,720
ما میخواهیم heap خود را
255
00:08:24,720 –> 00:08:27,280
با استفاده از یک آرایه پیادهسازی کنیم، سپس باید
256
00:08:27,280 –> 00:08:28,800
ویژگی ظرفیت را
257
00:08:28,800 –> 00:08:31,440
به ظرفیتی که وارد میشود تنظیم
258
00:08:31,440 –> 00:08:33,519
کنیم و در نهایت ویژگی اندازه خود
259
00:08:33,519 –> 00:08:36,559
را به اندازه صفر که
260
00:08:36,559 –> 00:08:39,599
تعداد عناصر موجود در پشته ما در
261
00:08:39,599 –> 00:08:41,599
مرحله بعدی است مقداردهی اولیه میکنیم. روشهای کمکی فراوانی خواهیم
262
00:08:41,599 –> 00:08:43,599
داشت، اولین روشهای کمکی که
263
00:08:43,599 –> 00:08:44,880
میخواهیم
264
00:08:44,880 –> 00:08:46,959
مرور کنیم به ما کمک میکنند تا شاخصهای
265
00:08:46,959 –> 00:08:48,160
والد و فرزند را
266
00:08:48,160 –> 00:08:50,800
محاسبه کنیم، بنابراین روش دریافت شاخص والد را
267
00:08:50,800 –> 00:08:53,760
که دارای یک پارامتر شاخص است، اعلام میکنیم.
268
00:08:53,760 –> 00:08:56,240
پارامتر شاخص، شاخص
269
00:08:56,240 –> 00:08:57,920
گره ای است که می خواهید شاخص والد آن را پیدا کنید،
270
00:08:57,920 –> 00:08:58,800
271
00:08:58,800 –> 00:09:01,680
بنابراین ما فقط شاخص منهای یک طبقه تقسیم دو را برمی گردانیم،
272
00:09:01,680 –> 00:09:02,880
273
00:09:02,880 –> 00:09:05,920
به طور مشابه، یک
274
00:09:05,920 –> 00:09:08,320
نمایه فرزند سمت چپ خواهیم داشت و آن شاخص فرزند سمت راست را دریافت
275
00:09:08,320 –> 00:09:09,600
276
00:09:09,600 –> 00:09:12,320
می کنیم. همچنین یک پارامتر شاخص داشته باشید، پارامتر ایندکس
277
00:09:12,320 –> 00:09:13,279
278
00:09:13,279 –> 00:09:15,120
که شاخص تهی است که میخواهید شاخص
279
00:09:15,120 –> 00:09:16,880
فرزند چپ یا راست آن را پیدا کنید،
280
00:09:16,880 –> 00:09:19,920
بنابراین برای فرزند چپ ما
281
00:09:19,920 –> 00:09:20,480
282
00:09:20,480 –> 00:09:23,440
2 برابر شاخص به اضافه یک و برای
283
00:09:23,440 –> 00:09:24,240
فرزند راست
284
00:09:24,240 –> 00:09:26,560
ما دو بر میگردانیم. چند برابر ایندکس بعلاوه
285
00:09:26,560 –> 00:09:27,440
دو،
286
00:09:27,440 –> 00:09:29,360
این بار باید چند روش کمکی دیگر تعریف کنیم و
287
00:09:29,360 –> 00:09:31,120
288
00:09:31,120 –> 00:09:33,200
بررسی کنیم که آیا یک گره
289
00:09:33,200 –> 00:09:34,480
دارای
290
00:09:34,480 –> 00:09:37,360
فرزند چپ والدین یا فرزند راست است، بنابراین
291
00:09:37,360 –> 00:09:39,120
روش والد has ما
292
00:09:39,120 –> 00:09:41,839
یک بولین برمی گرداند و یک شاخص خواهیم داشت.
293
00:09:41,839 –> 00:09:42,800
پارامتر
294
00:09:42,800 –> 00:09:44,399
ایندکس گرهای است که میخواهیم بدانیم
295
00:09:44,399 –> 00:09:46,399
آیا والد دارد یا نه،
296
00:09:46,399 –> 00:09:48,720
بنابراین بر اساس بزرگتر یا مساوی
297
00:09:48,720 –> 00:09:50,080
بودن یا نبودن شاخص والد
298
00:09:50,080 –> 00:09:53,279
299
00:09:53,279 –> 00:09:55,839
اگر بزرگتر یا مساوی صفر باشد، یک بولین برمیگردانیم.
300
00:09:55,839 –> 00:09:57,040
پدر و مادر
301
00:09:57,040 –> 00:09:59,120
در غیر این صورت به این معنی است که پدر و مادر
302
00:09:59,120 –> 00:10:00,480
متد index
303
00:10:00,480 –> 00:10:03,040
یک عدد منفی را برمی گرداند،
304
00:10:03,040 –> 00:10:04,240
به این معنی که هیچ راهی وجود ندارد که
305
00:10:04,240 –> 00:10:06,480
این گره بتواند والد داشته باشد، زیرا ما
306
00:10:06,480 –> 00:10:08,079
از یک آرایه استفاده
307
00:10:08,079 –> 00:10:10,240
می کنیم، سپس متد فرزند چپ خود را خواهیم داشت
308
00:10:10,240 –> 00:10:12,880
و روش فرزند سمت راست را
309
00:10:12,880 –> 00:10:13,760
داریم که
310
00:10:13,760 –> 00:10:16,399
امضای متد مشابهی برای فرزند چپ ما دارد.
311
00:10:16,399 –> 00:10:18,000
اگر
312
00:10:18,000 –> 00:10:20,480
شاخص فرزند سمت چپ
313
00:10:20,480 –> 00:10:21,120
314
00:10:21,120 –> 00:10:23,440
از اندازه کوچکتر باشد یا نه، برمی گردانیم، به این معنی که
315
00:10:23,440 –> 00:10:25,519
316
00:10:25,519 –> 00:10:27,760
اگر شاخص فرزند چپ بزرگتر
317
00:10:27,760 –> 00:10:30,480
از ویژگی اندازه باشد، این گره فرزند چپ دارد.
318
00:10:30,480 –> 00:10:32,720
از آنجایی که ویژگی اندازه
319
00:10:32,720 –> 00:10:34,720
تعداد عناصر درون
320
00:10:34,720 –> 00:10:37,120
پشته است، همیشه در آخرین نقطه آزاد موجود
321
00:10:37,120 –> 00:10:38,640
برای درج قرار دارد
322
00:10:38,640 –> 00:10:40,880
که باعث میشود شاخص فرزند
323
00:10:40,880 –> 00:10:42,720
بزرگتر از
324
00:10:42,720 –> 00:10:44,640
همان چیزی باشد که میتوان گفت برای
325
00:10:44,640 –> 00:10:46,000
فرزند مناسب،
326
00:10:46,000 –> 00:10:48,240
خواه ناخواه بازگردد. شاخص فرزند سمت راست
327
00:10:48,240 –> 00:10:49,519
کمتر از اندازه است
328
00:10:49,519 –> 00:10:51,760
اگر اینطور باشد به این معنی که این گره دارای
329
00:10:51,760 –> 00:10:52,720
فرزند راست است
330
00:10:52,720 –> 00:10:55,120
که در حال حرکت است، ما روشهای کمکی برای
331
00:10:55,120 –> 00:10:56,000
دریافت
332
00:10:56,000 –> 00:10:59,120
دادههای واقعی از والدین فرزند چپ و
333
00:10:59,120 –> 00:11:00,000
فرزند راست خواهیم داشت
334
00:11:00,000 –> 00:11:01,560
و این روشها بسیار متفاوت هستند.
335
00:11:01,560 –> 00:11:03,279
f-توضیحات
336
00:11:03,279 –> 00:11:05,279
بعدی ما به دو روش کمکی آخر می رویم.
337
00:11:05,279 –> 00:11:06,560
روش
338
00:11:06,560 –> 00:11:09,519
ما کامل است و روش مبادله ما
339
00:11:09,519 –> 00:11:09,920
340
00:11:09,920 –> 00:11:12,720
متد ما کامل است هر زمان
341
00:11:12,720 –> 00:11:13,519
که می خواهیم
342
00:11:13,519 –> 00:11:16,399
در داخل پشته خود وارد کنیم فراخوانی می شود تا مطمئن شویم که قبل از درج
343
00:11:16,399 –> 00:11:17,519
فضا وجود دارد
344
00:11:17,519 –> 00:11:19,760
و این یک
345
00:11:19,760 –> 00:11:20,720
تست بسیار ساده
346
00:11:20,720 –> 00:11:23,200
که ما فقط برمی گردیم تا ببینیم آیا اندازه با ظرفیت برابر است یا خیر
347
00:11:23,200 –> 00:11:24,880
348
00:11:24,880 –> 00:11:27,120
که به روش کمکی نهایی
349
00:11:27,120 –> 00:11:28,079
به نام
350
00:11:28,079 –> 00:11:30,480
swap فقط روش مبادله استاندارد شماست.
351
00:11:30,480 –> 00:11:31,200
352
00:11:31,200 –> 00:11:33,839
353
00:11:33,839 –> 00:11:36,000
354
00:11:36,000 –> 00:11:36,880
355
00:11:36,880 –> 00:11:39,200
این روش ممکن است هر زمان که
356
00:11:39,200 –> 00:11:41,360
نیاز به احیای مجدد درخت خود داشته باشیم،
357
00:11:41,360 –> 00:11:44,640
هنگامی که میخواهیم عنصری را اضافه یا حذف کنیم، فراخوانی شود،
358
00:11:44,640 –> 00:11:46,720
بنابراین اکنون که روشهای کمکی ما
359
00:11:46,720 –> 00:11:48,800
در مسیر خود قرار ندارند، اجازه دهید پیش برویم و در مورد
360
00:11:48,800 –> 00:11:51,760
درج در پشته خود صحبت کنیم تا روش درج تکراری ما
361
00:11:51,760 –> 00:11:54,079
دارای داده باشد.
362
00:11:54,079 –> 00:11:56,240
دادههایی را که میخواهیم در
363
00:11:56,240 –> 00:11:58,320
پشتههای خود درج کنیم، ابتدا بررسی میکنیم تا ببینیم آیا
364
00:11:58,320 –> 00:12:00,560
فضایی برای درج در پشتههایمان
365
00:12:00,560 –> 00:12:02,720
داریم اگر پشته ما پر است، فقط ادامه میدهیم
366
00:12:02,720 –> 00:12:04,079
و یک خطا پرتاب
367
00:12:04,079 –> 00:12:06,639
میکنیم، سپس ادامه میدهیم و این داده را وارد میکنیم.
368
00:12:06,639 –> 00:12:07,600
در آخرین
369
00:12:07,600 –> 00:12:10,560
موقعیت موجود در پشته خود، هنگامی
370
00:12:10,560 –> 00:12:11,760
که با موفقیت
371
00:12:11,760 –> 00:12:13,920
در پشته قرار داده شدیم، بیایید جلوتر برویم
372
00:12:13,920 –> 00:12:15,519
و اندازه را افزایش دهیم
373
00:12:15,519 –> 00:12:18,160
و در نهایت پس از انجام این کار،
374
00:12:18,160 –> 00:12:20,000
باید مطمئن شویم که داده
375
00:12:20,000 –> 00:12:21,680
ها در موقعیت مناسب ذخیره شده اند،
376
00:12:21,680 –> 00:12:24,000
بنابراین باید ما را فراخوانی کنیم.
377
00:12:24,000 –> 00:12:24,880
روش
378
00:12:24,880 –> 00:12:27,200
heapify up با نگاهی به روش heapify up تکراری
379
00:12:27,200 –> 00:12:28,160
380
00:12:28,160 –> 00:12:30,639
ما از عنصر تازه وارد شده شروع می کنیم
381
00:12:30,639 –> 00:12:31,600
که می تواند
382
00:12:31,600 –> 00:12:34,160
در اندازه منهای یک پیدا شود وقتی به
383
00:12:34,160 –> 00:12:35,120
نقطه شروع خود
384
00:12:35,120 –> 00:12:37,360
رسیدیم باید به بالا رفتن از درخت ادامه
385
00:12:37,360 –> 00:12:38,480
دهیم و آن را پر
386
00:12:38,480 –> 00:12:40,320
کنیم تا مدتی استفاده کنیم. حلقه برای ادامه
387
00:12:40,320 –> 00:12:41,680
راه رفتن تا بالای درخت،
388
00:12:41,680 –> 00:12:43,920
میخواهیم تا زمانی که یک گره والد داریم ادامه دهیم
389
00:12:43,920 –> 00:12:45,040
390
00:12:45,040 –> 00:12:47,519
و تا زمانی که عنصر والد
391
00:12:47,519 –> 00:12:49,279
بزرگتر از عنصر گرهای است که در
392
00:12:49,279 –> 00:12:50,240
حال حاضر
393
00:12:50,240 –> 00:12:52,800
در آن هستیم، در صورتی که لازم باشد بین این
394
00:12:52,800 –> 00:12:53,920
دو شاخص مبادله
395
00:12:53,920 –> 00:12:56,160
کنیم. ویژگی min heap را حفظ کنید
396
00:12:56,160 –> 00:12:57,040
که والد
397
00:12:57,040 –> 00:12:59,279
باید کمتر از فرزند باشد، پس از
398
00:12:59,279 –> 00:13:02,240
تعویض، به پیشروی درخت ادامه میدهیم،
399
00:13:02,240 –> 00:13:04,399
بنابراین صحبت کافی است.
400
00:13:04,399 –> 00:13:06,079
401
00:13:06,079 –> 00:13:09,200
g
402
00:13:09,200 –> 00:13:09,680
10
403
00:13:09,680 –> 00:13:11,920
در پشته، بنابراین ابتدا بررسی می کنیم که
404
00:13:11,920 –> 00:13:13,279
آیا پشته ما پر
405
00:13:13,279 –> 00:13:16,160
است یا نه، بنابراین ما در امتداد حرکت می کنیم، سپس
406
00:13:16,160 –> 00:13:17,040
داده ها را
407
00:13:17,040 –> 00:13:19,519
در آخرین موقعیت موجود ذخیره می کنیم تا
408
00:13:19,519 –> 00:13:21,360
مشخصه اندازه ما صفر باشد،
409
00:13:21,360 –> 00:13:23,440
بنابراین زمانی که این کار را انجام دادیم در آنجا ذخیره خواهیم کرد.
410
00:13:23,440 –> 00:13:25,680
که سپس جلو می رویم و
411
00:13:25,680 –> 00:13:26,560
اندازه را افزایش می
412
00:13:26,560 –> 00:13:29,040
دهیم زیرا با موفقیت آن را در داخل پشته قرار می دهیم
413
00:13:29,040 –> 00:13:29,760
414
00:13:29,760 –> 00:13:32,639
و سپس در نهایت متد heapify
415
00:13:32,639 –> 00:13:33,600
up
416
00:13:33,600 –> 00:13:36,160
خود را در متد heapify up خود فرا می خوانیم،
417
00:13:36,160 –> 00:13:38,399
شاخص آخرین عنصر درون
418
00:13:38,399 –> 00:13:38,880
پشته خود را دریافت می
419
00:13:38,880 –> 00:13:41,199
کنیم و سپس جلو می رویم و while خود را اجرا می کنیم.
420
00:13:41,199 –> 00:13:43,279
حلقه بزنید و بررسی کنید که آیا این گره دارای
421
00:13:43,279 –> 00:13:43,839
422
00:13:43,839 –> 00:13:46,000
والد است یا خیر، بنابراین ما را از
423
00:13:46,000 –> 00:13:48,480
حلقه بیرون میکشد و روش درج ما را برای
424
00:13:48,480 –> 00:13:49,440
بار دوم اجرا میکند و
425
00:13:49,440 –> 00:13:52,000
این بار 20 را درج میکند. ابتدا بررسی
426
00:13:52,000 –> 00:13:52,800
میکنیم که
427
00:13:52,800 –> 00:13:55,360
آیا پشته پر است یا نه، بنابراین ادامه دهید
428
00:13:55,360 –> 00:13:57,360
و 20 را در آخرین
429
00:13:57,360 –> 00:13:58,079
430
00:13:58,079 –> 00:14:00,320
موقعیت موجود در پشته ذخیره کنید، سپس جلو می رویم
431
00:14:00,320 –> 00:14:02,240
و اندازه را افزایش می
432
00:14:02,240 –> 00:14:04,399
دهیم زیرا با موفقیت آن را در پشته قرار می دهیم
433
00:14:04,399 –> 00:14:05,440
، اکنون
434
00:14:05,440 –> 00:14:08,079
تنها کاری که باید انجام شود این است که با فراخوانی heapify خود مطمئن شویم که 20
435
00:14:08,079 –> 00:14:10,079
در نقطه مناسب قرار
436
00:14:10,079 –> 00:14:12,959
گرفته است. تو روش p در متد heapify
437
00:14:12,959 –> 00:14:13,760
438
00:14:13,760 –> 00:14:16,079
up ما ابتدا شاخص
439
00:14:16,079 –> 00:14:17,360
آخرین عنصری را
440
00:14:17,360 –> 00:14:19,680
می گیریم که به تازگی در اجرای حلقه while خود وارد کرده
441
00:14:19,680 –> 00:14:21,680
ایم، سپس بررسی می کنیم که آیا این
442
00:14:21,680 –> 00:14:22,800
گره دارای والد است یا خیر
443
00:14:22,800 –> 00:14:25,040
که آن را مقایسه می کنیم تا
444
00:14:25,040 –> 00:14:27,519
ببینیم والد بزرگتر از مقدار است یا خیر. بچه
445
00:14:27,519 –> 00:14:29,440
اینطور نیست ما از حلقه while بیرون رانده می شویم و
446
00:14:29,440 –> 00:14:30,720
447
00:14:30,720 –> 00:14:33,279
روش درج خود را یک بار دیگر اجرا می کنیم،
448
00:14:33,279 –> 00:14:34,560
این بار با گذشتن از
449
00:14:34,560 –> 00:14:37,279
5 به عنوان آرگومان ابتدا بررسی می کنیم که
450
00:14:37,279 –> 00:14:38,560
آیا پشته پر
451
00:14:38,560 –> 00:14:41,360
است یا نه، بنابراین جلو می رویم و می گوییم 5
452
00:14:41,360 –> 00:14:42,639
در آخرین موقعیت
453
00:14:42,639 –> 00:14:44,800
در داخل پشته خود را ادامه می دهیم و
454
00:14:44,800 –> 00:14:46,240
اندازه را افزایش می
455
00:14:46,240 –> 00:14:49,279
دهیم زیرا با موفقیت آن را به پشته اضافه می کنیم،
456
00:14:49,279 –> 00:14:51,600
اکنون زمان آن است که آزمایش کنیم تا ببینیم آیا 5
457
00:14:51,600 –> 00:14:53,600
در موقعیت صحیح قرار
458
00:14:53,600 –> 00:14:56,560
گرفته است یا خیر، ابتدا با فراخوانی روش heapify up
459
00:14:56,560 –> 00:14:58,720
، شاخص آخرین عنصر را دریافت می کنیم.
460
00:14:58,720 –> 00:15:00,079
درج
461
00:15:00,079 –> 00:15:02,880
بعدی بیایید حلقه while خود را اجرا کنیم آیا
462
00:15:02,880 –> 00:15:04,480
این گره دارای والد است
463
00:15:04,480 –> 00:15:07,199
بله والد بزرگتر
464
00:15:07,199 –> 00:15:08,240
از فرزندش است
465
00:15:08,240 –> 00:15:11,120
بله بنابراین ما ادامه می دهیم و داده ها را
466
00:15:11,120 –> 00:15:12,000
بین دو
467
00:15:12,000 –> 00:15:15,040
گره مبادله می کنیم سپس جلو می رویم و
468
00:15:15,040 –> 00:15:15,920
درخت را به سمت بالا پیش می
469
00:15:15,920 –> 00:15:18,560
بریم و w ما را اجرا می کنیم حلقه hile یک بار دیگر آیا
470
00:15:18,560 –> 00:15:20,079
این گره یک والد
471
00:15:20,079 –> 00:15:22,480
دارد، بنابراین کاری برای انجام دادن باقی نمانده است،
472
00:15:22,480 –> 00:15:24,240
بنابراین ما از حلقه خارج می شویم،
473
00:15:24,240 –> 00:15:26,800
بنابراین از اینجا تا حد زیادی می دانیم
474
00:15:26,800 –> 00:15:28,000
که نسخه تکراری
475
00:15:28,000 –> 00:15:30,880
روش heapify up ما چگونه کار می کند،
476
00:15:30,880 –> 00:15:31,199
اما
477
00:15:31,199 –> 00:15:33,600
درختان به طور طبیعی هستند. بازگشتی پس بیایید
478
00:15:33,600 –> 00:15:35,279
پیاده سازی بازگشتی را
479
00:15:35,279 –> 00:15:37,920
ادامه دهیم، بنابراین ابتدا باید
480
00:15:37,920 –> 00:15:38,720
یک
481
00:15:38,720 –> 00:15:41,279
ویرایش جزئی در متد insert خود انجام دهیم، زمانی که می
482
00:15:41,279 –> 00:15:42,800
خواهیم متد heapify
483
00:15:42,800 –> 00:15:45,199
up خود را فراخوانی کنیم، باید
484
00:15:45,199 –> 00:15:47,600
فهرست آخرین عنصری را که به تازگی درج
485
00:15:47,600 –> 00:15:50,240
کرده ایم، با نگاهی به heapify خود پاس کنیم. روش up
486
00:15:50,240 –> 00:15:51,920
ما باید امضای متد را تغییر دهیم
487
00:15:51,920 –> 00:15:52,720
488
00:15:52,720 –> 00:15:54,800
زیرا در حال ارسال یک آرگومان هستیم، بنابراین
489
00:15:54,800 –> 00:15:56,480
اکنون یک پارامتر شاخص
490
00:15:56,480 –> 00:15:58,320
داریم از آنجایی که در حال خروج از ایندکس هستیم
491
00:15:58,320 –> 00:15:59,839
که به عنوان یک آرگومان ارسال
492
00:15:59,839 –> 00:16:02,240
می شود، دیگر نیازی به محاسبه شاخص
493
00:16:02,240 –> 00:16:03,440
درون heapify up خود نداریم
494
00:16:03,440 –> 00:16:06,320
. روش بعدی ما هنوز باید
495
00:16:06,320 –> 00:16:07,040
از درخت بالا برویم
496
00:16:07,040 –> 00:16:09,360
تا بتوانیم شرایطی را
497
00:16:09,360 –> 00:16:10,079
که
498
00:16:10,079 –> 00:16:12,480
در حلقه while استفاده می کنیم با نسخه تکرار شونده بدزدیم
499
00:16:12,480 –> 00:16:13,199
500
00:16:13,199 –> 00:16:16,000
و فقط از آن به عنوان یک if استفاده کنیم، بنابراین اگر
501
00:16:16,000 –> 00:16:17,600
این شرط درست
502
00:16:17,600 –> 00:16:20,000
نیست، نیازی به ادامه نیست، اما اگر
503
00:16:20,000 –> 00:16:22,240
درست باشد، دادهها را بین دو گره عوض
504
00:16:22,240 –> 00:16:22,800
505
00:16:22,800 –> 00:16:24,880
میکنیم تا گرهی که در حال حاضر در
506
00:16:24,880 –> 00:16:26,079
507
00:16:26,079 –> 00:16:28,560
آن قرار داریم و گره والد، و سپس به صورت بازگشتی از درخت بالا میرویم و
508
00:16:28,560 –> 00:16:29,920
با عبور از
509
00:16:29,920 –> 00:16:32,959
نمایه والد به روش heapify up خود، کاملاً درست است.
510
00:16:32,959 –> 00:16:34,079
بنابراین از اینجا
511
00:16:34,079 –> 00:16:35,759
اجازه دهید به اجرای بازگشتی خود بپردازیم،
512
00:16:35,759 –> 00:16:38,079
بنابراین ما
513
00:16:38,079 –> 00:16:40,000
پشته فراخوانی خود را فقط برای ردیابی
514
00:16:40,000 –> 00:16:42,639
متدهای اصلی خواهیم داشت، بنابراین روش درج خود را
515
00:16:42,639 –> 00:16:43,600
یک بار دیگر
516
00:16:43,600 –> 00:16:46,160
این بار با گذشتن از 8 فراخوانی می کنیم. بنابراین اجازه دهید
517
00:16:46,160 –> 00:16:47,759
این را در بالای پشته فشار
518
00:16:47,759 –> 00:16:50,399
دهیم و سپس بررسی کنیم تا ببینید اگر پشته پر است
519
00:16:50,399 –> 00:16:51,279
، اینطور نیست،
520
00:16:51,279 –> 00:16:53,600
بنابراین ما جلو می رویم و 8 را در
521
00:16:53,600 –> 00:16:55,600
آخرین موقعیت در گرما ذخیره می
522
00:16:55,600 –> 00:16:57,600
کنیم، سپس جلو می رویم و بعد از درج اندازه را افزایش می دهیم
523
00:16:57,600 –> 00:16:58,959
524
00:16:58,959 –> 00:17:01,279
و در نهایت ادامه می دهیم و
525
00:17:01,279 –> 00:17:02,000
526
00:17:02,000 –> 00:17:04,400
روش heapify up خود را این بار با عبور از شاخص استفاده می کنیم
527
00:17:04,400 –> 00:17:06,400
. آخرین عنصر داخل پشته
528
00:17:06,400 –> 00:17:09,039
که باید سه باشد، بنابراین ما آن
529
00:17:09,039 –> 00:17:10,480
را به پشته فشار می دهیم و همچنین
530
00:17:10,480 –> 00:17:13,039
در روش heapify up خود بررسی می کنیم
531
00:17:13,039 –> 00:17:15,039
که آیا گره ای که در حال حاضر در
532
00:17:15,0