my net house


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?


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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: