Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@blakesmith
Created November 11, 2013 15:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save blakesmith/7415238 to your computer and use it in GitHub Desktop.
Save blakesmith/7415238 to your computer and use it in GitHub Desktop.
property("meld two heaps with mins") = forAll { (h1: H, h2: H) =>
def getSeq(l: List[A], heap: H): List[A] = isEmpty(heap) match {
case true => l.reverse
case false => getSeq(findMin(heap) :: l, deleteMin(heap))
}
if (isEmpty(h1) || isEmpty(h2)) true
else {
val melded = getSeq(List(), meld(h1, h2))
val melded2 = getSeq(List(), meld(deleteMin(h1), insert(findMin(h1), h2)))
melded.sorted == melded2.sorted
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment