ערמה בינארית - מבנה הנתונים שמאחורי תור עדיפויות

ערמה בינארית (Binary Heap) היא עץ בינארי שלם המקיים את 'תכונת הערמה': ב-max-heap, ערך כל צומת ≥ ערכי בניו; ב-min-heap, ערך כל צומת ≤ ערכי בניו. השורש תמיד מכיל את הערך המקסימלי (או המינימלי).

ייצוג חכם - מערך במקום עץ עם מצביעים

מכיוון שהעץ שלם, אפשר לאחסן אותו במערך פשוט בלי מצביעים: לצומת באינדקס i, הבנים נמצאים ב-2i+1 ו-2i+2, וההורה ב-(i-1)/2. זה חוסך זיכרון ומשפר את ניצול המטמון.

// Max-heap stored as array
const heap = [50, 30, 40, 10, 20, 35];
//                  50
//                /    \
//              30      40
//             /  \    /
//           10    20  35

פעולת Insert

• מוסיפים את הערך החדש בסוף המערך (התא הפנוי הבא)
• מבצעים sift-up: כל עוד הערך גדול מההורה, מחליפים איתו
• סיבוכיות: O(log n) - עומק העץ

פעולת Extract-Max

• שומרים את ערך השורש (זה המקסימום)
• מעבירים את האלמנט האחרון לראש
• מבצעים sift-down: מחליפים עם הבן הגדול יותר עד שהתכונה מתקיימת
• סיבוכיות: O(log n)

Heapify - בניית ערמה ממערך קיים

אפשר לבנות ערמה ממערך לא ממוין ב-O(n) (ולא O(n log n)!) על ידי הרצת sift-down מהאלמנט האמצעי לאחור. זה הבסיס של אלגוריתם Heap Sort.