diff --git a/src/feerate.h b/src/feerate.h
--- a/src/feerate.h
+++ b/src/feerate.h
@@ -84,6 +84,9 @@
         nSatoshisPerK += a.nSatoshisPerK;
         return *this;
     }
+    CFeeRate operator+(const CFeeRate &a) {
+        return CFeeRate(nSatoshisPerK + a.nSatoshisPerK);
+    }
     std::string ToString() const;
 
     ADD_SERIALIZE_METHODS;
diff --git a/src/policy/fees.h b/src/policy/fees.h
--- a/src/policy/fees.h
+++ b/src/policy/fees.h
@@ -14,26 +14,41 @@
 #include <vector>
 
 class CFeeRate;
+class CTxMemPoolEntry;
+class CTxMemPool;
 
-/** Track confirm delays up to 25 blocks, can't estimate beyond that */
-static const unsigned int MAX_BLOCK_CONFIRMS = 25;
+/** \class MempoolFeeEstimator
+ * The MempoolFeeEstimator is used for estimating the feerate needed for a
+ * transaction to be included in a block within a certain number of blocks.
+ */
+class MempoolFeeEstimator {
+private:
+    std::vector<CFeeRate> m_minHeap;
+    std::vector<CFeeRate> m_maxHeap;
 
-/** Decay of .998 is a half-life of 346 blocks or about 2.4 days */
-static const double DEFAULT_DECAY = .998;
+public:
+    MempoolFeeEstimator() {}
 
-/** Require greater than 95% of X feerate transactions to be confirmed within Y
- * blocks for X to be big enough */
-static const double MIN_SUCCESS_PCT = .95;
+    /**
+     * Clear the state of the curBlock variables to start counting for after a
+     * block is received.
+     */
+    void clear();
 
-/** Require an avg of 1 tx in the combined feerate bucket per block to have stat
- * significance */
-static const double SUFFICIENT_FEETXS = 1;
+    /**
+     * Record a new fee data point in the current block stats
+     */
+    void addFee(CFeeRate fee);
+
+    /**
+     * Calculate a feerate estimate.
+     */
+    CFeeRate estimateMedian();
+};
 
 // Minimum and Maximum values for tracking feerates
 static constexpr Amount MIN_FEERATE(10 * SATOSHI);
 static const Amount MAX_FEERATE(int64_t(1e7) * SATOSHI);
-static const Amount INF_FEERATE(MAX_MONEY);
-static const Amount INF_PRIORITY(int64_t(1e9) * MAX_MONEY);
 
 // We have to lump transactions into buckets based on feerate, but we want to be
 // able to give accurate estimates over a large range of potential feerates.
@@ -41,7 +56,6 @@
 /** Spacing of FeeRate buckets */
 static const double FEE_SPACING = 1.1;
 
