0.前言

前几天遇到了一条寻找数组中第k小的题目，可以用STL的std::priority_queue来解决，将前k个元素放到std::priority_queue中，然后比较之后的每个元素和std::priority_queue的栈顶元素，如果元素比栈顶小，就将栈顶弹出，该元素弹入。最后栈顶的元素就是我们要找的结果。我们也可以实现一个简单的priority_queue来做这个工作。

1.简单的实现

namespace data_structure {
    template<typename T,
        typename Container=std::vector<T>,
        typename Compare=std::greater<T>>
    class priority_queue {
    public:
        //contruct an empty priority queue
        priority_queue() {
            data_.push_back(T());
        }
        //push an element into the priority queue
        void push(const T& element) {
            std::size_t curSize = ++heapSize_;
            data_.push_back(element);
            while (curSize != 1 && Compare()(element, data_[curSize / 2])) {
                data_[curSize] = data_[curSize / 2];
                curSize /= 2;
            }
            data_[curSize] = element;
        }
        //delete the first element of the priority queue
        void pop() {
            if (heapSize_ == 0)
                throw std::exception("empty priority queue");
            const T lastEle = data_.back();
            data_.pop_back();
            --heapSize_;
            std::size_t curPos = 1;
            std::size_t child = 2;
            while (child <= heapSize_) {
                if (child < heapSize_ && Compare()(data_[child + 1], data_[child]))
                    ++child;
                if (!(Compare()(data_[child], lastEle)))
                    break;
                data_[curPos] = data_[child];
                curPos = child;
                child *= 2;
            }
            data_[curPos] = lastEle;
        }
        //show the first element of the priority queue
        const T& front()const {
            if (heapSize_ == 0)
                throw std::exception("empty priority queue");
            return data_[1];
        }
        //is priority queue empty
        bool empty()const {
            return heapSize_ == 0;
        }
        //show the size of the priority queue
        std::size_t size() {
            return heapSize_;
        }
    private:
        Container data_;
        std::size_t heapSize_ = 0;
    };
}

这个版本的priority_queue和STL中的接受的参数一样，如果容器要自行指定的话，该容器必须有push_back()和pop_back()两个成员变量。
简单说一下实现原理：
通过一个大根堆或者小根堆来实现，每次插入元素时，与对应的父节点比较，如果你的比较函数为true，那么就与父元素交换，直到结构满足大根堆或者小根堆。每次删除元素时，选择容器中最后一个元素lastEle放到被删除的顶部，然后与对应的左右节点比较，如果该元素满足大根堆或者小根堆，删除完成，否则选择一个能够令这三个元素满足大根堆或者小根堆的元素与lastEle交换，直至所有节点都满足大根堆或者小根堆。
插入和删除的时间复杂度为O(height)，也就是大根堆或者小根堆的高，我们在这里用线性表的方式来描述大根堆和小根堆，他们是完全二叉树，使用线性表的方式描述对于空间没有浪费。
这里为了计算方便，在构造时将容器中的第一个数用class type的default constructor产生的值推送进去，所以如果该class type没有default constructor，你是无法使用这个priority_queue的。