ערימה בינארית
ערימה בינארית | |||
---|---|---|---|
![]() דוגמה לערימת מינימום בינארית | |||
סיבוכיות מקום וזמן | |||
| |||
זיכרון: |
| ||
חיפוש: |
| ||
הכנסה: |
| ||
הוצאה: |
| ||
שליפה: |
| ||
הצצה: |
|
במדעי המחשב, ערימה בינארית היא סוג של מבנה הנתונים ערימה. יתרונה הגדול הוא בנוחות השימוש בה והמקום המועט הדרוש כדי לתחזק אותה.
הערימה משמשת בין השאר למיון המכונה מיון ערימה, ולמימוש מבנה הנתונים המופשט תור עדיפויות.
מבנה
[עריכת קוד מקור | עריכה]הערימה מהווה עץ בינארי כמעט מושלם, כלומר שכל השורות, פרט אולי לאחרונה, מלאות, והאחרונה מלאה משמאל עד לנקודה מסוימת. בנוסף, היא מקיימת את "כלל הערימה": כל ערך של צומת אינו גדול משני בניו (ערימה זאת מכונה "ערימת מינימום"; אפשרי גם שכל צומת אינו קטן משני בניו, ואז היא נקראת "ערימת מקסימום").
עם זאת, בפועל אין צורך לממש עץ בינארי: די להחזיק את האיברים במערך, כשהאיברים מסודרים בו משמאל לימין, שורה אחרי שורה, כאשר ידוע שאביו של איבר הנמצא במקום ה-i הוא ובניו נמצאים במקומות ה-.
פעולות
[עריכת קוד מקור | עריכה]עבור ערימת מינימום-
- הכנסה: כדי להכניס איבר חדש, מגדילים את גודל הערימה ב-1, מכניסים את האיבר החדש בסוף הערימה, ולאחר מכן, כל עוד הוא קטן מאביו, מחליפים אותו עם אביו. סיבוכיות ריצה: (הסבר על סימון זה). עם זאת, על פי ניתוח לשיעורין הסיבוכיות של בניית ערימה בת איברים היא בלבד.
- הוצאה: כדי להוציא איבר, מחליפים את האיבר המועד להוצאה באיבר האחרון במערך, מורידים את האיבר הנ"ל מסוף המערך, ומקטינים את גודל הערימה ב-1. לאחר מכן משווים בין האיבר שהוצאנו לבין איבר שהחלפנו ואם האיבר שהחלפנו קטן מהאיבר שהוצאנו אז כל עוד האיבר שהוחלף קטן מאביו, מחלפים אותו באביו, ואם האיבר שהוחלף גדול מאיבר שהוצא אז כל עוד האיבר שהוחלף גדול מבניו, מחליפים אותו בקטן שביניהם. סיבוכיות זמן ריצה:
- מציאת המינימום (הצצה): מחזירים את האיבר הראשון. סיבוכיות זמן ריצה: .
- מחיקת המינימום (שליפה): מוחקים את האיבר המינימלי, מעבירים את האיבר האחרון להתחלה, ולאחר מכן, כל עוד הוא לא קטן משני בניו, מחליפים אותו עם הקטן מביניהם. זמן ריצה: .
- הקטנת ערך: מקטינים ערך, ולאחר מכן, כל עוד הוא קטן מאביו, מחליפים אותו עם אביו. סיבוכיות זמן ריצה: .
בניגוד לערימה בינומית, ערימה בינארית לא תומכת במיזוג ערימות.
ערימה d-ארית
[עריכת קוד מקור | עריכה]במקום לממש את הערימה כעץ בינארי, אפשר לממש אותה כעץ מכל דרגה אחרת. בערימה d-ארית לכל קודקוד d ילדים, ושאר המימוש בדומה. אביו של איבר הנמצא במקום ה-i הוא ובניו j נמצאים במקומות ה- . הכנסה והקטנת ערך יורדות ל-, ואילו מחיקת המינימום עולה ל- (משום שיש למצוא את הבן המינימלי).
שימושים
[עריכת קוד מקור | עריכה]הערימה הבינארית משמשת למיון ערימה. במיון זה, בונים ערימה מהאיברים ולאחר מכן מוחקים אותם אחד אחד. יתרונו הוא שהוא לא דורש זיכרון נוסף, וזמן הריצה שלו הוא הטוב ביותר האפשרי: במקרה הגרוע.
קישורים חיצוניים
[עריכת קוד מקור | עריכה]- ערימה בינארית, באתר MathWorld (באנגלית)
הערות שוליים
[עריכת קוד מקור | עריכה]- ^ Thomas Porter; Istvan Simon (1974). "Random Insertion into a Priority Queue Structure" (PDF). Stanford University Reports. Stanford University. p. 13. נבדק ב-31 בינואר 2014.
{{cite web}}
: (עזרה)
מבני נתונים | ||
---|---|---|
מבנים מופשטים | רשימה • מחסנית • קבוצה • מולטי קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרות | |
מימושים ליניאריים | מערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץ | |
גרפים ועצים | ערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • Trie • X-fast trie • טריי y מהיר• עץ WAVL | |
הסתברותיים | מסנן בלום |