Binary search is an extremely useful and popular algorithm used for quickly searching in a sorted array. Binary search is even used by people in real life (outside of programming) when they play the guess the number game. One person thinks a number between 1 and 100, and the other person tries to guess. The response is only less, equal or greater. If you guess 50 and get a _less_ response, you just narrowed down the search to half the interval, 1 to 50. You can keep going and guess 25. No matter if what answer you get, you either win, or narrow down the interval again to a half. This is how binary search works.
A binary heap is a simple data structure most often used for implementing priority queues. In a more general sense, a *heap* is a tree-based data structure which satisfies the *heap property*, and a *binary heap* is a *heap* which uses a *binary tree* to store its data. Any arbitrary binary tree which satisfies the following two properties can be considered a binary heap.
Having just implemented and tested a Fibonacci heap on a large dataset I thought I’d write up a bit about it, mostly so that I can reference this post later in the future, and to help me remember things I’ve learned better. Note that this blog post is not a tutorial on how to implement a Binomial/Fibonacci heap.
First, let’s begin with a few definitions. Throughout the article we’ll be talking about min-heaps.
Read More →
A Bloom filter is a simple yet powerful data structure. It allows you to answer the question have you seen this before? in a very fast and memory efficient way. Unlike a regular set, a Bloom filter only needs to store a few bits per item instead of storing the whole thing.
A bit vector (also known as bit set or bit array) is a set data structure which uses only 1 bit per element. It answers the question is X in the set?.
The main advantage is memory efficiency and speed, as the memory is allocated in a single continuous block, making it very cache friendly (unlike some tree based data structures), and requiring only a few bitwise operations to access/modify elements in the set.
Read More →