Binary Heaps

Min-heaps

• The root node is always the min value

• The tree must be a complete tree.

• the only relationship between the subtrees is that they are both greater than their parent node. There is no other relationship between them.

Operations

• push
• pop : worst case $\Theta(\ln n)$
• top $\Theta(1)$

push opearation

• Start by putting the new element at the leaf, and then find its correct place
• Start from the root, and then move the higher value down the tree.

How to gaurantee that the tree is complete? Percolation

S commplete tree is filled with bridth-first traversal

Implementing min-heap using an array

• parent of node $k$ is $k/2$
• children of node $k$ are indexed by $2k$ and $2k+1$

Comparison

• For bunary heap, inserting/accessing/deleting an element at different locations:

Other heaps

• Leftist heap
• Skew heap
• Binomial heap
• Fibonacci heap