Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.
As an alert commenter pointed out, I left out one really important thing in my earlier post about finger trees. That's what I get for trying to write when I'm sick :-). Seriously, this is a point that's implied...
For ages, I've been promising to write about finger trees. Finger trees are an incredibly elegant and simple structure for implementing sequence-based data structures. They're primarily used in functional languages, but there's nothing stopping an imperative-language programmer from using...
This post is very delayed, but things have been busy. I'm working my way up to finger trees, which are a wonderful functional data structure. They're based on trees - and like many tree-based structures, their performance relies heavily...
Last week, I promised to continue my discussion of ropes. I'm going to break that promise. But it's in a good cause. If you're a decent engineer, one of the basic principles you should follow is keeping this as...
It's been a while since I've written about any data structures. But it just so happens that I'm actually really working on implementing a really interesting and broadly useful data structure now, called a Rope. A bit of background,...
Another cool, but frequently overlooked, data structure in the tree family is called the B-tree. A B-tree is a search tree, very similar to a BST in concept, but optimized differently. BSTs provide logarithmic time operations, where the performance...
Last post, I described the basic idea of the binary heap data structure. But I didn't talk about how to implement it - and there's a very cool way of implementing it - optimally space efficient, very fast, and...
One of the most neglected data structures in the CS repertoire is the heap. Unfortunately, the jargon is overloaded, so "heap" can mean two different things - but there is a connection, which I'll explain in a little while....