There seemed to be a bit of confusion in regards to the utility of heaps. Let us recap some of the main distinctions of a heap and where it is typically useful and where it is not. Heaps are foremost a data structure for performing incremental calculations that involve ranking. Implementations of heaps are found as priority queues are found in nearly all programming languages. One practical use of heaps is priority scheduling. Heaps generally speaking aren’t great for one shot computations. For example, using heaps for a one time total sorting isn’t as helpful because it’s worst case running time of O(N log N) is no better than merge sort. If one was looking to sort unrelated arrays of ints, one won’t be able to benefit from heaps. Where heaps shine is if we can maintain the heap property each iteration and not having to redo work for each iteration. Consider the following example, we want to write a function that returns the top 5 most visited websites where for each function call we will be adding a website with an associated view count or update an existing website’s count. We can certain get this ranking be sorting everything each function call, but even for the very fast O(n) counting sort, it is expensive. A heap can do this in log N time per iteration.
One alternative that was mentioned is C#’s SortedList. SortedList keeps its contents in sorted sorted order at all times. Functionally, you can solve the running median problem with a SortedList. Where it diverges from the heap is the running time. Inserting into SortedList isn’t too bad at log N if the new element is added at end of list otherwise it is O(N), but deleting from the SortedList is O(N). So complexity of each iteration using SortedList is O(N) and over N iterations O(N2).
One important example of a binary heap implementation of priority queue is Dijkstra's single source shortest path algorithm. For sparse graphs, it turns out to be a good technique to reducing the running time of the algorithm to E log V due to the fact that it can extract min and decrease keys in log time.
Comments
Post a Comment