Heap - הכנסת איבר

כאמור ב- heap כל אב גדול מכל בניו, כמו-כן אנו יודעים שה- heap מאוזן ככל האפשר, כל הרמות מלבד התחתונה ביותר מלאות, וברמה התחתונה, כל האיברים הקיימים נמצאים במקומות השמאליים ביותר. האיבר החדש יוכנס אם כן לרמה התחתונה ביותר למקום השמאלי ביותר הפנוי. (או השמאלי ביותר ברמה חדשה אם ה- heap מלא.)

לאחר מכן כדי לדאוג לחוקיות ה- heap עלינו לדאוג שהאיבר החדש ימצא במקום, שאביו גדול ממנו, ובניו קטנים ממנו. כדי לעשות זאת נבדוק כל פעם אם האיבר החדש גדול מאביו, ואם כן אז נחליף ביניהם. מובן שאם האיבר גדול מבניו הוא גדול גם מבניו החדשים, ולכן יהיה כך גם אחרי החלפתו עם אביו, וחוזר חלילה.

היעילות תהיה אם כן לפי גובה העץ, שכן במקרה הגרוע ביותר נצטרך לבצע החלפות עד לשורש העץ ולכן היעילות היא (O(LogN.

פסאודו-קוד

function Heap_Insert(heap, val)
//We assume that the heap is implemented as
//  an array where the root is in Arr[1]
{
   pos <-- length(Arr)+1
   Arr[pos] <-- val
   while pos>1 and Arr[pos/2]>Arr[pos]
      swap(Arr[pos], arr[pos/2])
      pos = pos/2
}