sorting.heap: adding Heapsort implementation.

diff --git a/extra/sorting/heap/authors.txt b/extra/sorting/heap/authors.txt
new file mode 100644 (file)
index 0000000..e091bb8
--- /dev/null
+++ b/extra/sorting/heap/authors.txt
@@ -0,0 +1 @@
+John Benediktsson

diff --git a/extra/sorting/heap/heap-tests.factor b/extra/sorting/heap/heap-tests.factor
new file mode 100644 (file)
index 0000000..9e6f130
--- /dev/null
+++ b/extra/sorting/heap/heap-tests.factor
@@ -0,0 +1,14 @@
+USING: kernel sequences tools.test ;
+IN: sorting.heap
+
+{ { } } [ { } heapsort ] unit-test
+{ { 1 } } [ { 1 } heapsort ] unit-test
+{ { 1 2 3 4 5 } } [ { 1 4 2 5 3 } heapsort ] unit-test
+
+{
+    { "fred" "dino" "wilma" "betty" "barney" "pebbles" "bamm-bamm" }
+} [
+    { "fred" "wilma" "pebbles" "dino" "barney" "betty" "bamm-bamm" }
+    [ length ] heapsort-with
+] unit-test
+

diff --git a/extra/sorting/heap/heap.factor b/extra/sorting/heap/heap.factor
new file mode 100644 (file)
index 0000000..eb5a11c
--- /dev/null
+++ b/extra/sorting/heap/heap.factor
@@ -0,0 +1,29 @@
+! Copyright (C) 2014 John Benediktsson
+! See http://factorcode.org/license.txt for BSD license
+
+USING: assocs heaps kernel sequences ;
+
+IN: sorting.heap
+
+<PRIVATE
+
+: (heapsort) ( alist accum -- sorted-seq )
+    [ >min-heap ] [ [ [ push ] curry slurp-heap ] keep ] bi* ; inline
+
+PRIVATE>
+
+: heapsort ( seq -- sorted-seq )
+    [
+        [ dup zip ]
+        [ length ]
+        [ new-resizable ] tri
+        (heapsort)
+    ] [ like ] bi ;
+
+: heapsort-with ( seq quot: ( elt -- key ) -- sorted-seq )
+    [
+        [ keep ] curry [ { } map>assoc ] curry
+        [ length ]
+        [ new-resizable ] tri
+        (heapsort)
+    ] 2keep drop like ; inline

diff --git a/extra/sorting/heap/summary.txt b/extra/sorting/heap/summary.txt
new file mode 100644 (file)
index 0000000..e6f2c1f
--- /dev/null
+++ b/extra/sorting/heap/summary.txt
@@ -0,0 +1 @@
+Heapsort

diff --git a/extra/sorting/heap/tags.txt b/extra/sorting/heap/tags.txt
new file mode 100644 (file)
index 0000000..1e3d675
--- /dev/null
+++ b/extra/sorting/heap/tags.txt
@@ -0,0 +1,2 @@
+collections
+algorithms