[prev] 3 [next]

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)