מדריך לערמות ב-Python

מבוא

דמיינו לעצמכם שדה תעופה הומה עם טיסות הממריאות ונוחתות בכל דקה. בדיוק כפי שבקרי תעבורה אוויריים נותנים עדיפות לטיסות על סמך דחיפות, ערימות עוזרות לנו לנהל ולעבד נתונים על סמך קריטריונים ספציפיים, ומבטיחות שהנתונים ה"דחופים" או ה"חשובים" ביותר יהיו תמיד נגישים בראש.

במדריך זה, נצא למסע להבנת ערימות מהיסוד. נתחיל בהסרת המסתורין של ערימות והתכונות הטבועות שלהן. משם, נצלול ליישום הערימות של Python עצמו, ה- heapq מודול, ולחקור את מערך הפונקציות העשיר שלו. לכן, אם אי פעם תהיתם כיצד לנהל ביעילות מערך נתונים דינמי שבו יש צורך לעתים קרובות באלמנט העדיפות הגבוהה ביותר (או הנמוכה ביותר), אתם צפויים להתענוג.

מה זה ערימה?

הדבר הראשון שתרצה להבין לפני שאתה צולל לתוך השימוש בערימות הוא מה זה ערמה. ערימה בולטת בעולם של מבני נתונים כמעצמה מבוססת עצים, מיומנת במיוחד שמירה על סדר והיררכיה. למרות שהוא עשוי להידמות לעץ בינארי לעין לא מאומנת, הניואנסים במבנה שלו ובכללי השלטון מייחדים אותו באופן מובהק.

אחד המאפיינים המגדירים של ערימה הוא טבעה בתור א עץ בינארי שלם. זה אומר שכל רמה של העץ, אולי למעט האחרונה, מלאה לגמרי. בתוך הרמה האחרונה הזו, צמתים מתאכלסים משמאל לימין. מבנה כזה מבטיח שניתן לייצוג ולתפעל ערימות ביעילות באמצעות מערכים או רשימות, כאשר מיקומו של כל אלמנט במערך משקף את מיקומו בעץ.

המהות האמיתית של ערימה, לעומת זאת, טמונה בה הזמנת. ב ערימה מקסימלית, הערך של כל צומת נתון עולה או שווה את הערכים של הילדים שלו, וממקם את האלמנט הגדול ביותר ממש בשורש. מצד שני, א ערימה דקה פועל על עיקרון הפוך: ערך של כל צומת קטן או שווה לערכי הילדים שלו, מה שמבטיח שהאלמנט הקטן ביותר יושב בשורש.

ככל שנתקדם, נצלול עמוק יותר לאופן שבו המאפיינים המובנים של ערימות מאפשרים פעולות יעילות וכיצד של Python heapq מודול משלב בצורה חלקה ערימות במאמצי הקידוד שלנו.

מאפיינים ומאפיינים של ערימות

ערימות, עם המבנה הייחודי שלהן ועקרונות הסדר שלהן, מביאות קבוצה של מאפיינים ומאפיינים מובהקים שהופכים אותם לבעלי ערך רב בתרחישים חישוביים שונים.

בראש ובראשונה, ערימות הן יעיל מטבעו. המבנה מבוסס העצים שלהם, במיוחד פורמט העץ הבינארי המלא, מבטיח שניתן לבצע פעולות כמו הכנסה וחילוץ של רכיבי עדיפות (מקסימום או מינימום) בזמן לוגריתמי, בדרך כלל O (יומן n). יעילות זו היא ברכה עבור אלגוריתמים ויישומים הדורשים גישה תכופה לרכיבי עדיפות.

תכונה בולטת נוספת של ערימות היא שלהם יעילות זיכרון. מכיוון שניתן לייצג ערימות באמצעות מערכים או רשימות ללא צורך בהצבעות מפורשות לצמתי צאצא או הורה, הם חוסכים מקום. מיקומו של כל אלמנט במערך מתאים למיקומו בעץ, מה שמאפשר מעבר ומניפולציה צפויים וישירים.

תכונת הסדר של ערימות, בין אם כערימה מקסימלית או כערמה מינימלית, מבטיחה זאת השורש תמיד מחזיק באלמנט העדיפות הגבוהה ביותר. הסדר העקבי הזה הוא מה שמאפשר גישה מהירה לאלמנט בראש סדר העדיפויות מבלי צורך לחפש בכל המבנה.

יתר על כן, ערימות הן רב צדדי. בעוד ערימות בינאריות (כאשר לכל הורה יש לכל היותר שני ילדים) הם הנפוצים ביותר, ניתן להכליל ערימות כך שיש להם יותר משני ילדים, המכונה ערימות ד-ארי. גמישות זו מאפשרת כוונון עדין בהתבסס על מקרי שימוש ספציפיים ודרישות ביצועים.

