# Heap Sort

## Heap Sort

A heap is a nearly complete binary tree with the following two properties:
• Structural property: all levels are full, except possibly the last one, which is filled from left to right
• Order (heap) property: for any node x, Parent(x) ≥ x

### Array Representation of Heaps

• A heap can be stored as an array A.
• Root of tree is A
• Left child of A[i] = A[2i]
• Right child of A[i] = A[2i + 1]
• Parent of A[i] = A[ i/2 ]
• Heapsize[A] ≤ length[A]
The elements in the subarray A[(n/2+1) .. n] are leaves
Max-heaps (largest element at root), have the max-heap property:
• for all nodes i, excluding the root:
A[PARENT(i)] ≥ A[i]
Min-heaps (smallest element at root), have the min-heap property:
• for all nodes i, excluding the root:
A[PARENT(i)] ≤ A[i]

New nodes are always inserted at the bottom level (left to right) and nodes are removed from the bottom level (right to left).

### Operations on Heaps

• Maintain/Restore the max-heap property
1. MAX-HEAPIFY
• Create a max-heap from an unordered array
1. BUILD-MAX-HEAP
• Sort an array in place
1. HEAPSORT
• Priority queues

### Heapify Property

Suppose a node is smaller than a child and Left and Right subtrees of i are max-heaps. To eliminate the violation:
• Exchange with larger child
• Move down the tree
• Continue until node is not smaller than children
```
Max-Heapify(A, i, n)
{

l = Left(i)

r = Right(i)

largest=i;

if l ≤ n and A[l] > A[largest]

largest = l

if r ≤ n and A[r] > A[largest]

largest = r

if largest≠i

exchange (A[i] , A[largest])

Max-Heapify(A, largest, n)

}
```

### Analysis:

In the worst case Max-Heapify is called recursively h times, where h is height of the heap and since each call to the heapify takes constant time
Time complexity = O(h) = O(logn)

### Building a Heap

Convert an array A[1 … n] into a max-heap (n = length[A]). The elements in the sub-array A[(n/2+1) .. n] are leaves. Apply MAX-HEAPIFY on elements between 1 and n/2⌋.

### Algorithm:

```
Build-Max-Heap(A)

n = length[A]

for i ← ⌊n/2⌋ down to 1

do MAX-HEAPIFY(A, i, n)
```

### Time Complexity:

Running time:  Loop executes O(n) times and complexity of Heapify is O(lgn), therefore complexity of Build-Max-Heap is O(nlogn).
This is not an asymptotically tight upper bound