Everything's Beta

I happened to see one of my colleague’s passwords, “h3apS0r7″. As I asked him whether he actually knew how to implement it, I realized that I had never had to implement a Heapsort. And as we all (should) know: knowing how to do X and actually doing X are vastly different things.

So this post is my attempt at fixing that.

What’s Heapsort anyway? Like the name suggests it consists of

1. Building a (max/min)heap using the data
2. Plucking out the root(which is either the greatest or smallest value depending on whether you built a max or min heap) continuously such that you have the data in order.

Remind you of something? If you read just #2 you will see that Heapsort is just Selection sort powered by a heap

Let’s start off by implementing Selection sort. First we need a function pop_max(List) that returns/removes the maximum element from a list:

-module(heapsort).
-export([pop_max/1]).
 
% pop_max(List) returns {MaxValue, RestOfList}
pop_max([])->{nil,[]};
pop_max(L) -> 
     Max = lists:max(L),
     {Max,lists:delete(Max,L)}.

Integrating this into Selection sort is pretty easy too:

selectionSort([])-> [];
selectionSort(L) ->
    {Max,Rest} = pop_max(L),
    selectionSort(Rest) ++ [Max].
 
% Note: Yeah it's not tail recursive, but I think it looks cleaner.

Let’s try it out:

8> c(heapsort).                    
{ok,heapsort}
9> heapsort:selectionSort([1,5,2,77,8,3,2,5,8,12,53,1,5,87,1,4573,2,969]).
[1,1,1,2,2,2,3,5,5,5,8,8,12,53,77,87,969,4573]

Looks good to me.

Anyway, ideally we should be able to just swap out pop_max with pop_heap.

Let’s figure out how we want to implement the binary heap now. We need to support adding and removing the root from the heap.
Adding to the heap works as follows:

1. Add the item at the bottom.
2. Swap the item with it’s parent until the parent is greater than the item (a.k.a sift-up)

Removing from the heap is the inverse .i.e:

1. Pop off the root and set the last item on the lowest level as the root.
2. Swap the root with it’s children until the item is greater than it’s children(a.k.a sift-down).

Something else we want to determine is the underlining data structure for the Heap. We could use the binary tree we developed earlier, or we could use a list. Let’s go with the latter.

Anyway, I set myself a time limit of 20 minutes when I started this and it’s kinda late, so I’m going to implement the binary Heap in the next post

As promised, today we will try to re-implement the BST from last post and make it erlang-y. Once again, I am going to just implement inserts and leave the rest as as exercise for the reader. I am going to try to put down my thought process as I try to solve this.

To recap here’s what the BST insert looks like :

-record(node,{kvTuple,left,right}).
 
binsert(#node{kvTuple={CK,CV},left=L,right=R},{K,V}) when K < CK ->
    #node{kvTuple={CK,CV},left=binsert(L,{K,V}),right=R};
binsert(#node{kvTuple={CK,CV},left=L,right=R},{K,V}) ->
    #node{kvTuple={CK,CV},left=L,right=binsert(R,{K,V})};
binsert(null,{K,V}) ->
    #node{kvTuple={K,V},left=null,right=null}.

My first instinct is to give this process a “mailbox” so that we have a shared BST that can be updated by multiple processes concurrently. However, this will process the messages sequentially. To mitigate this we can spawn a process to handle each message and so parallelize it. Is this the best solution though ? As we are going utilizing parallelization, can we break this up into smaller/more processes?

What about if each node is a process? Would that work? Would this incur too much overhead ? Hopefully not. Erlang’s supposed to have really lightweight processes so we are going to assume it’s ok (maybe a future post about exactly what the overhead is).

So at this point I did a quick google search on concurrent BSTs to see if there were other ways I was missing and I ran into this post by Faud AlTabba which totally messed up this post
His post has an implementation for each of the ideas I talked about and covers everything I hoped too. So go read it. I’m going to go try to find something else to practice Erlang on.

The book I have been reading implements a Set using a BST. Implementing a naive BST
in Erlang proved much easier than I expected. Maybe thats because I just implemented inserts

I started with a function that does sorted inserts on lists :

insert([],V) -> V;
insert([H|T],V)  when V > H ->
    [H|insert(T,V)];
insert([H|T],V)  when V < H ->
    [insert(H,V)|T];
insert(H,V) ->
    [V|H].

Once I defined a node record, converting to a bst was pretty easy:

%% what our node looks like
-record(node,{kvTuple,left,right}).
 
binsert(#node{kvTuple={CK,CV},left=L,right=R},{K,V}) when K < CK ->
    #node{kvTuple={CK,CV},left=binsert(L,{K,V}),right=R};
binsert(#node{kvTuple={CK,CV},left=L,right=R},{K,V}) ->
    #node{kvTuple={CK,CV},left=L,right=binsert(R,{K,V})};
binsert(null,{K,V}) ->
    #node{kvTuple={K,V},left=null,right=null}.

Adding a “memberOf” function is pretty much exactly like the insert so I wont bother showing it here.

Anyway, since that was trivial to implement, lets take it a step further: Erlang’s strength is concurrency so next post will be about adding concurrency to this BST.

I have been meaning to read Purely Functional Data Structures for a while. So, I grabbed a copy earlier and started to work through the book using Erlang.

Translating¹ the first couple of examples to Erlang was easy and looked pretty much exactly like the ML implementations:

%concatenate 2 lists
concat([],X) -> X;
concat(Y,[]) -> Y;
concat([H|T],X) -> [H|concat(T,X)].
 
%update value at given index
update([_H|T],0,N) -> [N|T];
update([H|T],C,N) -> [H|update(T,C-1,N)].

The first exercise (2.1) was to write a function suffixes that takes a list xs and returns a list of all suffixes in decreasing order of length.

%get all suffixes for the list
suffixes([]) -> [];
suffixes([H|T]) -> [[H|T]|suffixes(T)].

These are generated in O(n) time and represented in O(n) space.


Next up implementing a Binary Search Tree…



1.Translating: Not strictly translating. I write my own from the description, then match it with the author’s ML implementation to make sure they are close enough.

Here’s some quick info on getting started with Erlang on osx:

Installation: Forget macports etc. just compile it from source :

curl http://www.erlang.org/download/otp_src_R13B.tar.gz
tar -xvfz otp_src_R13B.tar.gz
cd otp_src_R13B.tar.gz
./configure --enable-hipe
make
sudo make install

Editor/IDE:
I use aquamacs of course.
But beyond that, I don’t have a definitive answer here.
I am evaluating Distel and Erlang mode that comes with the distro.

ErlangXCode looks interesting, but I haven’t given it a go yet.