-
 class FeeFilterRounder {
 public:
     /** Create new FeeFilterRounder */
diff --git a/src/policy/fees.cpp b/src/policy/fees.cpp
--- a/src/policy/fees.cpp
+++ b/src/policy/fees.cpp
@@ -8,6 +8,51 @@
 
 #include "amount.h"
 #include "feerate.h"
+#include "primitives/transaction.h"
+#include "random.h"
+#include "streams.h"
+#include "txmempool.h"
+#include "util.h"
+
+#include <iostream>
+
+void MempoolFeeEstimator::clear() {
+    m_maxHeap.resize(0);
+    m_minHeap.resize(0);
+}
+
+static bool minComparor(const CFeeRate &a, const CFeeRate &b) {
+    return a < b;
+}
+
+void MempoolFeeEstimator::addFee(CFeeRate fee) {
+    auto maxHeapSize = m_maxHeap.size();
+    auto minHeapSize = m_minHeap.size();
+
+    if (maxHeapSize == 0 || fee <= m_maxHeap.front()) {
+        m_maxHeap.push_back(fee);
+        std::push_heap(m_maxHeap.begin(), m_maxHeap.end());
+    } else if (minHeapSize == 0 || fee <= m_minHeap.front()) {
+        m_minHeap.push_back(fee);
+        std::push_heap(m_minHeap.begin(), m_minHeap.end(), minComparor);
+    } else if (maxHeapSize < minHeapSize) {
+        m_maxHeap.push_back(fee);
+        std::push_heap(m_maxHeap.begin(), m_maxHeap.end(), minComparor);
+    } else {
+        m_minHeap.push_back(fee);
+        std::push_heap(m_minHeap.begin(), m_minHeap.end(), minComparor);
+    }
+}
+
+CFeeRate MempoolFeeEstimator::estimateMedian() {
+    if (m_maxHeap.size() == m_minHeap.size()) {
+        return CFeeRate(
+            (m_minHeap.front().GetFeePerK() + m_maxHeap.front().GetFeePerK()) /
+            2);
+    }
+    std::cout << "interesting" << std::endl;
+    return m_maxHeap.front();
+}
 
 FeeFilterRounder::FeeFilterRounder(const CFeeRate &minIncrementalFee) {
     Amount minFeeLimit = std::max(SATOSHI, minIncrementalFee.GetFeePerK() / 2);
diff --git a/src/test/policyestimator_tests.cpp b/src/test/policyestimator_tests.cpp
--- a/src/test/policyestimator_tests.cpp
+++ b/src/test/policyestimator_tests.cpp
@@ -14,6 +14,25 @@
 
 BOOST_FIXTURE_TEST_SUITE(policyestimator_tests, BasicTestingSetup)
 
+BOOST_AUTO_TEST_CASE(test_MempoolFeeEstimator) {
+    MempoolFeeEstimator estimator;
+    estimator.addFee(CFeeRate(5 * SATOSHI));
+    estimator.addFee(CFeeRate(4 * SATOSHI));
+    estimator.addFee(CFeeRate(1 * SATOSHI));
+    estimator.addFee(CFeeRate(2 * SATOSHI));
+    estimator.addFee(CFeeRate(3 * SATOSHI));
+    BOOST_CHECK_MESSAGE(
+        estimator.estimateMedian() == CFeeRate(3 * SATOSHI),
+        "Median is incorrect: " << estimator.estimateMedian().ToString());
+    estimator.addFee(CFeeRate(4 * SATOSHI));
+    estimator.addFee(CFeeRate(5 * SATOSHI));
+    estimator.addFee(CFeeRate(3 * SATOSHI));
+    estimator.addFee(CFeeRate(3 * SATOSHI));
+    BOOST_CHECK_MESSAGE(
+        estimator.estimateMedian() == CFeeRate(3 * SATOSHI),
+        "Median is incorrect: " << estimator.estimateMedian().ToString());
+}
+
 BOOST_AUTO_TEST_CASE(MempoolMinimumFeeEstimate) {
     CTxMemPool mpool;
     TestMemPoolEntryHelper entry;
diff --git a/src/txmempool.h b/src/txmempool.h
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -354,7 +354,6 @@
 struct mining_score {};
 struct ancestor_score {};
 
-class CBlockPolicyEstimator;
 
 /**
  * Information about a mempool transaction.
diff --git a/src/txmempool.cpp b/src/txmempool.cpp
--- a/src/txmempool.cpp
+++ b/src/txmempool.cpp
@@ -966,6 +966,7 @@
     // do not contain propagated transactions.
     return std::max(GetConfig().GetMinFeePerKB(), GetMinFee(maxMempoolSize));
 }
+
 CFeeRate CTxMemPool::estimateSmartFee(int nBlocks,
                                       int *answerFoundAtBlocks) const {
     if (answerFoundAtBlocks != nullptr) {
diff --git a/src/wallet/fees.h b/src/wallet/fees.h
--- a/src/wallet/fees.h
+++ b/src/wallet/fees.h
@@ -9,7 +9,6 @@
 
 #include "amount.h"
 
-class CBlockPolicyEstimator;
 class CCoinControl;
 class CFeeRate;
 class CTxMemPool;