לבסוף, ערימות הן התאמה עצמית. בכל פעם שמתווספים או מסירים אלמנטים, המבנה מסדר את עצמו מחדש כדי לשמור על תכונותיו. איזון דינמי זה מבטיח שהערימה תישאר אופטימלית לפעולות הליבה שלה בכל עת.

ככל שנעמיק ביישום והיישומים המעשיים של Python, הפוטנציאל האמיתי של ערימות יתגלה לפנינו.

סוגי ערמות

לא כל הערימות נוצרות שוות. בהתאם לסדר ולמאפיינים המבניים, ניתן לסווג ערימות לסוגים שונים, כל אחד עם סט יישומים ויתרונות משלו. שתי הקטגוריות העיקריות הן ערימה מקסימלית ו ערימה דקה.

המאפיין הבולט ביותר של א ערימה מקסימלית הוא שהערך של כל צומת נתון גדול או שווה לערכים של ילדיו. זה מבטיח שהאלמנט הגדול ביותר בערימה נמצא תמיד בשורש. מבנה כזה שימושי במיוחד כאשר יש צורך לגשת לעתים קרובות לרכיב המקסימלי, כמו ביישומים מסוימים של תור עדיפות.

המקביל לערימה המקסימלית, א ערימה דקה מבטיח שהערך של כל צומת נתון קטן או שווה לערכים של ילדיו. זה מציב את האלמנט הקטן ביותר של הערימה בשורש. ערימות מינימליות לא יסולא בפז בתרחישים שבהם האלמנט הקטן ביותר הוא בעל חשיבות עליונה, כגון באלגוריתמים העוסקים בעיבוד נתונים בזמן אמת.

מעבר לקטגוריות הראשוניות הללו, ניתן להבחין בערימות גם על סמך גורם ההסתעפות שלהן:

בעוד ערימות בינאריות הן הנפוצות ביותר, כאשר לכל הורה יש לכל היותר שני ילדים, ניתן להרחיב את מושג הערימות לצמתים שיש להם יותר משני ילדים. ב ערימת ד-ארי, לכל צומת יש לכל היותר d יְלָדִים. ניתן לבצע אופטימיזציה של וריאציה זו עבור תרחישים ספציפיים, כמו הקטנת גובה העץ כדי להאיץ פעולות מסוימות.

ערימה בינומיאלית הוא קבוצה של עצים בינומיים המוגדרים רקורסיבית. ערימות בינומיות משמשות ביישומי תור עדיפות ומציעות פעולות מיזוג יעילות.

נקרא על שם רצף פיבונאצ'י המפורסם, ה ערימת פיבונאצ'י מציע זמני ריצה מופחתים יותר עבור פעולות רבות בהשוואה לערימות בינאריות או בינומיות. הם שימושיים במיוחד באלגוריתמים לאופטימיזציה של רשת.

יישום הערמה של Python – ה heapq מודול

Python מציעה מודול מובנה לפעולות ערימה - ה heapq מודול. מודול זה מספק אוסף של פונקציות הקשורות לעימה המאפשרות למפתחים להפוך רשימות לערמות ולבצע פעולות ערימה שונות ללא צורך ביישום מותאם אישית. בואו נצלול לניואנסים של מודול זה וכיצד הוא מביא לכם את כוחן של ערימות.

השמיים heapq המודול אינו מספק סוג נתוני ערימה מובהק. במקום זאת, הוא מציע פונקציות שעובדות על רשימות Python רגילות, משנות ומתייחסות אליהן כאל ערימות בינאריות.

גישה זו גם חסכונית בזיכרון וגם משתלבת בצורה חלקה עם מבני הנתונים הקיימים של Python.

זה אומר ש ערימות מיוצגות כרשימות in heapq. היופי בייצוג זה הוא הפשטות שלו - מערכת אינדקס הרשימה מבוססת האפס משמשת כעץ בינארי מרומז. עבור כל אלמנט נתון במיקום i, זה:

• הילד השמאלי נמצא בעמדה 2*i + 1
• הילד הנכון נמצא בעמדה 2*i + 2
• צומת האב נמצא בעמדה (i-1)//2

מבנה מרומז זה מבטיח שאין צורך בייצוג עץ בינארי נפרד מבוסס-צומת, מה שהופך את הפעולות לפשוטות ושימוש בזיכרון מינימלי.

חשוב לציין כי heapq מודול יוצר ערימות דקות כברירת מחדל. המשמעות היא שהאלמנט הקטן ביותר נמצא תמיד בשורש (או המיקום הראשון ברשימה). אם אתה צריך ערימה מקסימלית, תצטרך להפוך את הסדר על ידי הכפלת אלמנטים ב -1 או השתמש בפונקציית השוואה מותאמת אישית.

פיתון heapq מודול מספק חבילת פונקציות המאפשרות למפתחים לבצע פעולות ערימה שונות ברשימות.

בסעיפים הבאים, נצלול עמוק לתוך כל אחת מהפעולות הבסיסיות הללו, נחקור את המכניקה שלהן ומקרי שימוש.

