Data Structures:
Category: Data Structures
A while ago, I wrote a couple of posts that claimed to talk about finger trees. Unfortunately, I really botched it. I'd read a bunch of data structure papers, and managed to get myself thoroughly scrambled. What I wrote...
Read on »
Posted by Mark C. Chu-Carroll at 10:47 AM • 19 Comments •
Category: Haskell
In the Haskell stuff, I was planning on moving on to some monad-related stuff. But I had a reader write in, and ask me to write another post on data structures, focusing on a structured called a zipper. A...
Read on »
Posted by Mark C. Chu-Carroll at 8:23 PM • 19 Comments •
Category: Data Structures
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...
Read on »
Posted by Mark C. Chu-Carroll at 10:28 AM • 11 Comments •
Category: Data Structures
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...
Read on »
Posted by Mark C. Chu-Carroll at 4:36 PM • 18 Comments •
Category: Data Structures
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...
Read on »
Posted by Mark C. Chu-Carroll at 9:55 AM • 5 Comments •
Category: Data Structures
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...
Read on »
Posted by Mark C. Chu-Carroll at 9:03 PM • 25 Comments •
Category: Data Structures
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,...
Read on »
Posted by Mark C. Chu-Carroll at 10:14 PM • 11 Comments •
Category: Data Structures
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...
Read on »
Posted by Mark C. Chu-Carroll at 5:53 PM • 10 Comments •
Category: Data Structures
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...
Read on »
Posted by Mark C. Chu-Carroll at 10:49 AM • 24 Comments •
Category: Data Structures
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....
Read on »
Posted by Mark C. Chu-Carroll at 11:37 AM • 34 Comments •