为何BST的deleteMin性能优于Binary Heap？求技术解答

我基于《Weiss数据结构与算法（C++版）》实现了基础的二叉堆（Binary Heap）和二叉搜索树（BST），在Visual Studio 2022 Release模式下测试deleteMin操作：heap.deleteMin()耗时约0.099s，而bst.remove(bst.findMin())耗时约0.06s，BST性能略优（快约1.5倍）。我原以为堆实现优先队列速度远快于BST，请问这是正常现象还是我的实现存在问题？

测试主函数 #

int main()
{
    BinarySearchTree<int> bst;
    BinaryHeap<int> heap;
    
    std::clock_t start;
    double duration;
    int n = 1000000;
    for (int i = 0; i < n; ++i)
    {
        heap.insert(rand() % 10000000);
        bst.insert(rand() % 10000000);
    }

    start = std::clock();
    for (int i = 0; i < n; ++i)
        //heap.deleteMin(); // 0.099s
        bst.remove(bst.findMin()); // 0.06s
    duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
    std::cout << "time: " << duration << '\n';    
}

BST实现 #

template<typename Comparable>
class BinarySearchTree
{

public:
    BinarySearchTree() 
        : root{nullptr}
    { 
    }
    
    BinarySearchTree(const BinarySearchTree& rhs)
    {
        root = clone(rhs.root); 
    }

    ~BinarySearchTree()
    {
        makeEmpty(root); 
    }

    const Comparable& findMin()const
    {
        return findMin(root)->element;
    }

    const Comparable& findMax()const
    {
        return findMax(root)->element;
    }

    bool contains(const Comparable& x)const
    {
        return contains(x, root);
    }

    void insert(const Comparable& x)
    {
        insert(x, root);
    }

    void remove(const Comparable& x)
    {
        remove(x, root); 
    }

private:
    struct BinaryNode
    {
        Comparable element;
        BinaryNode* left;
        BinaryNode* right;
        BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt)
            : element{theElement}, left{lt}, right{rt}{}
        BinaryNode(const Comparable&& theElement, BinaryNode* lt, BinaryNode* rt)
            : element{ std::move(theElement) }, left{ lt }, right{ rt } {}
    };

    BinaryNode* root; 

    BinaryNode* clone(BinaryNode* t)const
    {
        if (t == nullptr)
            return nullptr;
        else
            return new BinaryNode{ t->element, clone(t->left), clone(t->right) }; 
    }

    bool contains(const Comparable& x, BinaryNode* t)const
    {
        if (t == nullptr)
            return false;
        else if (x < t->element)
            return contains(x, t->left);
        else if (t->element < x)
            return contains(x, t->right);
        else return true; //found
    }

    BinaryNode* findMin(BinaryNode* t) const
    {
        if (t == nullptr)
            return nullptr;
        if (t->left == nullptr)
            return t;
        return findMin(t->left);
    }

    BinaryNode* findMax(BinaryNode* t)const
    {
        if (t == nullptr)
            return nullptr;
        if (t->right == nullptr)
            return t;
        return findMin(t->right); // 此处存在bug，应为findMax
    }

    void insert(const Comparable& x, BinaryNode*& t)
    {
        if (t == nullptr)
            t = new BinaryNode(x, nullptr, nullptr);
        else if (x < t->element)
            insert(x, t->left);
        else if (t->element <= x)
            insert(x, t->right);
        else; // duplicate, do nothing
    }

    void insert(Comparable&& x, BinaryNode*& t)
    {
        if (t == nullptr)
            t = new BinaryNode{ std::move(x),nullptr, nullptr };
        else if (x < t->element)
            insert(std::move(x), t->left);
        else if (t->element <= x)
            insert(std::move(x), t->right);
        else //duplicate, do nothing
            ;
    }

    void remove(const Comparable& x, BinaryNode*& t)
    {
        if (t == nullptr)
            return;
        if (x < t->element)
            remove(x, t->left);
        else if (t->element <= x)
            remove(x, t->right);
        else if (t->left != nullptr && t->right != nullptr) // two children
        {
            t->element = findMin(t->right)->element;
            remove(t->element, t->right);
        }
        else
        {
            BinaryNode* oldNode = t;
            t = (t->left != nullptr) ? t->left : t->right; 
            delete oldNode; 
        }
    }

    void makeEmpty(BinaryNode*& t)
    {
        if (t != nullptr)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = nullptr;
    }

};

二叉堆实现 #

template < typename Comparable>
class BinaryHeap
{
public:
    explicit BinaryHeap(int capacity = 100)
        :arr(capacity), currentSize{0}
    {}

    explicit BinaryHeap(const std::vector<Comparable>& items)
        : arr(items.size() + 10), currentSize{ items.size() }
    {
        for (int i = 0; i < items.size(); ++i)
            arr[i + 1] = items[i];
        buildHeap();
    }
    
