Stack vs Heap
מחסנית היא רשימה מסודרת שבה הוספה ומחיקה של פריטי רשימה יכולה להתבצע רק בקצה אחד הנקרא העליון. מסיבה זו, מחסנית נחשבת למבנה נתונים אחרון בחוץ (LIFO). ערמה היא מבנה נתונים מיוחד המבוסס על עצים והוא עונה על תכונה מיוחדת הנקראת תכונת הערמה. כמו כן, ערמה היא עץ שלם, כלומר אין רווחים בין עלי העץ כלומר בעץ שלם כל רמה מתמלאת לפני הוספת רמה חדשה לעץ והצמתים ברמה נתונה מתמלאים מ משמאל לימין.
מה זה Stack?
כפי שהוזכר קודם לכן, מחסנית היא מבנה נתונים שבו מוסיפים ומוסרים אלמנטים רק מקצה אחד הנקרא העליון.ערימות מאפשרות רק שתי פעולות בסיסיות הנקראות דחיפה ופופ. פעולת הדחיפה מוסיפה אלמנט חדש לראש הערימה. פעולת הפופ מסירה אלמנט מהחלק העליון של הערימה. אם המחסנית כבר מלאה, כאשר מבוצעת פעולת דחיפה, היא נחשבת כהצפת מחסנית. אם פעולת פופ מבוצעת על מחסנית שכבר ריקה, היא נחשבת כזרימת מחסנית. בשל המספר הקטן של פעולות שניתן לבצע על מחסנית, זה נחשב למבנה נתונים מוגבל. בנוסף, לפי האופן שבו מוגדרות פעולות הדחיפה והפופ, ברור שאלמנטים שנוספו אחרונים לערימה יוצאים ראשונים מהערימה. לכן מחסנית נחשבת כמבנה נתונים של LIFO.
מה זה Heap?
כפי שהוזכר קודם לכן, ערמה היא עץ שלם שמספק את תכונת הערמה.מאפיין ערימה קובע שאם y הוא צומת צאצא של x אז הערך המאוחסן בצומת x צריך להיות גדול או שווה לערך המאוחסן בצומת y (כלומר, ערך (x) ≥ ערך (y)). מאפיין זה מרמז שהצומת עם הערך הגדול ביותר ימוקם תמיד בשורש. ערימה שנבנית באמצעות מאפיין זה נקראת max-heap. קיימת וריאציה נוספת של תכונת הערימה המציינת את ההפך מכך. (כלומר ערך (x) ≤ ערך (y)). זה מרמז שהצומת עם הערך הקטן ביותר ימוקם תמיד בשורש, ובכך נקרא ערימה קטנה. קיים מגוון רחב של פעולות המבוצעות בערימות כגון מציאת מינימום (בערמות מינימליות) או מקסימום (בערמות מקסימליות), מחיקת מינימום (בערימות מינימליות) או מקסימום (בערימות מקסימליות), הגדלת (במקסימום ערימות) -heaps) או מקש מצטמצם (בערמות קטנות) וכו'
מה ההבדל בין Stack ל-Heap?
ההבדל העיקרי בין ערימות לערמות הוא שבעוד מחסנית היא מבנה נתונים ליניארי, ערימה היא מבנה נתונים לא ליניארי.מחסנית היא רשימה מסודרת העוקבת אחר המאפיין LIFO, בעוד שהערמה היא עץ שלם שעוקב אחר מאפיין הערימה. יתר על כן, מחסנית היא מבנה נתונים מוגבל התומך רק במספר מוגבל של פעולות כמו push ו-pop, בעוד שה-heap תומך במגוון רחב של פעולות כמו איתור ומחיקה של המינימום או המקסימום, הגדלה או הקטנה של המפתח ומיזוג.
