Heapsort

Heap
 Sort in place
 Binary tree
 Worst case runtime (n lg n)

PARENT(i) -> i/2
Left (i)  -> 2i
Right (i) -> 2i + 1

MAX_HEAP

A[PARENT(i)] >= A[i]

MIN_HEAP

A[PARENT(i)] <= A[i]

MAX-HEAPIFY
 Maintain the max-heap propert

 MAX-HEAPIFY (A, i)
   l = LEFT (i)
   r = RIGHT (i)
   if l <= A:heap-size and A[l] > A[i]
        largest = l
   else largest = i
   if r <= A.heap-size and A[r] > A[largest]
        largest = r
   if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY (A, largest)

Heap Sorting

 HEAPSORT (A)
  BUILD-MAX-HEAP (A)
  for i = A.length downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY (A, 1)

Priority queues
 One of the main usage is that we can use max-priority queues to schedule jobs on a shared computer.The max-priority queue keeps track of the jobs to
be performed and their relative priorities. When a job is finished or interrupted,the scheduler selects the highest-priority job from among those pending by calling EXTRACT-MAX. The scheduler can add a new job to the queue at any time by calling INSERT.

Reference: Introduction to Algorithms By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein