راهنمای Heaps در پایتون

معرفی

فرودگاهی شلوغ را تصور کنید که هر دقیقه پروازهایی از آن بلند و فرود می‌آیند. همانطور که کنترل‌کننده‌های ترافیک هوایی پروازها را بر اساس فوریت اولویت‌بندی می‌کنند، heaps به ما کمک می‌کند تا داده‌ها را بر اساس معیارهای خاص مدیریت و پردازش کنیم و اطمینان حاصل کنیم که «فوری‌ترین» یا «مهم‌ترین» داده‌ها همیشه در بالای صفحه قابل دسترسی هستند.

در این راهنما، ما سفری را برای درک انبوهی از زمین آغاز خواهیم کرد. ما با ابهام زدایی از چیستی پشته ها و ویژگی های ذاتی آنها شروع می کنیم. از آنجا، ما به پیاده‌سازی پشته‌ها توسط پایتون می‌پردازیم heapq ماژول، و مجموعه غنی از قابلیت های آن را کشف کنید. بنابراین، اگر تا به حال به این فکر کرده‌اید که چگونه می‌توانید مجموعه‌ای از داده‌های پویا را که اغلب به بالاترین (یا پایین‌ترین) اولویت نیاز است، به‌طور کارآمد مدیریت کنید، در انتظار شما هستید.

هیپ چیست؟

اولین چیزی که می خواهید قبل از فرو رفتن در استفاده از پشته ها بدانید این است پشته چیست. یک پشته در دنیای ساختارهای داده به عنوان یک نیروگاه مبتنی بر درخت برجسته است، به ویژه در حفظ نظم و سلسله مراتب. در حالی که ممکن است برای چشمان آموزش ندیده شبیه یک درخت دوتایی باشد، تفاوت های ظریف در ساختار و قوانین حاکم بر آن به طور مشخص آن را متمایز می کند.

یکی از ویژگی های تعیین کننده یک پشته ماهیت آن به عنوان یک است درخت باینری کامل. این بدان معنی است که هر سطح درخت، به جز آخرین سطح، به طور کامل پر شده است. در این آخرین سطح، گره ها از چپ به راست پر می شوند. چنین ساختاری تضمین می‌کند که پشته‌ها را می‌توان به‌طور کارآمد با استفاده از آرایه‌ها یا فهرست‌ها نشان داد و دستکاری کرد، با موقعیت هر عنصر در آرایه منعکس کننده محل قرارگیری آن در درخت.

با این حال، جوهر واقعی یک توده در آن نهفته است مرتب سازی. در یک حداکثر انبوه، مقدار هر گره داده شده از مقادیر فرزندان خود فراتر می رود یا برابر است و بزرگترین عنصر را درست در ریشه قرار می دهد. از سوی دیگر، الف پشته دقیقه بر اساس اصل مخالف عمل می کند: مقدار هر گره یا کمتر یا برابر با مقادیر فرزندان آن است، و اطمینان می دهد که کوچکترین عنصر در ریشه قرار می گیرد.

همانطور که پیشرفت می کنیم، عمیق تر به این می پردازیم که چگونه این ویژگی های ذاتی heap ها عملیات کارآمد را ممکن می کند و چگونه پایتون heapq ماژول به طور یکپارچه انبوهی را در تلاش های کدنویسی ما ادغام می کند.

ویژگی ها و خواص هیپ ها

Heap ها با ساختار منحصر به فرد و اصول نظم دهی خود، مجموعه ای از ویژگی ها و ویژگی های متمایز را ارائه می دهند که آنها را در سناریوهای محاسباتی مختلف ارزشمند می کند.

اول و مهمتر از همه، پشته ها هستند ذاتا کارآمد. ساختار درختی آنها، به‌ویژه قالب درخت دودویی کامل، تضمین می‌کند که عملیاتی مانند درج و استخراج عناصر اولویت (حداکثر یا حداقل) را می‌توان در زمان لگاریتمی انجام داد، معمولا O (ورود به سیستم). این کارایی برای الگوریتم‌ها و برنامه‌هایی که نیاز به دسترسی مکرر به عناصر اولویت دارند، امتیازی است.

یکی دیگر از ویژگی های قابل توجه کپه ها آنها هستند کارایی حافظه. از آنجایی که هپ‌ها را می‌توان با استفاده از آرایه‌ها یا لیست‌ها بدون نیاز به اشاره‌گرهای صریح به گره‌های فرزند یا والد نشان داد، در فضا صرفه‌جویی می‌کنند. موقعیت هر عنصر در آرایه با قرارگیری آن در درخت مطابقت دارد و امکان پیمایش و دستکاری قابل پیش بینی و ساده را فراهم می کند.

