BinaryHeap.h

Go to the documentation of this file.

 
#ifndef INCLUDE_BINARYHEAP_H_
#define INCLUDE_BINARYHEAP_H_
#include "seqList.h"
 
namespace Queue
{
    template <typename Comparable, class Compare = std::less<Comparable>>
    class BinaryHeap
    {
        // Member types
    public:
        typedef size_t size_type;      
        typedef Comparable value_type; 
        typedef value_type &reference;
        typedef const value_type &const_reference;
 
        // Data members
    protected:
        size_type current_size_;
 
        List::seqList<value_type> array_;
 
        static constexpr Compare comp = Compare{};
 
        // Member functions
    protected:
        void buildHeap();
 
        void percolateDown(size_type hole);
 
        void percolateUp(size_type hole);
 
    public:
        explicit BinaryHeap(size_type capacity = 100, const Compare &comp = Compare{});
 
        explicit BinaryHeap(const List::seqList<value_type> &items, const Compare &comp = Compare{});
 
        ~BinaryHeap() = default;
 
        bool empty() const;
 
        const_reference top() const;
 
        void pop();
 
        void pop(Comparable *minItem);
 
        void push(const_reference x);
 
        void clear();
 
        size_type size() const;
 
        void print_heap(std::ostream &out) const
        {
            for (size_type i = 1; i <= current_size_; ++i)
                out << array_[i] << ", ";
            out << std::endl;
        }
 
        friend std::ostream &operator<<(std::ostream &out, const BinaryHeap &heap)
        {
            heap.print_heap(out);
            return out;
        }
    };
 
    template <typename Comparable, class Compare>
    BinaryHeap<Comparable, Compare>::BinaryHeap(size_type capacity, const Compare &_comp)
        : current_size_{0}, array_(capacity + 1)
    {
    }
 
    template <typename Comparable, class Compare>
    bool BinaryHeap<Comparable, Compare>::empty() const
    {
        return !current_size_;
    }
 
    template <typename Comparable, class Compare>
    typename BinaryHeap<Comparable, Compare>::const_reference BinaryHeap<Comparable, Compare>::top() const
    {
        return array_[1];
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::push(const_reference x)
    {
        size_type hole = ++current_size_;
        array_.push_back(Comparable{}); // 在堆尾建立hole结点, 作为初始候选位置。可能触发doubleSpace
 
        // 向上过滤
        // 若x置于hole（候选位置）中会破坏堆性质，则hole上滤一层
        while (hole > 1 && comp(array_[hole / 2], x))
        {
            array_[hole] = array_[hole / 2];
            hole /= 2;
        }
        array_[hole] = x;
    }
 
    template <typename Comparable, class Compare>
    BinaryHeap<Comparable, Compare>::BinaryHeap(const List::seqList<Comparable> &items, const Compare &_comp)
        : current_size_{items.size()}, array_(items.size() + 11)
    {
        for (size_type i = 0; i < items.size(); ++i)
        {
            array_[i + 1] = items[i];
            array_.resize(items.size() + 1);
        }
        buildHeap();
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::buildHeap()
    {
        for (size_type i = current_size_ / 2; i > 0; --i)
        {
            percolateDown(i);
        }
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::percolateDown(size_type hole)
    {
        auto tmp = std::move(array_[hole]);
        size_type child;
 
        for (; hole * 2 <= current_size_; hole = child)
        {
            // 选出候选位置的优先级最高的child
            child = hole * 2;
            if (child < current_size_ && comp(array_[child], array_[child + 1]))
            {
                ++child;
            }
            // 检查是否违反堆性质，若是则下滤一层
            if (comp(tmp, array_[child]))
            {
                array_[hole] = std::move(array_[child]);
                continue;
            }
            break;
        }
        array_[hole] = std::move(tmp);
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::percolateUp(size_type hole)
    {
        value_type tmp = std::move(array_[hole]);
 
        // 向上过滤
        // 若x置于hole（候选位置）中会破坏堆性质，则hole上滤一层
        while (hole > 1 && comp(array_[hole / 2], tmp))
        {
            array_[hole] = std::move(array_[hole / 2]);
            hole /= 2;
        }
        array_[hole] = std::move(tmp);
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::pop()
    {
        array_[1] = std::move(array_[current_size_--]);
        array_.pop_back();
        percolateDown(1);
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::pop(Comparable *minItem)
    {
        *minItem = std::move(array_[1]);
        array_[1] = std::move(array_[current_size_--]);
        array_.pop_back();
        percolateDown(1);
    }
 
    template <typename Comparable, class Compare>
    void BinaryHeap<Comparable, Compare>::clear()
    {
        array_.clear();
        current_size_ = 0;
    }
 
    template <typename Comparable, class Compare>
    typename BinaryHeap<Comparable, Compare>::size_type BinaryHeap<Comparable, Compare>::size() const
    {
        return array_.size();
    }
 
} // namespace Queue
 
#endif /* INCLUDE_BINARYHEAP_H_ */