Treap (Tree + Heap)
Treap is an efficient and simple data structure that combines the best of both binary search trees and heaps. It provides the benefits of efficient search, insert, and delete operations.
Category: Special Data Structures
Estimating Percolation in a Matrix Network
Dynamic connectivity algorithms provide an efficient way to model and analyze percolation in a grid of sites.
Comparing Performance of Disjoint-Set Algorithms: Quick Union, Quick Find, and Weighted Quick Union
Disjoint-set data structures, commonly known as Union-Find, are fundamental data-structures in computer science for efficiently solving problems related to connectivity in graphs or set operations.
Comparing Order Statistics Algorithm and Min Heap for Finding the Kth Smallest Element
Both methods provide effective solutions for finding the kth smallest element in a list of numbers. Understanding their strengths and trade-offs will help you select the most suitable approach for your use case.
LRU (Least Recently Used) Cache | Algorithm & Implementation
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.
Data Structures for Disjoint Sets | Union Find Algorithm
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.
C++ Standard Template Library (STL) – [Heap]
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.
Heap Data structure | Heap Sort in C++
The Heapsort algorithm uses Heap data structure to sort an array in O(nlogn) time complexity. It starts by calling Build-Max-Heap.
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 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.
Segment Tree (Update) for Range Min Query and Range Sum Query
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.