# my net house

WAHEGURU….!

## Heap and Heap Sorts]draft[

Heap Sort is bit different from Other types of SOrts.

Things we need in HeapSort:

1. Priority Queue: Implement Set S of Elements, Each of Elements is Associated with Key.
2. Insert Operation(): insert Element x into Set S
3. Max(S): eturn element of S with largest key.
4. Extract-Max(S): Extract max and remove it from S.
5. IncreaseKey() : Increase the value of x’s key to new Value.

Heap a tree: Root of tree First ELement (i=1)

parent of i = i/2

left of i = 2i , right of i = 2i+1

MaxHeap: The key of Node>=Key of Children!

Big Question: how we maintain the Max-Heap() ?

Another Big Question: How we rae gong to Build Max-Heap?

Heap-Operations:

build_max_heap(): Produces Max heap from un-ordered Array()

max_heapify(): Correct the single violation of heap.

Look for the children in the Condition and Check

Convert Array A[….n] into Max-Heap

Code is:

def build_max_heap(A):

for i=n/2 down to 1:

do max_heapify(A,i)

Present-Complexity: O(NlogN)

How to get Better Complexity like: O(N)?

Need to underStand Convergence-Series!

Conclusion in Five-Steps of HeapSorting:

1. Build Max Heap from un-ordered array.
2. Find/Assume Max element is A[1]
3. Swap element A[1] with A[n] now maxElement is at end of the array.
4. Discard N Element from the array and decrement the heap by n-1
5. Now new root may violate the max heap but children are “Max-Heap”

Again MaxHeapify() which means Loop to step2 to 5 until array size is not 1!!

Thenkkewwww