Heap Sort

Heap Sort

A large area of memory from which the programmer can allocate blocks as needed, and deal locate them (or allow them to be garbage collected) when no longer needed

A balanced, left-justified binary tree in which no node has a value greater than the value in its parent

Class	Sorting algorithm
Data structure	Array
Worst case performance
Best case performance	[1]
Average case performance
Worst case space complexity	total,  auxiliary

Example

Here’s a sample binary tree after it has been heapified

Algorithm

•       MAX‐HEAPIFY(A, i)

•       1. l←LEFT(i)

•       2. r←RIGHT(i)

•       3. ifl ≤ heap‐size[A] and A[l] > A[i]

•       4. then largest←l

•       5. else largest←i

•       6. ifr ≤ heap‐size[A] and a[r] > A[largest]

•       7. then largest←r

•       8. iflargest≠i

•       9. then exchange A[i] A[largest]

•       10. MAX‐HEAPIFY (A, largest)