PriorityQueueのPairringHeapの実装を、再起呼び出しを使わないよう変更

diff --git a/src/LibNMeCab/Core/PriorityQueue.cs b/src/LibNMeCab/Core/PriorityQueue.cs
index 525e2af..5a70c74 100644 (file)
--- a/src/LibNMeCab/Core/PriorityQueue.cs
+++ b/src/LibNMeCab/Core/PriorityQueue.cs
@@ -46,6 +46,8 @@ namespace NMeCab.Core
 
         public void RemoveFirst()
         {
+            if (this.Count == 0) throw new InvalidOperationException("Empty");
+
             this.rootNode = this.Unify(this.rootNode.Childs);
             this.Count--;
         }
@@ -71,14 +73,27 @@ namespace NMeCab.Core
         {
             if (nodes == null || nodes.Count == 0) return null;
 
-            Node x = nodes.First.Value;
-            nodes.RemoveFirst();
-            if (nodes.Count == 0) return x;
+            Node[] tmp = new Node[nodes.Count / 2]; //擬似的Stack
+
+            for (int i = 0; i < tmp.Length; i++)
+            {
+                Node x = nodes.First.Value;
+                nodes.RemoveFirst();
+                Node y = nodes.First.Value;
+                nodes.RemoveFirst();
+                tmp[i] = this.Merge(x, y);
+            }
+
+            Node z;
+            if (nodes.Count == 1)
+                z = nodes.First.Value;
+            else
+                z = null;
 
-            Node y = nodes.First.Value;
-            nodes.RemoveFirst();
+            for (int i = tmp.Length - 1; i >= 0; i--)
+                z = this.Merge(tmp[i], z);
 
-            return this.Merge(this.Merge(x, y), this.Unify(nodes));
+            return z;
         }
     }
 }