diff --git a/src/include/fst/minimize.h b/src/include/fst/minimize.h
index 7e59f9c..69518c9 100644
--- a/src/include/fst/minimize.h
+++ b/src/include/fst/minimize.h
@@ -181,9 +181,7 @@ class CyclicMinimizer {
     }
   };

-  using ArcIterQueue =
-      std::priority_queue<RevArcIterPtr, std::vector<RevArcIterPtr>,
-                          ArcIterCompare>;
+  using ArcIterQueue = std::vector<RevArcIterPtr>;

  private:
   // Prepartitions the space into equivalence classes. We ensure that final and
@@ -241,30 +239,26 @@ class CyclicMinimizer {
     P_.Initialize(Tr_.NumStates() - 1);
     // Prepares initial partition.
     PrePartition(fst);
-    // Allocates arc iterator queue.
-    aiter_queue_ = std::make_unique<ArcIterQueue>();
   }
   // Partitions all classes with destination C.
   void Split(ClassId C) {
+
     // Prepares priority queue: opens arc iterator for each state in C, and
     // inserts into priority queue.
     for (PartitionIterator<StateId> siter(P_, C); !siter.Done(); siter.Next()) {
       const auto s = siter.Value();
       if (Tr_.NumArcs(s + 1)) {
-        aiter_queue_->push(std::make_unique<RevArcIter>(Tr_, s + 1));
+        aiter_queue_.push_back(std::make_unique<RevArcIter>(Tr_, s + 1));
       }
     }
+    std::make_heap(aiter_queue_.begin(), aiter_queue_.end(), ArcIterCompare{});
     // Now pops arc iterator from queue, splits entering equivalence class, and
     // re-inserts updated iterator into queue.
     Label prev_label = -1;
-    while (!aiter_queue_->empty()) {
-      // NB: There is no way to "move" out of a std::priority_queue given that
-      // the `top` accessor is a const ref. We const-cast to move out the
-      // unique_ptr out of the priority queue. This is fine and doesn't cause an
-      // issue with the invariants of the pqueue since we immediately pop after.
-      RevArcIterPtr aiter =
-          std::move(const_cast<RevArcIterPtr &>(aiter_queue_->top()));
-      aiter_queue_->pop();
+    while (!aiter_queue_.empty()) {
+      std::pop_heap(aiter_queue_.begin(), aiter_queue_.end(), ArcIterCompare{});
+      RevArcIterPtr aiter = std::move(aiter_queue_.back());
+      aiter_queue_.pop_back();
       if (aiter->Done()) continue;
       const auto &arc = aiter->Value();
       auto from_state = aiter->Value().nextstate - 1;
@@ -274,7 +268,10 @@ class CyclicMinimizer {
       if (P_.ClassSize(from_class) > 1) P_.SplitOn(from_state);
       prev_label = from_label;
       aiter->Next();
-      if (!aiter->Done()) aiter_queue_->push(std::move(aiter));
+      if (!aiter->Done()) {
+        aiter_queue_.push_back(std::move(aiter));
+        std::push_heap(aiter_queue_.begin(), aiter_queue_.end(), ArcIterCompare{});
+      }
     }
     P_.FinalizeSplit(&L_);
   }
@@ -298,7 +295,7 @@ class CyclicMinimizer {
   VectorFst<RevArc> Tr_;
   // Priority queue of open arc iterators for all states in the splitter
   // equivalence class.
-  std::unique_ptr<ArcIterQueue> aiter_queue_;
+  ArcIterQueue aiter_queue_;
 };

 // Computes equivalence classes for acyclic FST.