From dabe74f963928a1d34dfc3092e86eccff431d7fa Mon Sep 17 00:00:00 2001
From: komutan <t_komuta@nifty.com>
Date: Wed, 8 Jul 2015 20:04:47 +0900
Subject: [PATCH] =?utf8?q?PriorityQueue=E3=81=AEPairringHeap=E3=81=AE?=
 =?utf8?q?=E5=AE=9F=E8=A3=85=E3=82=92=E3=80=81=E5=86=8D=E8=B5=B7=E5=91=BC?=
 =?utf8?q?=E3=81=B3=E5=87=BA=E3=81=97=E3=82=92=E4=BD=BF=E3=82=8F=E3=81=AA?=
 =?utf8?q?=E3=81=84=E3=82=88=E3=81=86=E5=A4=89=E6=9B=B4?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 src/LibNMeCab/Core/PriorityQueue.cs | 27 +++++++++++++++++++++------
 1 file changed, 21 insertions(+), 6 deletions(-)

diff --git a/src/LibNMeCab/Core/PriorityQueue.cs b/src/LibNMeCab/Core/PriorityQueue.cs
index 525e2af..5a70c74 100644
--- 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;
         }
     }
 }
-- 
2.11.0