**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