Fibonacci Heap 1.1 has been released. Version 1.1 fixes a big problem with using key heaps. It also adds support to increase the key in key heaps.
The fib package is an implementation of a Fibonacci Heap. A Fibonacci Heap is a very efficient heap. The cost of an insert is O(1), and the amortized cost of an extract minimum is O(lgn). You can extract an already inserted item out of order in O(lgn). The way the fibonacci heap obtains this is by delaying the organizing of the items until you extract.
It supports two methods of ordering the heap. You can either set a function to compare your data, or you can pass in an integer value as the sort key. These two methods are mutually exclusive. The type of heap you create depends upon which make heap function you call. If you call fh_makeheap, you have to call fh_setcmp to set the comparision function and fh_insert to add items. If you call fh_makekeyheap, you then call fh_insertkey with a key value to add items.
The fib package had some problems up to this point, i.e., it wouldn't work correctly. I have now fixed this. I have also fixed a performance problem w/ fh_consolidate and added a fh_deleteheap function to destroy a heap.
I have completed a review of the Fibonacci source code and have fixed a few minor things. I have also recently received a couple of bug reports and have fixed both of them. Read the README in the archive to find out more info.
Source for Fibonacci Heap version 1.1. Released January 14, 2003.
Source for Fibonacci Heap version 1.0. Released April 30, 2000.
Please see the man pages that are a part of the pacakge. I will put up an archive of all the man pages for the various projects I have done.
This article is translated to Serbo-Croatian language by Jovana Milutinovich from Webhostinggeeks.com.