Little Sugar (Heaps)

• Heap is a data structure whcih satisfies the MAX-HEAP or MIN-HEAP property
• All basic operations on a heap run in a time proportional to the height of the heap (lg n ) where n being the total number of nodes in a heap
• A heap is generally a complete tree
• IN an array represenation of an N-element heap the leaves nodes are indexed by n/2+1 , n/2 + 2 ... n
• In an N element heap , the number of nodes of height H are n/pow(2,h+1)