Application of heap (in computer science)

Following are applications of heap:

• Heap Sort - fast way to get minimum computation
  SelectionSort() with time complexity - Θ(n²) 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 x₁, ... x_n and at each time step i, you need to give the median of {x₁, ..., x_i}. Use O(log i) time at each step i. We can solve this by maintaining two heaps, H_low and H_high to keep track of the smallest half of the elements and the largest half of the elements respectively. H_low supports extract-max while H_high supports extract-min. The key idea is to maintain the invariant that about i/2 smallest (largest) elements in H_low (H_high).
  
  When you add a new element, if it is smallest than max element in H_low then add it in there. Otherwise, add to H_high. What if there is an imbalance? That is, if H_low has two more elements than H_high? Then you simply extra the max of H_low and add to the other heap.
  
  So how do we compute the median? It is the max of the H_low or the min of H_high. 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.