Ahh, Heaps.
Heaps are one of those data structures that turn up everywhere. They serve a humble purpose: find the maximum value (depending on if you're using min or max ordering) of a set efficiently. It is this very purpose that imbues
Randomized Meldable Heaps
When it comes to priority queues, the binary heap is the go-to data structure when it comes to implementation, and with good reason. Binary heaps offer worst-case logarithmic complexity for all operations that i
Foreach
The "foreach" loop is a special case of the for loop, usually enacted on a linear container such as an array or a list, where for every iteration of the loop, some action is performed on a member of the container until that actio
Computer Sciences better mouse trap
In the beginning the large majority of sort implementations were the more commonly known quadratic sorts: selection sort, insertion sort, and the omnipresent bubble sort. Radix sort was in use for the physic
Quicksort
In my previous post on quick sort I covered in detail the recursive implementation of the famous sorting algorithm. In that post I mentioned that a downside of quick sort is that it has the potential to encounter worst-case quadrati
Search
Recent Posts
-
DFA Minimization: Moore's Algorithm
-
Parsing Regular Expressions with MGCPGen
-
Determinization: Converting εNFA to DFA
-
Implementing Lexical Scoping: Resolving Variable Names with De Bruijn Indices
-
Improving Balance of Ternary Search Tries
-
Making Sense of LALR Parser Construction
-
Compiling Set Comprehensions to Bytecode: an exercise in managing abstractions
-
Fast Multi-Pattern String Searching with the Aho-Corasick Algorithm
-
Capture Groups: Tracking Regular Expression Sub Matches
-
Resolving Shift/Reduce Conflicts With Operator Precedence
Meta