Heap and Heap Sorts]draft[
Heap Sort is bit different from Other types of SOrts.
Things we need in HeapSort:
- Priority Queue: Implement Set S of Elements, Each of Elements is Associated with Key.
- Insert Operation(): insert Element x into Set S
- Max(S): eturn element of S with largest key.
- Extract-Max(S): Extract max and remove it from S.
- 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?
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
for i=n/2 down to 1:
How to get Better Complexity like: O(N)?
Need to underStand Convergence-Series!
Conclusion in Five-Steps of HeapSorting:
- Build Max Heap from un-ordered array.
- Find/Assume Max element is A
- Swap element A with A[n] now maxElement is at end of the array.
- Discard N Element from the array and decrement the heap by n-1
- 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!!