# Data Structures

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

## Understanding Heap Sort

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 the input as well as output rem...

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

## Building Heaps from an array of keys

[nextpage title="Introduction"] In the last post we learnt the basics of the heap data structure, its array and tree representations. We also learnt about the heap property and its significance. In the process of learning we understood that a given node can be disturbed and the heap property needs to be restored using the Heapify operation. Here in this post, we will try building heaps from an array of keys. Building Heaps Let us think about the easiest way to build a heap. Assume we are given the below array A: This clearly is not satisfying the max heap property because the root ...