Ebbe’s D-universe

This is my first “code” post. I’ve implemented a very basic binary minimum heap in D. A heap is a way to structure your data in a very nice way. It’s running time is quite acceptable, as any operation runs in O(lg n).

A reason to have a min-heap, could be if you wanted to implement the A* path-finding-algorithm. There are of course many more reasons

What it does, is keeping track of values along with a key. It sorts the different values according to the key. You can then extract the value that currently has the smallest key.

Here’s the most important lines:

3. /**
4. Heap made by Esben Damgaard
5. Posted on the blog d.hvemder.dk
6.  
7. "THE BEER-WARE LICENSE" (Revision 42):
8. <ebbe _at_ skummer.com> wrote this file. As long as you retain this notice you can do whatever you want with this stuff. If we meet some day, and you think this stuff is worth it, you can buy me a beer in return. Esben Damgaard
9.  
10. **/
11.  
12. void main() {
13. MinHeap!(char[]) heap = new MinHeap!(char[])();
14. heap.insert(4, "I should be first out( remember to visit d.hvemder.dk )");
15. writefln(heap.extractMin() );
...
25. };
26.  
27. class MinHeap(T) {
...
91. public:
92. void insert(int argKey, T argValue) {
93. nodes.length = nodes.length + 1;
94. nodes[length-1] = new Node!(T)(argKey, argValue);
95. decreaseKey(nodes.length-1, argKey);
96. }
97.  
98. T showMin() {
99. return nodes[0].getValue();
100. }
101.  
102. T extractMin() {
103. if( nodes.length < 1 )
104. return cast(T) null;
105. T temp = nodes[0].getValue();
106. nodes[0] = nodes[length-1];
107. heapify(0);
108. nodes.length = nodes.length - 1;
109. return temp;
110. }
111. };
112. Download this code: heap.d

As you can see you are welcome to do whatever you want to do with the file, as long a you keep my beer-ware license in the file.

The implementation is still quite simple, and I intend to extend it to be both a min-heap and a max-heap. It should also be possible to change a values key. I haven’t quite figured out how to do that though It could be done by just saving an id along with the insert. You should then be able to search for that id. The running time, though isn’t that good for searching in heaps like this one. It needs a little more thinking.

A smart thing I learned while implementing this, is in line 27. Here it is up to the user to define what type the values should be. This makes the heap very dynamic in what can be stored. In line 13 there’s an example where I create a MinHeap which can store char[]. Nice