FibonacciHeap does not work

[GoogleCodeExporter]

What steps will reproduce the problem?
1. ScalaCheck property as follows does not run ok for FibonacciHeap but does 
work for BinomialHeap:

import org.scalacheck._
import net.pragyah.scalgorithms.heaps._

object HeapSpecification extends Properties("Heap") {
  property("FibonacciHeap insert list of values and extract them in order") = Prop.forAll { l: List[Int] => 
    val f = new FibonacciHeap[Int](Int.MinValue)
    l.foreach (f.insert(_))
    (l.map (x => f.extractMin().get)) == l.sorted    
  }
  property("BinomialHeap insert list of values and extract them in order") = Prop.forAll { l: List[Int] => 
    val f = new BinomialHeap[Int](Int.MinValue)
    l.foreach (f.insert(_))
    (l.map (x => f.extractMin().get)) == l.sorted    
  }
}

2. Running it gives me consistently property violations, for example for a list 
like:

[info] ! Heap.FibonacciHeap insert list of values and extract them in order: 
Exception raised on property evaluation.
[info] > ARG_0: List("0", "-2", "0", "0", "-1", "-3", "0", "0")
[info] > Exception: java.util.NoSuchElementException: None.get
[info] + Heap.BinomialHeap insert list of values and extract them in order: OK, 
passed 100 tests.


What is the expected output? What do you see instead?

I'm expecting a heap to be able to get in a list of (semi-)random values and 
successive extractMins to return them in an ascending order. I'd also guess 
FibonacciHeap works in a same way as BinomialHeap.



What version of the product are you using? On what operating system?

The scalgorithms was a svn checkouted version few days old (2011-04-26 or so).

[info] Building project HeapTester 1.0 against Scala 2.8.1
[info]    using HeapTesterProject with sbt 0.7.5 and Scala 2.7.7

This is Mac OSX that I'm running the test in.

Mach kernel version:
     Darwin Kernel Version 10.7.0: Sat Jan 29 15:17:16 PST 2011; root:xnu-1504.9.37~1/RELEASE_I386
Kernel configured for up to 4 processors.
4 processors are physically available.
4 processors are logically available.
Processor type: i486 (Intel 80486)
Processors active: 0 1 2 3
Primary memory available: 4.00 gigabytes
Default processor set: 77 tasks, 420 threads, 4 processors



Please provide any additional information below.

I briefly went over Introductions to Algorithms book FibonacciHeap section and 
compared the implementation to the pseudo-code. I could not spot any glaring 
error. I did not read the keyNode map structure closely.  I'm sorry I cannot 
submit a patch. I hope someone can take a deeper look at this with the 
associated test case.

The scala compiler gave few warnings. I do not guess these affect the behavior 
at all, as I also fixed them by using Map.remove instead of Map.removeKey and 
List.filterNot instead of List.remove and the case failed anyway.

Original issue reported on code.google.com by aleksi.n...@gmail.com on 1 May 2011 at 2:37