Heap - מיון (Heap sort)

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

סיבוכיות

הכנסת איבר ומחיקת איבר מקסימלי (מינימלי), עולה (O(LogN, אנו עושים 2N פעולות כאלה ולכן הסיבוכיות הכוללת היא:
(O(2N * LogN) = O(N * LogN.

פסאודו-קוד

function Heapsort(theList) {
   create theHeap 
   for each element of theList 
      theHeap.insert(theList.nextElement()); 
   theList.makeEmpty(); 
   while (theHeap is not empty) 
      theList.addElement(theHeap.deleteMin());
}