Heap Sorting

A Θ(n log n) sorting algorithm

  • Create data structure (heap) to manage
    information during the execution of an
    algorithm.

  • The heap has other applications beside
    sorting: Priority Queues

  • The heap data structure and its variants
    are very useful for many algorithms


In practice, heaps are usually implemented as arrays


To represent a complete binary tree as an array:
– The root node is A[1]
– Node i is A[i]
– The parent of node i is A[i/2] (note: integer divide)
– The left child of node i is A[2i]
– The right child of node i is A[2i + 1]


Binary Heaps are just complete trees

Min Heaps: Value of each node is greater than or equal to the value of its parent with a smallest value at the root

Max Heaps: Value of each node is less then or equal to the value of its parent with the max value at the root.


Binary heap needs 3 functions:

  1. Find

  2. Insertion - add new value to the array. Repair the heap by comparing the added element with its parent and swapping.

  3. Deletion - always removes the head value. Repair the heap by comparing the element with both children and swapping


“Heapify” checks if its a heap and swaps values if it is not a correct heap.

“BluidHeap”