1. Heap - it can be used as a priority queue!

• A binary tree SORTING keys at its nodes
• Heap-Order : key(v) ≥ or ≤ key(parent(v))
• Complete Binary Tree height(h), 2^i nodes of depth i (i = 0 ~ h-1)

n ≥ 2^h

→ h ≤ log(n)

• at depth h-1, the internal nodes are to the left of the externals
• The last node : the rightmost node of max depth

**it's different from a binary search tree. We use bst to find an item or see if it has an item quickly, and we use a heap to get the item w the smallest key quickly

2. Operation

Upheap

1 goes up from the bottom to the top

• Compare the node with its parent
• Swap if it doesn't satisfy the heap order
• O(log(n)) ( ** height = O(log(n)) )

Downheap

7 goes down by swapping

• Compare the node with the smaller child
• Swap if it doesn't satisfy the heap order
• O(log(n)) ( ** height = O(log(n)) )

Removal of min or max

• Replace the root with the last node
• Remove the last node which has the value of the root
• Downheap the new top

Updating the last node for inserting

• Go up until a left child is reached or the root is reached → the root will be reached if the tree is full (= 2^h nodes at the bottom)
• Go to the right child(sibling of the node that is reached) from the node that is reached
• Go down left until a leaf is reached