priority_queue优先队列容器

priority_queue优先队列容器

一、原理

    优先队列也是一种从一端入队,另一端出队的队列。不同于一般队列的是,队列中最大的元素总是位于队首位置,因此总是将当前队列中的最大元素出队。 

    C++ STL优先队列的泛化,底层默认采用vector向量容器,使得队列容器的元素可做数组操作,从而应用堆算法找出当前队列最大元素,并将它调整到队首位置,确保最大元素先出队。(堆算法(heap algorithm)具有nlog(n)阶的算法时间复杂度)。优先队列可看作容器适配器,将底层的序列容器vector转换为优先队列priortity_queue。

二、应用

仅需取队首和队尾元素的操作,因此priority_queue优先队列容器不提供迭代器。

1、创建

(1)priority_queue() 

默认的构造函数,创建一个空的 priority_queue 对象。

priority_queue pq;//使用默认的vector为底层容器,创建了一个空的优先队列对象pq,数据元素为int类型。

(2)priority_queue(const priority_queue&) 

复制构造函数,用一个优先队列对象创建新的优先队列对象。

//priority_queue > pq1; 

priority_queue > pq2(pq1); //利用priority_queue对象pq1,创建一个以双向链表为底层容器的priority_queue对象pq2。

2、入队和出队

void push(const value_type& x) //插入,入队

void pop() //出队,删除队首元素

3、取队首元素

const value_type& top() const //。这个函数实际是调用了底层容器的front函数。读取优先队列的队首元素。

4、其它

1)bool empty()//判断是否为空

2)size_type size()//返回优先队列的当前元素个数。 

注意:要包含的头文件也是queue.

你可能感兴趣的