ערימה (מבנה נתונים)
מתוך ויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב, ערימה היא מבנה נתונים בצורת עץ מכוון המקיים תכונה בסיסית, הנקראת תכונת הערימה. תכונה זו מבטיחה יעילות של הערימה כאשר רוצים לאחזר את הערך הגדול ביותר או הקטן ביותר שמאוחסן בערימה, והעובדה שאין דרישות נוספות על המבנה הפנימי של הערימה מבטיחה שניתן יהיה לבצע ביעילות פעולות של הוספת ומחיקת איברים לערימה.
מבחינה פורמלית, ערימה היא עץ מכוון שבו לכל צומת יש מפתח. המפתחות הם איברים בקבוצה סדורה לינארית, כלומר ניתן להשוות בין כל שניים מהם. העץ מקיים תכונה אחת נוספת, שמכונה "תכונת הערימה":
- המפתח של כל צומת בערימה קטן ממפתח אביו.
לערימה המקיימת תכונה זו קוראים "ערימת מקסימום", כי היא מבטיחה שהאיבר הגדול ביותר בערימה יהיה שורש העץ. ניתן להפוך את הדרישה, ולדרוש שהמפתח של כל צומת בערימה יהיה גדול ממפתח אביו. במקרה כזה תתקבל ערימה המכונה "ערימת מינימום".
דרישה זו היא הדרישה היחידה מערימות באופן כללי. ישנם סוגים ספציפיים של ערימות שבהם נוספות דרישות, המשפרות את תפקוד הערימה.
תוכן עניינים |
[עריכה] סוגי ערימות
[עריכה] ערימה בינארית
ערימה בינארית היא ערימה שממומשת באמצעות עץ בינארי, כלומר לכל צומת לכל היותר שני בנים. בנוסף לתכונת הערימה, היא מקיימת תכונה נוספת הנוגעת לצורתה:
- הערימה היא עץ כמעט שלם, כלומר היא מלאה לחלוטין בכל רמותיה פרט אולי לאחרונה המלאה מצד שמאל עד לנקודה מסוימת.
בזכות תכונה זו, דרך נוחה לייצג ערימה בינארית היא בתוך מערך, ובצורה קומפקטית בה אין צורך לשמור מצביעים מכל תא במערך לתאים המייצגים את בניו. גישה זו מאפשרת את מימוש מיון ערימה, שממיין איברים תוך שימוש במקום קבוע (במקום להקצות כמות זכרון נוספת התלויה בגודל הקלט) - כל המיון יתבצע בתוך המערך שבו נתונים האיברים.
[עריכה] ערימה בינומית
ערימה בינומית מיוצגת בתור אוסף של עצים בינומיים. ההגדרה המיוחדת של עצים בינומיים מבטיחה שהערימה תקיים, פרט לתכונת הערימה, תכונה נוספת:
- לכל דרגה נתונה, קיים בערימה הבינומית לכל היותר עץ אחד שזוהי דרגת שורשו (כלומר, כל העצים בערימה הם מאורך שונה).
בשל תכונות אלו ערימה בינומית מסוגלת לאפשר מיזוג עם ערימה נוספת מסוגה בזמן מהיר.
[עריכה] ערימת פיבונאצ'י
ערימות פיבונאצ'י ממומשות גם הן בתור אוסף של עצים, בדומה לערימות בינומיות, אך העצים אינם חייבים להיות עצים בינומיים. בשל כך ערימת פיבונאצ'י היא גמישה יותר, ומהירה יותר כאשר מתייחסים לסיבוכיות משוערכת של זמן הריצה של הפעולות שבה (כלומר, לא בודקים את הזמן שלוקחת פעולה בודדת, אלא את הזמן שלוקחת סדרה של פעולות).
ערימת פיבונאצ'י משמשת לשיפור זמן הריצה של אלגוריתמים דוגמת אלגוריתם דייקסטרה והאלגוריתם של פרים.
[עריכה] ראו גם
- מיון ערימה

