Heaps

A container for objects that have keys. 2 operations - Insert and Extract-min or max; both takes place in log(n) time. n being the no. of keys.

Conceptually - think of a heap as a tree - rooted, binary.

Heap Property - at every node x, key[x] <= all keys of x's children

Consequence - object at root must have minimum key value

Array Implementation

parent[i] = i/2 if i is even  or  floor(i/2) if i is odd.
and children of i = 2i, 2i+1

Use of array is good in terms of storage - no space wasted on pointers. Traversing should be easier.

Insert and Bubble-Up (given key k) Runtime = O(logn)

  1. Stick k at end of last level
  2. Bubble-up k until heap property is restored (i.e. key of k's parent is <= k)
No. of levels in heap tree == log(n) [base 2]  -> n is no. of items in heap

Extract-Min and Bubble-Down Runtime = O(logn)


  • Delete root
  • Move last leaf to be new root
  • Iteratively bubble-down until heap property has been restored [always swap with smaller child]


Applications

  1. Sorting: Canonical use of heap - fast way to do repeated minimum computations.
    Runtime = O(nlogn) time (Each heap operation has a logarithmic runtime; do it n times!)
  • Insert all n array elements into a heap.
  • Extract-min to pluck out elements in sorted order
    2.   Event Manager: Synonym for a heap: Priority Queue.
          Example use: Game simulation
  • objects = event records [action/update to occur at given time in the future]
  • key = time event scheduled to occur
  • Extract-min = yields the next scheduled event 
    3.   Median maintenance
      At each time step i, calculate the median of i numbers in O(logi) time.
  • maintain heaps Hlow: supports EXTRACT_MAX; Hhigh: supports EXTRACT_MIN
   4.    Speeding up Dijikstra from O(nm) to O(mlogn) 

No comments:

Post a Comment