Heaps (cont)
Heaps are typically used for implementing Priority Queues
- priorities determined by order on keys
- new items added initially at lower-most, right-most leaf
- then new item "drifts up" to appropriate level in tree
- items are always deleted by removing root (top priority)
Since heaps are dense trees, depth = floor(log2N)+1
Insertion cost = O(logN), Deletion cost = O(logN)
|