Data Structure topics

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

data structure

Skip List

A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items. A skip list allows the process of item look up in efficient manner. The time complexity of operations are O(log N)

data structure

Octree data structure

Octree is a tree data structure where each internal node has 8 children. An octree is generally used to represent relation between objects in a 3-dimensional space. It is used in 3D computer graphics. Octrees are also used for nearest neighbor search which can be done easily in logarithmic time.

data structure

Palindromic Tree (Eertree)

Palindromic tree (Eertree) is a tree based data structure that is specifically used to tackle problems involving palindromes of a string like 'longest palindrome in a string', 'count of plaindromic substrings'. It keeps track of all palindromic substrings of a string in linear time and space

data structure

Fusion Tree

Fusion tree is a tree data structure that implements associative array in a known universe size. Fusion trees are used to solve predecessor and successor problem. We have covered sketch, parallel comparison, predecessor and successor and insert operations in O(log N) time and O(N) space complexity

data structure

Doubly Linked List

Doubly Linked List has the flexibility of traversing the list in both the ways i.e., forward and backward unlike singly linked list where movement is restricted in forward direction only. Doubly Linked List contains an extra pointer to link the previous node which enables the backward traversing.

data structure

Implementing Queue using Linked list

A queue (First in First out) is an ordered collection of items where the addition of new items happens at one end, called the rear, and removal of existing items occurs at the other end called front. It can be implemented using Linked Lists which brings many advantages over array implementation

data structure

Quadtree

Quadtree is a tree data structure which is used to represent 2-dimensional space. It finds major applications in computer graphics where it is used to represent relations between objects in a 2D space and for image compression. We discussed point region (PR) quadtree which store points in a 2D space

data structure

Van Emde Boas tree

Van Emde Boas tree is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations (insert, delete, lookup, maximum, minimum, successor and predecessor) in O(log log M) time, where M is the maximum number of elements that can be stored in the tree.

data structure

Queue

Queue is a linear data structure that can be used to store data in order by imposing rules on data insertion and deletion. It has found immense use and can be implemented using arrays and linked lists. The operations include enqueue and dequeue which are of O(1) time complexity with space of O(N)

data structure

Y fast trie

Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values

data structure

X-fast trie

X-fast trie is a data structure used to store integers from a bounded domain. It is a bitwise trie, i.e. a binary tree where each subtree stores values having binary representations with common prefix. It is a trie of hash tables and supports successor and predecessor operations in log log U time

data structure

AVL Tree: A tree that can stay balanced by rotating

An AVL Tree (Adelson-Velsky and Landis tree) is a self balancing binary search tree such that for every internal node of the tree the heights of the children of node can differ by at most 1. It uses four types of rotations to keep itself balanced and delete, insert and search take O(log N) time

data structure

Treap / Randomized cartesian tree

A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity

data structure

Cartesian Tree

A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. An inorder traversal of the tree would give the original sequence used to form the tree. It is used as binary search tree for an ordered sequence

data structure

Prefix sum array

Prefix Sum array is a data structure design which helps us to answer several queries such as sum in a given range in constant time which would otherwise take linear time. It requires a linear time preprocessing and is widely used due to its simplicity and effectiveness.