    bool isEmpty() const
    {
        return currentSize == 0;
    }
    const Comparable& findMin() const
    {
        return arr[1];
    }
    
    void insert(const Comparable& x)
    {
        if (currentSize == arr.size() - 1)
            arr.resize(arr.size() * 2);
        
        // Percolate up
        int hole = ++currentSize;
        Comparable copy = x;
        
        arr[0] = std::move(copy);
        for (; x < arr[hole / 2]; hole /= 2)
            arr[hole] = std::move(arr[hole / 2]);
        arr[hole] = std::move(arr[0]);
    }

    void insert(Comparable&& x)
    {
        if (currentSize == arr.size() - 1)
            arr.resize(arr.size() * 2);

        // Percolate up
        int hole = ++currentSize;

        arr[0] = std::move(x);
        for (; x < arr[hole / 2]; hole /= 2)
            arr[hole] = std::move(arr[hole / 2]);
        arr[hole] = std::move(arr[0]);
    }
 
     /**
* Remove the minimum item.
* Throws UnderflowException if empty.
*/
    void deleteMin()
    {
        if (isEmpty())
            throw UnderflowException{ };
        
        arr[1] = std::move(arr[currentSize--]);
        percolateDown(1);
    }
    
    /**
    * Remove the minimum item and place it in minItem.
    * Throws UnderflowException if empty.
    */
    void deleteMin(Comparable & minItem)
    {
        if (isEmpty())
            throw UnderflowException{ };
        
        minItem = std::move(arr[1]);
        arr[1] = std::move(arr[currentSize--]);
        percolateDown(1);
    }
    
    void makeEmpty();
    
 private:
    int currentSize; // Number of elements in heap
    std::vector<Comparable> arr; // The heap array
    
    /**
    * Establish heap order property from an arbitrary
    * arrangement of items. Runs in linear time.
    */
    void buildHeap()
    {
        for (int i = currentSize / 2; i > 0; --i)
            percolateDown(i);
    }

    /**
    * Internal method to percolate down in the heap.
    * hole is the index at which the percolate begins.
    */
    void percolateDown(int hole)
    {
        int child;
        Comparable tmp = std::move(arr[hole]);

        for (; hole * 2 <= currentSize; hole = child)
        {
            child = hole * 2;
            if (child != currentSize && arr[child + 1] < arr[child])
                ++child;
            if (arr[child] < tmp)
                arr[hole] = std::move(arr[child]);
            else
                break;
        }
        arr[hole] = std::move(tmp);
    }
};

问题分析 #

一、测试场景的特殊性 #

你的测试是连续删除最小值，这对BST来说是极端友好的场景：

• 每次findMin只需要遍历左子树到底，在随机插入的BST中，初始树高是O(logn)；但连续删除最小值后，左子树会被逐步清空，后续的findMin路径会越来越短，甚至直接返回当前根节点（当左子树为空时），实际访问节点数远小于logn。
• 二叉堆的deleteMin逻辑固定：每次将最后一个元素移到根节点，然后执行percolateDown，这一步的时间复杂度是严格O(logn)，且每次操作都要进行多次元素移动和比较，没有场景优化的空间。

二、实现细节的影响 #

1. BST的操作开销极低：
   • Release模式下编译器会把findMin的递归优化为循环，消除函数调用开销；
   • 连续删除最小值时，被删除的节点左子树必然为空，remove操作直接将右子树接上去，是O(1)的指针操作，整体开销极小。
2. 二叉堆的数组操作开销：
   • 虽然数组是连续内存，缓存友好，但percolateDown过程中需要多次比较左右子节点、移动元素，单次deleteMin的常数因子高于BST在该场景下的操作。以n=1e6为例，堆每次percolateDown平均要进行约20次元素移动和比较，而BST后期的remove(findMin)几乎是O(1)操作。
3. BST的小bug不影响测试：你的BST中findMax函数错误地调用了findMin，但当前测试只用到findMin，所以这个bug不会影响结果。

三、理论复杂度 vs 实际性能 #

理论上，二叉堆和BST的deleteMin都是O(logn)时间复杂度，但常数因子差异巨大：

• 堆的常数因子来自数组元素的移动和多次比较，操作开销稳定；
• BST在连续删最小值的场景下，常数因子被大幅降低，实际运行速度超过堆是正常的。

如果换成随机删除任意元素或插入删除交替进行的场景，堆的性能优势会体现出来：BST的树高可能因删除操作失衡，find和remove的开销会波动；而堆的操作始终保持稳定的O(logn)。

四、结论 #

你的实现基本符合标准，没有影响测试结果的严重bug，这个测试结果是正常的，是特定场景下的表现，不能说明BST在所有优先队列场景下都优于二叉堆。

内容的提问来源于stack exchange，提问作者Russell Butler