Heap

Used to implement a max priority queue

Used for HeapSort

Properties

Heap Ordering

• depending on maximum/minimum, or

Complete Binary Tree

• filled up from left to right
• results in a height of

Operations

insert

• add as leaf, bubble up until not required. increaseKey
• bubble up key decreaseKey
• bubble down key (leftwards) delete
• swap last element with element to be deleted
• delete last element
• bubble down element at position of element to be deleted extractMax/Min
• run a delete operation on the root node