Saturday, August 24, 2013

Application of heap (in computer science)

Following are applications of heap:
  • Heap Sort - fast way to get minimum computation
    SelectionSort() with time complexity - Θ(n2) when uses heap data-structure is used as Heapsort, with time compexity nlogn. Heapsort has 2 steps
    1) Insert all n array elements in the heap O(n)
    2) Extract min to place elements in sorted order n * O(lg n)
    So, it is now close to quicksort.
  • Priority Queue
    A heap can also be called a priority queue. It can be used to schedule events and to check which event is going to occur next, using the timestamp as key. This makes it much faster than keeping an unordered list and finding the max each time.
  • Median maintanence
    Thirdly we can use a heap for "median maintenance." You can given a sequence x1, ... xn and at each time step i, you need to give the median of {x1, ..., xi}. Use O(log i) time at each step i. We can solve this by maintaining two heaps, Hlow and Hhigh to keep track of the smallest half of the elements and the largest half of the elements respectively. Hlow supports extract-max while Hhigh supports extract-min. The key idea is to maintain the invariant that about i/2 smallest (largest) elements in Hlow (Hhigh).

    When you add a new element, if it is smallest than max element in Hlow then add it in there. Otherwise, add to Hhigh. What if there is an imbalance? That is, if Hlow has two more elements than Hhigh? Then you simply extra the max of Hlow and add to the other heap.

    So how do we compute the median? It is the max of the Hlow or the min of Hhigh. If i is even, then they are both medians. Otherwise, the median is just from the heap that has one more element than the other.
  • Speeding up algorithm like djikstra - see here.



Post a Comment