diff --git a/quic/core/qpack/qpack_header_table.cc b/quic/core/qpack/qpack_header_table.cc
index bb28f72..30f15a5 100644
--- a/quic/core/qpack/qpack_header_table.cc
+++ b/quic/core/qpack/qpack_header_table.cc
@@ -131,10 +131,13 @@
   }
 
   // Notify and deregister observers whose threshold is met, if any.
-  while (!observers_.empty() &&
-         observers_.top().required_insert_count <= inserted_entry_count()) {
-    Observer* observer = observers_.top().observer;
-    observers_.pop();
+  while (!observers_.empty()) {
+    auto it = observers_.begin();
+    if (it->first > inserted_entry_count()) {
+      break;
+    }
+    Observer* observer = it->second;
+    observers_.erase(it);
     observer->OnInsertCountReachedThreshold();
   }
 
@@ -188,10 +191,10 @@
   max_entries_ = maximum_dynamic_table_capacity / 32;
 }
 
-void QpackHeaderTable::RegisterObserver(Observer* observer,
-                                        uint64_t required_insert_count) {
+void QpackHeaderTable::RegisterObserver(uint64_t required_insert_count,
+                                        Observer* observer) {
   DCHECK_GT(required_insert_count, 0u);
-  observers_.push({observer, required_insert_count});
+  observers_.insert({required_insert_count, observer});
 }
 
 uint64_t QpackHeaderTable::draining_index(float draining_fraction) const {
@@ -219,11 +222,6 @@
   return it->InsertionIndex();
 }
 
-bool QpackHeaderTable::ObserverWithThreshold::operator>(
-    const ObserverWithThreshold& other) const {
-  return required_insert_count > other.required_insert_count;
-}
-
 void QpackHeaderTable::EvictDownToCurrentCapacity() {
   while (dynamic_table_size_ > dynamic_table_capacity_) {
     DCHECK(!dynamic_entries_.empty());
diff --git a/quic/core/qpack/qpack_header_table.h b/quic/core/qpack/qpack_header_table.h
index f251894..919a4eb 100644
--- a/quic/core/qpack/qpack_header_table.h
+++ b/quic/core/qpack/qpack_header_table.h
@@ -96,8 +96,8 @@
 
   // Register an observer to be notified when inserted_entry_count() reaches
   // |required_insert_count|.  After the notification, |observer| automatically
-  // gets unregistered.
-  void RegisterObserver(Observer* observer, uint64_t required_insert_count);
+  // gets unregistered.  Each observer must only be registered at most once.
+  void RegisterObserver(uint64_t required_insert_count, Observer* observer);
 
   // Used on request streams to encode and decode Required Insert Count.
   uint64_t max_entries() const { return max_entries_; }
@@ -179,21 +179,8 @@
   // The number of entries dropped from the dynamic table.
   uint64_t dropped_entry_count_;
 
-  // Data structure to hold an Observer and its threshold.
-  struct ObserverWithThreshold {
-    Observer* observer;
-    uint64_t required_insert_count;
-    bool operator>(const ObserverWithThreshold& other) const;
-  };
-
-  // Use std::greater so that entry with smallest |required_insert_count|
-  // is on top.
-  using ObserverHeap = std::priority_queue<ObserverWithThreshold,
-                                           std::vector<ObserverWithThreshold>,
-                                           std::greater<ObserverWithThreshold>>;
-
-  // Observers waiting to be notified.
-  ObserverHeap observers_;
+  // Observers waiting to be notified, sorted by required insert count.
+  std::multimap<uint64_t, Observer*> observers_;
 };
 
 }  // namespace quic
diff --git a/quic/core/qpack/qpack_header_table_test.cc b/quic/core/qpack/qpack_header_table_test.cc
index 00f36e5..5a97c20 100644
--- a/quic/core/qpack/qpack_header_table_test.cc
+++ b/quic/core/qpack/qpack_header_table_test.cc
@@ -89,9 +89,9 @@
     return table_.SetDynamicTableCapacity(capacity);
   }
 
-  void RegisterObserver(QpackHeaderTable::Observer* observer,
-                        uint64_t required_insert_count) {
-    table_.RegisterObserver(observer, required_insert_count);
+  void RegisterObserver(uint64_t required_insert_count,
+                        QpackHeaderTable::Observer* observer) {
+    table_.RegisterObserver(required_insert_count, observer);
   }
 
   uint64_t max_entries() const { return table_.max_entries(); }
@@ -418,7 +418,7 @@
 
 TEST_F(QpackHeaderTableTest, Observer) {
   StrictMock<MockObserver> observer1;
-  RegisterObserver(&observer1, 1);
+  RegisterObserver(1, &observer1);
   EXPECT_CALL(observer1, OnInsertCountReachedThreshold);
   InsertEntry("foo", "bar");
   EXPECT_EQ(1u, inserted_entry_count());
@@ -427,8 +427,8 @@
   // Registration order does not matter.
   StrictMock<MockObserver> observer2;
   StrictMock<MockObserver> observer3;
-  RegisterObserver(&observer3, 3);
-  RegisterObserver(&observer2, 2);
+  RegisterObserver(3, &observer3);
+  RegisterObserver(2, &observer2);
 
   EXPECT_CALL(observer2, OnInsertCountReachedThreshold);
   InsertEntry("foo", "bar");
@@ -444,8 +444,8 @@
   // notified.
   StrictMock<MockObserver> observer4;
   StrictMock<MockObserver> observer5;
-  RegisterObserver(&observer4, 4);
-  RegisterObserver(&observer5, 4);
+  RegisterObserver(4, &observer4);
+  RegisterObserver(4, &observer5);
 
   EXPECT_CALL(observer4, OnInsertCountReachedThreshold);
   EXPECT_CALL(observer5, OnInsertCountReachedThreshold);
diff --git a/quic/core/qpack/qpack_progressive_decoder.cc b/quic/core/qpack/qpack_progressive_decoder.cc
index 5ce0612..5632286 100644
--- a/quic/core/qpack/qpack_progressive_decoder.cc
+++ b/quic/core/qpack/qpack_progressive_decoder.cc
@@ -295,7 +295,7 @@
       OnError("Limit on number of blocked streams exceeded.");
       return false;
     }
-    header_table_->RegisterObserver(this, required_insert_count_);
+    header_table_->RegisterObserver(required_insert_count_, this);
   }
 
   return true;