0

Definition:

A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Implementation:

To implement Priority queue, unsorted array, sorted array and binary heap data structure are the 3 implementation strategies .

To be specific, binary heap implementation strategy can be represented using array of keys,

enter image description here

or

each key as binary node having two children.

enter image description here

Question:

Apart from priority queue implementation, Are their any other applications of using binary heap data structure?

Community
  • 1
  • 1
overexchange
  • 15,768
  • 30
  • 152
  • 347
  • 1
    See also heap sort. – Alexey Frunze Jan 04 '17 at 12:27
  • 1
    Not really. Even heapsort, it could be argued, is just populating a priority queue and then pulling things off of in order. Binary heap *is* a priority queue. The more important question is what are applications of priority queues and, of those, which are best implemented with a binary heap and which should use some other priority queue implementation. – Jim Mischel Jan 04 '17 at 13:49
  • 1. Please provide proper attribution for the source where you copied that from. See http://stackoverflow.com/help/referencing. 2. Asking for a list of all applications of binary heaps is probably too broad. 3. What research have you done? Have you looked in data structures textbooks to see what they do with a heap? – D.W. Jan 05 '17 at 00:55
  • "Not really." -- Yes, really. "Even heapsort, it could be argued, is just populating a priority queue and then pulling things off of in order. " -- Not argued validly. HeapSort sorts -- that's the *application*. That it internally uses a heap is a tautology. The reason HeapSort is used is not because it has a heap internally, but because of its performance characteristics. See https://en.wikipedia.org/wiki/Introsort – Jim Balter Jan 05 '17 at 08:54
  • @JimBalter: I think you're saying that Heapsort is a separate application because "Priority Queue Sort" wouldn't be as fast; that the heap's performance characteristics (in particular, the ability to rearrange an array in-place to build a binary heap in O(n)) makes using a binary heap superior to using just any old priority queue. Is that what you're saying? – Jim Mischel Jan 05 '17 at 17:41
  • @D.W. I have taken the reference from wiki – overexchange Jan 05 '17 at 18:01
  • Please edit the question to follow the guidelines regarding referencing your source. http://stackoverflow.com/help/referencing That includes (1) providing the name of the author or source for the material and (2) linking to the original web page. Don't just put clarifications in the comments; we want you to edit the question. "From wiki" is not specific enough; a wiki is a kind of software, and could refer to any number of websites. If you meant from Wikipedia, you should figure out what page, and then edit your question to follow the guidelines regarding attribution. – D.W. Jan 05 '17 at 18:42
  • @JimMischel No, what I'm saying is that the fact that there's a PQ inside HeapSort is completely irrelevant -- no one cares, and a totally different sort algorithm with the same performance characteristics could be substituted for HeapSort if someone discovered one. – Jim Balter Jan 05 '17 at 18:49

2 Answers2

0

A binary heap can be used to extract (max or min) element in O(logn) time. This property can be exploited to be used in many algorithms to get better run-time.

For example, once I used it in k-merge sort algorithm to increase time efficiency of sorting step of the k-merge sort. In brief, it made binary heaps of the k-subarrays, and the sorting can be achieved in linear time which is better than usual sorting step of a merge sort.

It is also used in Dijkstra's algorithm, Prim's algorithm to decrease their run time.

You can also take a look here

Community
  • 1
  • 1
CODError
  • 779
  • 2
  • 10
  • 25
  • 3
    You cannot extract elements from a binary heap in constant time. *delete-min* is an O(log n) operation. Also, the OP asked for uses of binary heap other than to implement a priority queue. All three of your examples (merge sort, Dijkstra's algorithm, Prim's algorithm) are based on priority queues. Binary heap is just a convenient implementation. – Jim Mischel Jan 04 '17 at 13:54
  • I corrected my answer. thanks for pointing it out. I am trying to list the few usage of binary heaps. I didn't talk about the implementation. If you have any situation when you don't use a binary heap as a priority queue, then you are most welcome to leave a comment. I will be glad to learn. – CODError Jan 05 '17 at 08:27
  • "extract (max or min) element" -- this is virtually the definition of a priority queue, so you haven't answered the question, as @JimMischel pointed out. "If you have any situation when you don't use a binary heap as a priority queue" -- you have it backwards. There are several ways to implement priority queues without using heaps ... the OP mentions sorted and unsorted arrays, and there are numerous others. The question is whether binary heaps are good for anything else. See my answer for ... an actual answer. Edit: I think maybe you didn't have backwards, just poorly phrased. – Jim Balter Jan 05 '17 at 08:46
  • @JimBalter I see in your answer that you suggest heapsort as a good application of binary heap. So you think heapsort algorithm doesn't use the property of extracting min/max element from the tree? Is it not just using a binary heap as a priority queue internally? I don't really understand your point here. – CODError Jan 05 '17 at 09:35
  • @CODError "So you think heapsort algorithm doesn't use the property of extracting min/max element from the tree?" -- No, I don't think that. "I don't really understand your point here" -- I explained it in a comment under the OP's question. Extraction of min/max isn't the *reason* HeapSort is used ... the reason is solely its performance characteristics. Some totally different algorithm with the same performance characteristics could be used instead if someone discovered one. – Jim Balter Jan 05 '17 at 18:46
0

Binary heaps have one other useful (and major) application: HeapSort. HeapSort has higher overhead than QuickSort but its worst case is O(n log n) vs. QuickSort's O(n*n). QuickSort can be improved upon to obtain a worst case of O(n log n) by switching to HeapSort once the interval is sufficiently short -- this is called IntroSort, and is what is used in the STL and the C++ standard library. See https://en.wikipedia.org/wiki/Introsort

Jim Balter
  • 16,163
  • 3
  • 43
  • 66