Data Structure topics

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

data structure

Rope: the Data Structure used by text editors to handle large strings

Rope data structure is widely used by software such as text editors like Sublime, email systems like Gmail and text buffers to handle large strings efficiently.

algorithm

Algorithm to convert Binary Search Tree into Balanced Binary Search Tree

In this article, we will explore an algorithm to convert a Binary Search Tree (BST) into a Balanced Binary Search Tree in linear time O(N).

algorithm

Converting Postfix to Infix using Stack

We have explored an algorithm to convert a Postfix expression to Infix expression using Stack. This takes linear time O(N)

data structure

Count inversions in an array using Fenwick Tree

Fenwick tree is usually used for range query problems but it can be used to solve the problem of finding the number of inversions in an array efficiently.

data structure

Understanding Fenwick tree (Binary Indexed Tree) with Range product

Fenwick tree is a tree based data structure that is widely used to solve range query problems in logarithmic time O(log N) which would otherwise have taken linear time O(N). In this article, we have explained it in depth using the range product query problem.

algorithm

Learn how to traverse a Binary Tree (Inorder , Preorder , Postorder)

In this article we will learn three Depth first traversals namely inorder, preorder and postorder and their use. These three types of traversals generally used in different types of binary tree. In summary, Inorder: left, root, right; Preorder: root, left, right and Postorder: left, right, root

data structure

Optimizing a Segment Tree with Lazy Propagation

Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.

data structure

Understand everything about Binary Search Tree

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure. It can be used to search for the presence of a number in O(log(n)) time and a simple traversal gives the numbers in sorted order.

data structure

Fibonacci Heap

A Fibonacci heap is a heap data structure similar to the binomial heap. It uses Fibonacci numbers and also used to implement the priority queue element in Dijkstra’s shortest path algorithm which reduces the time complexity from O(m log n) to O(m + n log n)

data structure

Understanding Bit mask/ Bit map in depth

A bit mask is a data structure, usually an integer or array of bits, that represent a bit pattern which signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.

data structure

Binary Tree

A binary tree is a tree data structure in which each node has upto two children (that is a maximum of two children nodes), which are referred to as the left child and the right child. Implementation and applications of binary tree

data structure

Max Heap and Min Heap

A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes. The most important property of a min heap is that the node with the smallest, or minimum value, will always be the root node. Max heap is similar

data structure

Pairing Heap

Pairing heaps are a type of heap data structures which have fast running time for their operations. They are modificaton of Binomial Heap. Basically it is a type of self adjusting Binomial Heap which adjusts or rearrange themselves during the operations, due to which they remain balanced.

data structure

Leftist Heap

A leftist heap is a modification priority queue implemneted with variant of binary heap. Regarding binary heap, it is always a complete binary tree. It has two main properites Mean Heap Property and Heavy on left side and supports common operations in O(log N) time complexity.

data structure

Binomial Heap

Binomial Heap is an extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap. A Binomial Heap is a collection of Binomial trees. Binomial Heap is used to implement priority queues.

data structure

Priority Queue

Priority queue is an abstract data type which is like a queue or stack data structure with each element having a priority assigned to it. In priority queue, an element with highest priority assigned is served first, if two elements have same priority then they are served according to enqueue order

data structure

Implementing Stack using queues in two ways

A stack is based on the principle of Last-in-First-Out(LIFO). It is commonly used abstract data type with two major operations, namely pop and push. Push() and pop() are carried out in the topmost element, which is the item most recently added to the stack. Push operation adds an element to stack

data structure

Stack

Stack serves two principal operations: push, which adds an element to the collection, and pop, which removes the most recently added element that was not yet removed. We have covered functions like top, isFull, isEmpty, peek, pop, push and given an implementation example

data structure

Union Find (Disjoint Set)

A Union Find data structure (also called disjoint-set) is a data structure that keeps track of elements partitioned into a number of disjoint subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.

data structure

K Dimensional Tree

K Dimensional tree (or k-d tree) is a tree data structure that is used to represent points in a k-dimensional space. It is used for various applications like nearest point (in k-dimensional space), efficient storage of spatial data, range search. We implemented it in C++ and explained the operations

data structure

Hash Map / Hash table

Hash map (hash table, unordered map, dictionary, hash set) is a widely used efficient data structure that used to store data which can be searched in constant time O(1). This data structure is implemented over an array that maps keys to values that is it is a set of key value pairs.

data structure

XOR Linked List

XOR Linked List is the memory efficient version of Doubly Linked List because it makes use of only one space for address field with every node. It provides facilitates list traversal in both forward and backward directions. Insertion and deletion operations take constant time

data structure

Circular Queue / Ring Buffer / Circular Buffer

Circular Queue (Ring Buffer) is also a linear data structure, which follows the principle of FIFO(First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.

data structure

Implementing Queue using Stack in two ways

Queue is an abstract data structure similar to Stacks. Queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). For implementing queue using stack, one method is to make dequeue costly and other is to make enqueue costly