Skip to main content

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 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.

Labels:

Comments

Post a Comment

Popular posts from this blog

Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like . For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting
Post a Comment
Read more

Top 5 Books for Language-Specific Interview Questions

Shrunk and White of Programming When you put down that you know a certain programming language or languages on your resume, you are setting certain expectations for the interviewer. I would strongly caution against putting down "expert" in a language unless you invented or are one of the language's maintainers. You are giving your interviewer the license to quiz you on programming language lore. There are a handful of concepts that are considered "standard" knowledge for each language which go broadly beyond syntax and general semantics. These concepts commonly involve major pitfalls in a given language and the idiomatic technique for negotiating these pitfalls and writing efficient and maintainable code. Note, although the concepts are considered idiomatic, you can seldom infer them from knowledge of syntax and semantics alone. The tricky part here is that most courses that teach a particular programming language do not cover these idiomatic techniques and e
Post a Comment
Read more

What Are The Types of Questions Asked In Tech Interviews?

Many interview prep books focus on the bread and butter coding interviewing questions, but in real interviews your interviewer may pose other types of questions. It is important to be comfortable and come prepared for these other types of questions which depart dramatically for coding questions yet still may bear considerable weight in your interview evaluation. Behavioral & experience These are the standard non-technical interview questions where the interviewer asks about what you did in particular scenarios and how you performed in the roles listed on your resume. Language specific knowledge questions There is a manageable set of questions for each common programming language. There are questions for uncommon languages too should to encounter a company that emphasizes their use of some of the lesser known languages. Usually these questions attempt to probe for your knowledge of some differentiator and key feature of the programming language. For example, virtual functio
Post a Comment
Read more