Queue::priority_queue_int Class Reference

基于最小堆的整型的优先级队列类 More...

Inheritance diagram for Queue::priority_queue_int:

Collaboration diagram for Queue::priority_queue_int:

Public Member Functions
	priority_queue_int (const List::seqList< value_type > &items)
size_type	findMin (value_type x) const
	找出优先级值大于等于指定值x的最小元素，返回其下标 More...
void	decreaseKey (size_type i, value_type value)
	将第i个结点的优先级值减小value More...
void	increaseKey (size_type i, value_type value)
	将第i个结点的优先级值增加value More...
Public Member Functions inherited from Queue::BinaryHeap< int, std::greater< int > >
	BinaryHeap (size_type capacity=100, const std::greater< int > &comp=std::greater< int > {})
	Construct a new Binary Heap object. More...
	BinaryHeap (const List::seqList< value_type > &items, const std::greater< int > &comp=std::greater< int > {})
	Construct a new Binary Heap object. More...
	~BinaryHeap ()=default
	Destroy the Binary Heap object. More...
bool	empty () const
	判队空 More...
const_reference	top () const
	返回队头元素值 More...
void	pop ()
	队头元素出队 More...
void	pop (int *minItem)
	队头元素出队，保存在minItem指向的空间中 More...
void	push (const_reference x)
	将x入队 More...
void	clear ()
	清空队列 More...
size_type	size () const
	Return size. More...
void	print_heap (std::ostream &out) const
	将二叉堆中元素顺序输出. More...

Additional Inherited Members
Public Types inherited from Queue::BinaryHeap< int, std::greater< int > >
typedef size_t	size_type
	an unsigned integral type More...
typedef int	value_type
	Type of the elements. More...
typedef value_type &	reference
Public Attributes inherited from Queue::BinaryHeap< int, std::greater< int > >
const typedef value_type &	const_reference
Protected Member Functions inherited from Queue::BinaryHeap< int, std::greater< int > >
void	buildHeap ()
	Establish heap order property from an arbitrary arrangement of items. More...
void	percolateDown (size_type hole)
	Internal method to percolate down in the heap. More...
void	percolateUp (size_type hole)
	Internal method to percolate up in the heap. More...
Protected Attributes inherited from Queue::BinaryHeap< int, std::greater< int > >
size_type	current_size_
	Number of elements in heap. More...
List::seqList< value_type >	array_
	The heap array. More...
Static Protected Attributes inherited from Queue::BinaryHeap< int, std::greater< int > >
static constexpr std::greater< int >	comp
	function object of type Compare More...

Detailed Description

基于最小堆的整型的优先级队列类

Definition at line 28 of file ch7_7.cc.

Constructor & Destructor Documentation

priority_queue_int()

Queue::priority_queue_int::priority_queue_int ( const List::seqList< value_type > &  items )

inline

Definition at line 31 of file ch7_7.cc.

Member Function Documentation

decreaseKey()

void Queue::priority_queue_int::decreaseKey	(	size_type	i,
		value_type	value
	)

将第i个结点的优先级值减小value

Parameters

i	目标元素的下标
value	优先级值的减小量

Definition at line 187 of file ch7_7.cc.

findMin()

Queue::priority_queue_int::size_type Queue::priority_queue_int::findMin

(

value_type

x

)

const

找出优先级值大于等于指定值x的最小元素，返回其下标

Parameters

x

指定值x

Returns

int 大于等于指定值x的最小元素的下标，0表示查找失败

Definition at line 172 of file ch7_7.cc.

References Queue::BinaryHeap< int, std::greater< int > >::array_, and Queue::BinaryHeap< int, std::greater< int > >::current_size_.

Referenced by main().

Here is the caller graph for this function:

increaseKey()

void Queue::priority_queue_int::increaseKey	(	size_type	i,
		value_type	value
	)

将第i个结点的优先级值增加value

Parameters

i	目标元素的下标
value	优先级值的增加量

Definition at line 199 of file ch7_7.cc.

Referenced by main().

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• src/ch7_7.cc