LRU (Least Recently Used) Cache is a type of cache replacement algorithm, where the least recently used item is evicted when the cache is full.
This data structure is useful in situations where we need to group items together based on certain criteria, and then perform operations on these groups.
The Heap data structure is an array that can be viewed as a complete Binary Tree. Each node in the tree corresponds to an element of the array A.
In this post we will learn about, how to build min/max Heaps using STL.
The Heapsort algorithm uses Heap data structure to sort an array in O(nlogn) time complexity. It starts by calling Build-Max-Heap.
In the last post we discussed about C++ Standard Template Library (STL) Linked List. In this post we will learn about STL Priority queue and using it as Max/Min Heap. A priority queue is a data structure for maintaining a set of elements having an associated value.
Update query (Range min query) For update query, we are given an index which needs to be updated. Let val be the value needed to be changed of a given node x. We start from the root of the segment tree and update all nodes (containing minimum value from given index) which have given index in their range. If a node doesn’t have a given index in its range, we don’t make any changes to that node.
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. Trie is an efficient information reTrieval data structure and hence the name Trie. It is a special data structure used to store strings. It consists of nodes and edges like a tree.
Segment tree is a data structure that is used to solve a certain problem, called RMQ (Range Minimum Query).