Heap - מציאת ומחיקת איבר מקסימלי (או מינימלי)

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

מציאת איבר מקסימלי (מינימלי), תהיה פשוט החזרת השורש (ולכן סבוכיות של (O(1).

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

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

פסאודו-קוד

function Heap_DeleteMin(heap)
{
   node = heap.root
   val = node.data
   while (node.data is smaller than one of its children)
   {
      child = node's child with smaller value of data
      swap(node.data, child.data)
      node = child
   }
   return val
}