第C++BoostHeap使用實例詳解目錄一、說明Boost.Heap二、功能示例

一、說明Boost.Heap

Boost.Heap也可以稱為Boost.PriorityQueue，因為該庫提供了幾個優(yōu)先級隊列。但是，Boost.Heap中的優(yōu)先級隊列與std::priority_queue不同，它支持更多功能。

二、功能示例

示例17.1。使用boost::heap::priority_queue

#includeboost/heap/priority_queue.hpp

#includeiostream

usingnamespaceboost::heap;

intmain()

priority_queueint

pq.push(2);

pq.push(3);

pq.push(1);

for(inti:pq)

std::couti'\n';

priority_queueintpq2;

pq2.push(4);

std::coutstd::boolalpha(pqpq2)'\n';

}

Example17.1

示例17.1使用了boost::heap::priority_queue類，該類在boost/heap/priority_queue.hpp中定義。一般來說，這個類的行為類似于std::priority_queue，除了它允許你迭代元素。迭代中返回的元素順序是隨機的。

boost::heap::priority_queue類型的對象可以相互比較。示例17.1中的比較返回true，因為pq的元素比pq2多。如果兩個隊列具有相同數(shù)量的元素，則將成對比較元素。

示例17.2。使用boost::heap::binomial_heap

#includeboost/heap/binomial_heap.hpp

#includeiostream

usingnamespaceboost::heap;

intmain()

binomial_heapint

bh.push(2);

bh.push(3);

bh.push(1);

binomial_heapintbh2;

bh2.push(4);

bh.merge(bh2);

for(autoit=bh.ordered_begin();it!=bh.ordered_end();++it)

std::cout*it'\n';

std::coutstd::boolalphabh2.empty()'\n';

}

Example17.2

示例17.1使用了boost::heap::priority_queue類，該類在boost/heap/priority_queue.hpp中定義。一般來說，這個類的行為類似于std::priority_queue，除了它允許你迭代元素。迭代中返回的元素順序是隨機的。

boost::heap::priority_queue類型的對象可以相互比較。示例17.1中的比較返回true，因為pq的元素比pq2多。如果兩個隊列具有相同數(shù)量的元素，則將成對比較元素。

示例17.2。使用boost::heap::binomial_heap

示例17.2引入了類boost::heap::binomial_heap。除了允許您按優(yōu)先級順序迭代元素之外，它還允許您合并優(yōu)先級隊列。一個隊列中的元素可以添加到另一個隊列。

示例在隊列bh上調(diào)用merge()。隊列bh2作為參數(shù)傳遞。對merge()的調(diào)用將數(shù)字4從bh2移動到bh。調(diào)用后，bh包含四個數(shù)字，bh2為空。

for循環(huán)在bh上調(diào)用ordered_begin()和ordered_end()。ordered_begin()返回一個從高優(yōu)先級元素迭代到低優(yōu)先級元素的迭代器。因此，示例17.2將數(shù)字4、3、2和1寫入標準輸出。

示例17.3。更改boost::heap::binomial_heap中的元素

#includeboost/heap/binomial_heap.hpp

#includeiostream

usingnamespaceboost::heap;

intmain()

binomial_heapint

autohandle=bh.push(2);

bh.push(3);

bh.push(1);

bh.update(handle,4);

std::coutbh.top()'\n';

}

boost::heap::binomial_heap允許您在元素添加到隊列后更改它們。示例17.3保存了push()返回的句柄，從而可以訪問存儲在bh中的數(shù)字2。

update()是boost::heap::binomial_heap的成員函數(shù)，可以調(diào)用它來更改元素。示例17.3調(diào)用成員函數(shù)將2替換為4。然后，使用top()獲取具有最高優(yōu)先級的元素，現(xiàn)在為4。

除了update()之外，boost::heap::binomial_heap還提供了其他成員函數(shù)來更改元素。如果您事先知道更改是否會導(dǎo)致更高或更低的優(yōu)先級，則可以調(diào)用成員函數(shù)increase()或decrease()。在示例17.3中，對update()的調(diào)用可以替換為對increase()的調(diào)用，因為該數(shù)字從2增加到4。

Boost.Heap提供了額外的優(yōu)先級隊列，