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