Special Data Structures Archives

C++ Standard Template Library (STL) – [Priority queue]

In the last post we discussed about C++ Standard Template Library (STL) Linked List. In this post we would learn about STL Priority queue and using it as Max/Min Heap. Priority Queue A priority queue is a data structure for maintaining a set of elements having an associated value. Priority Queue […]

C/C++, Heaps, Special Data Structures

Huffman Code Explained using Heap [Introduction to Algorithms book]

Huffman codes are a widely used technique for compressing data. Huffman codes is a greedy algorithm to build up an optimal way of representing each character as a binary string. Suppose we have a 10,000 character data file that we wish to store. And we observe a character ‘a’ occurs very […]

Greedy approach, Heaps, Special Data Structures

Segment Tree (Update) for Range Min Query and Range Sum Query

In the last post we discussed about constructing a segment tree and querying the segment tree. Time complexity of constructing a segment tree is O(n) and querying (RMQ) the segment tree is O(logn). Whereas space complexity of segment tree is O(n). As we need an array of size (2n-1) to construct […]

Special Data Structures

Trie – LeetCode Solution [Medium]

A Trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Applications There are various applications of this special data structure such as : Autocomplete in mobile and web applications Spelling checker Solving word games and many more. Implementation Trie is […]

Special Data Structures

Segment Tree

Segment tree is a data structure that is used to solve a certain problem, called RMQ (Range Minimum Query).

Special Data Structures