## 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[1]
- 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]

### Adding/Deleting Nodes

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

- MAX-HEAPIFY

- Create a max-heap from an unordered array

- BUILD-MAX-HEAP

- Sort an array in place

- 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 = lif r ≤ n and A[r] > A[largest]largest = rif largest≠iexchange (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 1do 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).

## 0 Comments

Subscribe Us and Thanks for visiting blog.