Skip to main content

Posts

Showing posts from November 12, 2017

Why Heaps?

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 w…