Data Structures

This category contains all the posts related to data structures. For e.g.: Hash Tables, Linked Lists, Trees, Graphs, Heaps, Tries etc..

Euler Graphs – Origin of Graph Theory

This should have been my first post in the Graph Theory series but nevertheless I got time to discuss this now. Every one must have heard the famous problem of Seven Bridges of Königsberg. If not, then please take some time to read about the problem either on the Wikipedia or right down below: The city of Konigsberb is located on both the banks of the river Pregel(Kaliningrad, Russia - former Prussia).  The city also included two big islands and these islands were connected to each other and the main land by the means of seven bridges. Something like below: The problem is to devise a...

Graph Theory Applications – The Instant Insanity Puzzle

[nextpage title="Applications of Graph Theory"] Graph Theory is used in modelling and solving a lot of real world problems, games and puzzles. Here we discuss a very famous puzzle " The Instant Insanity " problem. The goal of this post is to demonstrate that such complicated problem statements can be so easily modeled and solved using Graph Theory. Also I would like to build some more  interest into Graph Theory. If you want to feel more comfortable with the basics of Graph Theory, here is a list of primers you might like to read once. Problem Definition - The Instant Insanity Puzzle The...

Priority Queues

Introduction You have N distinct jobs to process, and you are given the responsibility to schedule them on the only available job processor. New jobs keeps on getting added into the set of available jobs. Not all the jobs are to be executed as they come. There might be few which needs to be executed immediately and few can be postponed for some time. You have an efficiently algorithm to decide the priority of an incoming job. The task at hand is as follows: To schedule available jobs based on the priority assigned to them. Add new jobs to the set after assigning a priority to it. ...

Understanding Heap Sort

[nextpage title="Introduction"] Heap Sort is one of the efficient sorting algorithms with a guaranteed worst case running time of O(NlogN). This is an in place sorting algorithm but it does not offer stable sorting. In place Sorting: A sorting algorithm which sorts the input using very small or no extra space. It means that the input data is overwritten by the resulting output data. Stable Sorting: A stable sorting algorithm is one, in which the relative order of equal keys is preserved. It means if there are non unique keys in the input data, then their relative order of occurrence in ...

Operations on a Heap

Introduction In this post, we will try to put together all the leanings from the previous posts and define the basic operations on a heap. Also, we will try and derive the running time of each such operation and write code for the same. Also, we will discuss an interesting problem statement which can be easily solved using the heap property. Basic Operations on Heap The heap can support the following basic operations as any other data structure IncreaseKey - Changes the key value of a given node to a new value. It is assumed that the new value is at least as big as the current value....