כיצד להפוך רשימה לערימה

השמיים 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]

כיצד להוסיף אלמנט לערימה

השמיים heappush() הפונקציה מאפשרת לך להכניס אלמנט חדש לערימה תוך שמירה על תכונות הערימה:

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

הפעלת הקוד תיתן לך רשימה של אלמנטים השומרים על המאפיין min heap:

[3, 5, 7]

כיצד להסיר ולהחזיר את האלמנט הקטן ביותר מהערימה

השמיים heappop() הפונקציה מחלצת ומחזירה את האלמנט הקטן ביותר מהערימה (השורש בערימה מינימלית). לאחר ההסרה, זה מבטיח שהרשימה תישאר ערימה חוקית:

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

זה יוציא את האלמנט הקטן ביותר ואת הרשימה שנותרה:

1
[3, 7, 5, 9]

כאן, 1 הוא האלמנט הקטן ביותר מ- heap, והרשימה שנותרה שמרה על נכס הערימה, גם לאחר שהסרנו 1.

כיצד לדחוף פריט חדש ולפוצץ את הפריט הקטן ביותר

השמיים heappushpop() פונקציה היא פעולה משולבת שדוחפת פריט חדש לערימה ואז קופצת ומחזירה את הפריט הקטן ביותר מהערימה:

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

זה יפלט 3, האלמנט הקטן ביותר, והדפיסו את החדש heap רשימה הכוללת כעת 4 תוך שמירה על נכס הערימה:

3
[4, 5, 7, 9]

כיצד להחליף את הפריט הקטן ביותר ולדחוף פריט חדש

השמיים heapreplace() הפונקציה מקפיצה את האלמנט הקטן ביותר ודוחפת אלמנט חדש אל הערימה, הכל בפעולה אחת יעילה:

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

זה מודפס 1, האלמנט הקטן ביותר, והרשימה כוללת כעת 4 ושומרת על מאפיין הערימה:

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 מודול מספק קבוצה חזקה של כלים לעבודה עם ערימות, ישנם תרחישים שבהם התנהגות ברירת המחדל של ערימה מינימלית לא תספיק. בין אם אתם מחפשים ליישם ערימה מקסימלית או זקוקים לערמה שפועלת על סמך פונקציות השוואה מותאמות אישית, בניית ערימה מותאמת אישית יכולה להיות התשובה. בואו נבדוק כיצד להתאים ערימות לצרכים ספציפיים.

יישום Max Heap באמצעות heapq

כברירת מחדל, heapq יוצר ערימות דקות. עם זאת, עם טריק פשוט, אתה יכול להשתמש בו כדי ליישם ערימה מקסימלית. הרעיון הוא להפוך את סדר האלמנטים על ידי הכפלתם ב -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 מתפקד כדי לשמור על מבנה ערימה מקסימלי.

ערימות עם פונקציות השוואה מותאמות אישית

לפעמים, ייתכן שתזדקק לערמה שאינה משווה רק על סמך הסדר הטבעי של האלמנטים. לדוגמה, אם אתה עובד עם אובייקטים מורכבים או שיש לך קריטריוני מיון ספציפיים, פונקציית השוואה מותאמת אישית הופכת חיונית.

כדי להשיג זאת, אתה יכול לעטוף אלמנטים בכיתה עוזרת שתוקפת את אופרטורי ההשוואה:

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

עם הגדרה זו, אתה יכול להגדיר כל פונקציית השוואה מותאמת אישית ולהשתמש בה עם הערימה.

סיכום

ערימות מציעות ביצועים צפויים עבור פעולות רבות, מה שהופך אותן לבחירה אמינה למשימות מבוססות עדיפות. עם זאת, חיוני לשקול את הדרישות והמאפיינים הספציפיים של היישום הנדון. במקרים מסוימים, התאמה של יישום הערימה או אפילו בחירה במבני נתונים חלופיים עשויים להניב ביצועים טובים יותר בעולם האמיתי.

ערימות, כפי שעברנו דרכן, הן יותר מסתם עוד מבנה נתונים. הם מייצגים מפגש של יעילות, מבנה ויכולת הסתגלות. מהמאפיינים הבסיסיים שלהם ועד ליישום שלהם ב-Python's heapq מודול, heaps מציעים פתרון חזק למספר עצום של אתגרים חישוביים, במיוחד אלה המתמקדים בעדיפות.

• הפצת תוכן ויחסי ציבור מופעל על ידי SEO. קבל הגברה היום.
• PlatoData.Network Vertical Generative Ai. העצים את עצמך. גישה כאן.
• PlatoAiStream. Web3 Intelligence. הידע מוגבר. גישה כאן.
• PlatoESG. פחמן, קלינטק, אנרגיה, סביבה, שמש, ניהול פסולת. גישה כאן.
• PlatoHealth. מודיעין ביוטכנולוגיה וניסויים קליניים. גישה כאן.
• מקור: https://stackabuse.com/guide-to-heaps-in-python/