Common applications
Heap data structures are actually quite common, although you may not always realize you are working with one. Here are some of the most common applications for the heap data structure:
- Selection algorithms: A selection algorithm is used to determine the kth smallest or largest element in a collection, or the median valued object of a collection. In a typically collection, this operation costs O(n). However, in an ordered heap implemented with an array finding the kth element is an O(1) operation because we can find the element by simply examining the k index in the array.
- Priority queue: Priority queues are an abstract data structure similar to standard queues except that the nodes contain an additional value representing the priority of that object in relation to others in the collection. Due to the natural sorting of the heap data structure, priority queues are often implemented using the heap.
