ערימה – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
הוספת תבנית מבני נתונים
הרחבה
שורה 1:
{{פירוש נוסף|נוכחי=מבנה נתונים|אחר=אזור הזיכרון הדינמי|ראו=[[הקצאת זיכרון דינמית]]}}
ב[[מדעי המחשב]], '''ערימה''' היא [[מבנה נתונים]] בצורת [[עץ מכוון]] המקיים תכונה בסיסית, הנקראת '''תכונת הערימה'''. תכונה זו מבטיחה יעילות של הערימה כאשר רוצים לאחזר את הערך הגדול ביותר או הקטן ביותר שמאוחסן בערימה, והעובדה שאין דרישות נוספות על המבנה הפנימי של הערימה מבטיחה שניתן יהיה לבצע ביעילות פעולות של הוספת ומחיקת איברים לערימה.
ב[[מדעי המחשב]], '''ערימה''' היא [[מבנה נתונים]] בצורת [[עץ מכוון]] המקיים תכונה בסיסית, הנקראת '''תכונת הערימה''': המפתח של כל צומת בעץ קטן ממפתח אביו. בתוצאה מדרישה זו, הצומת בעל המפתח הגדול ביותר בכל הוא תמיד השורש של העץ, וניתן למצוא אותו ב[[סיבוכיות זמן]] {{כ}}<math>(O(1</math>, כלומר במספר פעולות קבוע, שאיננו תלוי במספר האיברים בערימה.
 
לערימה המקיימת תכונה זו קוראים "ערימת מקסימום", כי היא מבטיחה שהאיבר הגדול ביותר בערימה יהיה שורש העץ. ניתן להפוך את הדרישה, ולדרוש שהמפתח של כל צומת בערימה יהיה גדול ממפתח אביו. במקרה כזה תתקבל ערימה המכונה "ערימת מינימום".
מבחינה פורמלית, ערימה היא עץ מכוון שבו לכל צומת יש מפתח. המפתחות הם איברים ב[[סדר מלא|קבוצה סדורה לינארית]], כלומר ניתן להשוות בין כל שניים מהם. העץ מקיים תכונה אחת נוספת, שמכונה "תכונת הערימה":
* המפתח של כל צומת בערימה קטן ממפתח אביו.
 
לערימה המקיימת תכונה זו קוראים "ערימת מקסימום", כי היא מבטיחה שהאיבר הגדול ביותר בערימה יהיה שורש העץ. ניתן להפוך את הדרישה, ולדרוש שהמפתח של כל צומת בערימה יהיה גדול ממפתח אביו. במקרה כזה תתקבל ערימה המכונה "ערימת מינימום".
 
דרישה זו היא הדרישה היחידה מערימות באופן כללי. ישנם סוגים ספציפיים של ערימות שבהם נוספות דרישות, המשפרות את תפקוד הערימה.
 
הערימות השונות הן המימושים היעילים ביותר של [[מבנה נתונים מופשט|מבנה הנתונים המופשט]] [[תור עדיפויות]].
 
==סוגי ערימות==