Lesson 9 Heap

expression tree

Infix print

• print infix expression that coresponds to Tree

infixPrint(T){
    // stopping
    if (isLeaf(T))
        print(T.data) //operand
    else{
        // recursion
        print("(")
        InfixPrint(T.left)
        print(")")
        print(T.data)//operator
        print("(")
        InfisPrint(T.right)
        print(")")
    }
}

(3)((5)+(7))
Infix print: Left subtree root Right subtree
*Inorder traversal

Postfix Print

PostfixPrint(T){
    //stopping
    if(isLeaf(T))
        print(T.data)  //operand
    else{
        //recursion
        PostfixPrint(T.left)
        PostfixPrint(T.right)
        print(T.data) //operands
    }
}

Postfix print: Left subtree Right subtree root

Post order traversal

Heap: priority queue

node:
data key + data
key mimic: ID of book

• Task: find the largest priority node
  key to mean priority
  data to mean todo

While taking node, often take the largest priory one

• How to realize this function fastly

Binary max-tree

• root key other node’s key
• every sub-tree is bin-maxtree
  
  GetLargest root
  Remove Largest ? replace with larger of sub-root recursively

Complexity analysis

Removal

• least time complexity: #card=math&code=%5Cmathcal%7BO%7D%28h%29)
  
• worst time complexity: #card=math&code=%5Cmathcal%7BO%7D%28n%29)
  
  To avoid larger complexity, we need to optimize the tree’s structure;
  Binary tree with complexity #card=math&code=h%20%3D%20%5Cmathcal%7BO%7D%20%28log%20n%29) has two similar structure:
  Full binary tree and Complete binary tree
  
• Complete binary max-tree

While removing, the property of complete/ max may be lost
Remove Largest:

• 1. last -> root (maintain complete)
     
• 1. sink down (maintain max)
     
• complexity:%20to%20%5Cmathcal%7BO%7D(logn)#card=math&code=%5Cmathcal%7BO%7D%28h%29%20to%20%5Cmathcal%7BO%7D%28logn%29)

Insertion

Insertion:

• 1. insert at last
     
• 1. flat up
     
• complexity:(worst: #card=math&code=%5Cmathcal%7BO%7D%28h%29))
  

complete binary tree and array

complete binary tree array
heap partially ordered array

selsection sort on (unordered array): )%20%3D%20%5Cmathcal%7BO%7D%20(n%5E2)#card=math&code=%5Cmathcal%7BO%7D%28n%20%5Ccdot%20%5Cmathcal%7BO%7D%28n%29%29%20%3D%20%5Cmathcal%7BO%7D%20%28n%5E2%29)

selection sort on heap: %20%5Ccdot%20%5Cmathcal%7BO%7D(log%20%20n))%20%3D%20%5Cmathcal%7BO%7D(nlogn)#card=math&code=%5Cmathcal%7BO%7D%28n%20%5Cmathcal%7BO%7D%281%29%20%5Ccdot%20%5Cmathcal%7BO%7D%28log%20%20n%29%29%20%3D%20%5Cmathcal%7BO%7D%28nlogn%29)

unordered array to a heap: n times insertion: )%20%3D%20%5Cmathcal%7BO%7D(logn)#card=math&code=%5Cmathcal%7BO%7D%28n%20%5Ccdot%20%5Cmathcal%7BO%7D%28h%3Dlogn%29%29%20%3D%20%5Cmathcal%7BO%7D%28logn%29)

summarize

structure	insert	remove largest
heap	#card=math&code=O%28logn%29)	#card=math&code=O%28logn%29)
max-tree	#card=math&code=O%28h%29)	#card=math&code=O%28h%29)
unordered linked-list	#card=math&code=O%281%29)	#card=math&code=O%28n%29)
ordered linked-list	#card=math&code=O%28n%29)	#card=math&code=O%281%29)