خاصیت سفارش دهی هپ ها، چه به صورت max heap یا min heap، این امر را تضمین می کند ریشه همیشه عنصر بالاترین اولویت را دارد. این ترتیب ثابت چیزی است که امکان دسترسی سریع به عنصر با اولویت را بدون نیاز به جستجو در کل ساختار فراهم می کند.

علاوه بر این، پشته ها هستند همه کاره. در حالی که هپ های باینری (که در آن هر والدین حداکثر دو فرزند دارند) رایج ترین هستند، هپ ها را می توان به بیش از دو فرزند تعمیم داد، که به عنوان شناخته شده است. پشته های d-ary. این انعطاف پذیری امکان تنظیم دقیق بر اساس موارد استفاده خاص و الزامات عملکرد را فراهم می کند.

در نهایت، پشته ها هستند خود تنظیم. هر زمان که عناصر اضافه یا حذف شوند، ساختار خود را مجدداً تنظیم می کند تا خواص خود را حفظ کند. این تعادل پویا تضمین می کند که هیپ همیشه برای عملیات اصلی خود بهینه می ماند.

با کاوش عمیق‌تر در پیاده‌سازی و کاربردهای عملی پایتون، پتانسیل واقعی heaps در برابر ما آشکار می‌شود.

انواع هیپ ها

همه توده ها یکسان ایجاد نمی شوند. بسته به ترتیب و ویژگی‌های ساختاری، هپ‌ها را می‌توان به انواع مختلفی دسته‌بندی کرد که هر کدام مجموعه‌ای از کاربردها و مزایای خاص خود را دارند. دو دسته اصلی هستند حداکثر انبوه و پشته دقیقه.

متمایزترین ویژگی الف حداکثر انبوه این است که مقدار هر گره داده شده بزرگتر یا برابر با مقادیر فرزندان آن است. این تضمین می کند که بزرگترین عنصر در پشته همیشه در ریشه قرار دارد. چنین ساختاری به ویژه زمانی مفید است که نیاز به دسترسی مکرر به حداکثر عنصر وجود داشته باشد، مانند اجرای صف های اولویت خاص.

همتای حداکثر هیپ، a پشته دقیقه تضمین می کند که مقدار هر گره داده شده کمتر یا برابر با مقادیر فرزندان آن باشد. این کوچکترین عنصر پشته را در ریشه قرار می دهد. انبوه های حداقل در سناریوهایی که کمترین عنصر از اهمیت بالایی برخوردار است، مانند الگوریتم هایی که با پردازش بلادرنگ داده سروکار دارند، بسیار ارزشمند هستند.

فراتر از این دسته بندی های اولیه، هپ ها را می توان بر اساس فاکتور انشعاب آنها نیز متمایز کرد:

در حالی که پشته های باینری رایج ترین هستند، با هر یک از والدین حداکثر دو فرزند، مفهوم هپ ها را می توان به گره هایی که بیش از دو فرزند دارند تعمیم داد. در یک پشته d-ary، هر گره حداکثر دارد d فرزندان. این تنوع را می توان برای سناریوهای خاص، مانند کاهش ارتفاع درخت برای سرعت بخشیدن به عملیات خاص، بهینه کرد.

دوجمله ای هیپ مجموعه ای از درختان دو جمله ای است که به صورت بازگشتی تعریف می شوند. پشته های دوجمله ای در اجرای صف های اولویت دار استفاده می شوند و عملیات ادغام کارآمد را ارائه می دهند.

نام آن از دنباله معروف فیبوناچی، the پشته فیبوناچی زمان اجرای استهلاک بهتری را برای بسیاری از عملیات در مقایسه با پشته های باینری یا دو جمله ای ارائه می دهد. آنها به ویژه در الگوریتم های بهینه سازی شبکه مفید هستند.

پیاده سازی هیپ پایتون – The heapq ماژول ها

پایتون یک ماژول داخلی برای عملیات پشته ارائه می دهد - the heapq مدول. این ماژول مجموعه ای از توابع مرتبط با heap را ارائه می دهد که به توسعه دهندگان این امکان را می دهد تا لیست ها را به heap تبدیل کرده و بدون نیاز به پیاده سازی سفارشی، عملیات های مختلف heap را انجام دهند. بیایید به تفاوت‌های ظریف این ماژول و اینکه چگونه قدرت پشته‌ها را برای شما به ارمغان می‌آورد، بپردازیم.

La heapq ماژول یک نوع داده پشته متمایز ارائه نمی دهد. در عوض، توابعی را ارائه می‌دهد که روی لیست‌های پایتون معمولی کار می‌کنند، آنها را تبدیل می‌کند و به‌عنوان آن‌ها رفتار می‌کند پشته های باینری.

این رویکرد هم از نظر حافظه کارآمد است و هم به طور یکپارچه با ساختارهای داده موجود پایتون ادغام می شود.

این یعنی پشته ها به صورت لیست نشان داده می شوند in heapq. زیبایی این نمایش در سادگی آن است - سیستم فهرست فهرست مبتنی بر صفر به عنوان یک درخت باینری ضمنی عمل می کند. برای هر عنصر معین در موقعیت i، آن:

• کودک چپ در موقعیت است 2*i + 1
• کودک راست در موقعیت است 2*i + 2
• گره والد در موقعیت است (i-1)//2

این ساختار ضمنی تضمین می کند که نیازی به نمایش درخت باینری مبتنی بر گره جداگانه وجود ندارد و عملیات را ساده می کند و استفاده از حافظه را به حداقل می رساند.

ذکر این نکته ضروری است که heapq واحد به صورت پیش‌فرض تعداد min heap ایجاد می‌کند. این بدان معنی است که کوچکترین عنصر همیشه در ریشه (یا اولین موقعیت در لیست) است. اگر به یک پشته حداکثر نیاز دارید، باید ترتیب را با ضرب عناصر در برعکس کنید -1 یا از یک تابع مقایسه سفارشی استفاده کنید.

پایتون heapq ماژول مجموعه ای از توابع را ارائه می دهد که به توسعه دهندگان اجازه می دهد تا عملیات پشته های مختلف را در لیست ها انجام دهند.

در بخش‌های بعدی، به عمق هر یک از این عملیات‌های اساسی می‌پردازیم، مکانیک و موارد استفاده آن‌ها را بررسی می‌کنیم.

چگونه یک لیست را به یک پشته تبدیل کنیم

La heapify() تابع نقطه شروع بسیاری از وظایف مرتبط با پشته است. یک تکرار (معمولاً یک لیست) می گیرد و عناصر آن را در جای خود مجدداً مرتب می کند تا ویژگی های یک پشته کوچک را برآورده کند:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

با این کار یک لیست دوباره ترتیب داده شده است که نشان دهنده یک پشته حداقل معتبر است:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

چگونه یک عنصر را به Heap اضافه کنیم

La heappush() تابع به شما این امکان را می دهد که یک عنصر جدید را در پشته وارد کنید و در عین حال ویژگی های پشته را حفظ کنید:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

با اجرای کد، لیستی از عناصری که ویژگی min heap را حفظ می کنند به شما ارائه می دهد:

[3, 5, 7]

نحوه حذف و برگرداندن کوچکترین عنصر از هیپ

La heappop() تابع کوچکترین عنصر را از پشته (ریشه در یک پشته کوچک) استخراج و برمی گرداند. پس از حذف، اطمینان حاصل می کند که لیست یک پشته معتبر باقی می ماند:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

این کوچکترین عنصر و لیست باقیمانده را خروجی می دهد:

1
[3, 7, 5, 9]

در اینجا، 1 کوچکترین عنصر از heap، و لیست باقیمانده ویژگی heap را حتی پس از حذف ما حفظ کرده است 1.

چگونه یک مورد جدید را فشار دهید و کوچکترین مورد را پاپ کنید

La heappushpop() تابع یک عملیات ترکیبی است که یک آیتم جدید را روی پشته هل می دهد و سپس ظاهر می شود و کوچکترین آیتم را از پشته برمی گرداند:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

این خروجی است 3، کوچکترین عنصر، و چاپ جدید heap لیستی که اکنون شامل می شود 4 در حین حفظ خاصیت heap:

3
[4, 5, 7, 9]

چگونه کوچکترین مورد را جایگزین کنیم و یک مورد جدید را فشار دهیم

La heapreplace() تابع کوچکترین عنصر را باز می کند و یک عنصر جدید را روی پشته هل می دهد، همه در یک عملیات کارآمد:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

این چاپ می کند 1، کوچکترین عنصر، و لیست اکنون شامل 4 است و ویژگی heap را حفظ می کند:

1
[4, 5, 7, 9]

یافتن اکستریم های متعدد در هیپ پایتون

nlargest(n, iterable[, key]) و nsmallest(n, iterable[, key]) توابع برای بازیابی چندین عنصر بزرگ یا کوچک از یک تکرار شونده طراحی شده اند. آنها می توانند کارآمدتر از مرتب کردن کل تکرار شونده در زمانی که شما فقط به چند مقدار شدید نیاز دارید. به عنوان مثال، فرض کنید لیست زیر را دارید و می خواهید سه مقدار کوچک و سه مقدار بزرگ را در لیست پیدا کنید:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

در اینجا، nlargest() و nsmallest() توابع می توانند مفید باشند:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

این به شما دو لیست می دهد - یکی شامل سه مقدار بزرگ و دیگری شامل سه کوچکترین مقدار از لیست است data لیست:

[9, 6, 5]
[1, 1, 2]

چگونه هپ سفارشی خود را بسازید

در حالی که پایتون heapq ماژول مجموعه ای قوی از ابزارها را برای کار با heap ها فراهم می کند، سناریوهایی وجود دارد که رفتار پیش فرض min heap ممکن است کافی نباشد. چه به دنبال پیاده‌سازی یک هیپ حداکثر باشید یا به یک هیپ نیاز داشته باشید که بر اساس توابع مقایسه سفارشی عمل کند، ساخت یک پشته سفارشی می‌تواند پاسخگو باشد. بیایید بررسی کنیم که چگونه انبوهی را برای نیازهای خاص تنظیم کنیم.

پیاده سازی Max Heap با استفاده از heapq

به طور پیش فرض، heapq ایجاد کپه های دقیقه. با این حال، با یک ترفند ساده، می توانید از آن برای پیاده سازی یک max heap استفاده کنید. ایده این است که ترتیب عناصر را با ضرب آنها در معکوس کنیم -1 قبل از اضافه کردن آنها به پشته:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

با این رویکرد، بزرگترین عدد (از نظر قدر مطلق) به کوچکترین تبدیل می شود، که اجازه می دهد heapq عملکردی برای حفظ ساختار پشته حداکثر.

Heaps با توابع مقایسه سفارشی

گاهی اوقات، ممکن است به یک پشته نیاز داشته باشید که فقط بر اساس ترتیب طبیعی عناصر مقایسه نشود. به عنوان مثال، اگر با اشیاء پیچیده کار می کنید یا معیارهای مرتب سازی خاصی دارید، یک تابع مقایسه سفارشی ضروری می شود.

برای رسیدن به این هدف، می توانید عناصر را در یک کلاس کمکی قرار دهید که عملگرهای مقایسه را لغو می کند:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

با این تنظیمات، می توانید هر تابع مقایسه کننده سفارشی را تعریف کنید و از آن با heap استفاده کنید.

نتیجه

Heaps عملکرد قابل پیش بینی را برای بسیاری از عملیات ارائه می دهد و آنها را به انتخابی مطمئن برای وظایف مبتنی بر اولویت تبدیل می کند. با این حال، در نظر گرفتن الزامات و ویژگی های خاص برنامه در دست ضروری است. در برخی موارد، بهینه سازی اجرای heap یا حتی انتخاب ساختارهای داده جایگزین ممکن است عملکرد بهتری در دنیای واقعی داشته باشد.

Heaps، همانطور که ما از طریق آن سفر کرده ایم، بیش از یک ساختار داده دیگر هستند. آنها ترکیبی از کارایی، ساختار و سازگاری را نشان می دهند. از ویژگی های اساسی آنها تا پیاده سازی آنها در پایتون heapq ماژول، heaps یک راه حل قوی برای تعداد بی شماری از چالش های محاسباتی، به ویژه آنهایی که حول محور اولویت هستند، ارائه می دهد.

• محتوای مبتنی بر SEO و توزیع روابط عمومی. امروز تقویت شوید.
• PlatoData.Network Vertical Generative Ai. به خودت قدرت بده دسترسی به اینجا.
• PlatoAiStream. هوش وب 3 دانش تقویت شده دسترسی به اینجا.
• PlatoESG. کربن ، CleanTech، انرژی، محیط، خورشیدی، مدیریت پسماند دسترسی به اینجا.
• PlatoHealth. هوش بیوتکنولوژی و آزمایشات بالینی. دسترسی به اینجا.
• منبع: https://stackabuse.com/guide-to-heaps-in-python/