Priority queue. More...

#include <BinaryHeap.h>

Inheritance diagram for Queue::BinaryHeap< Comparable, Compare >:

Collaboration diagram for Queue::BinaryHeap< Comparable, Compare >:

Public Types
typedef size_t	size_type
	an unsigned integral type More...

typedef Comparable	value_type
	Type of the elements. More...

typedef value_type &	reference

Public Member Functions
	BinaryHeap (size_type capacity=100, const Compare &comp=Compare{})
	Construct a new Binary Heap object. More...

	BinaryHeap (const List::seqList< value_type > &items, const Compare &comp=Compare{})
	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 (Comparable *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...

Public Attributes
const typedef value_type &	const_reference

Protected Member Functions
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
size_type	current_size_
	Number of elements in heap. More...

List::seqList< value_type >	array_
	The heap array. More...

Static Protected Attributes
static constexpr Compare	comp = Compare{}
	function object of type Compare More...

Friends
std::ostream &	operator<< (std::ostream &out, const BinaryHeap &heap)
	将二叉堆中元素顺序插到输出流对象out中. More...

Detailed Description

template<typename Comparable, class Compare = std::less<Comparable>>
class Queue::BinaryHeap< Comparable, Compare >

Priority queue.

Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion.\ This context is similar to a heap, where elements can be inserted at any moment, and only the max heap element can be retrieved (the one at the top in the priority queue).

Template Parameters

Comparable Type of the elements.\ Aliased as member type priority_queue::value_type.

std::less<Comparable> A binary predicate that takes two elements (of type T) as arguments and returns a bool.\ The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.\ The priority_queue uses this function to maintain the elements sorted in a way that preserves heap properties (i.e., that the element popped is the last according to this strict weak ordering).\ This can be a function pointer or a function object, and defaults to less<T>, which returns the same as applying the less-than operator (a<b).\ 即：comp(a, b)返回true，当且仅当b的优先级高于a. 故若comp为less，则为最大堆.

Definition at line 40 of file BinaryHeap.h.

Member Typedef Documentation

◆ reference

template<typename Comparable , class Compare = std::less<Comparable>>

typedef value_type& Queue::BinaryHeap< Comparable, Compare >::reference

Definition at line 46 of file BinaryHeap.h.

◆ size_type

template<typename Comparable , class Compare = std::less<Comparable>>

typedef size_t Queue::BinaryHeap< Comparable, Compare >::size_type

an unsigned integral type

Definition at line 44 of file BinaryHeap.h.

◆ value_type

template<typename Comparable , class Compare = std::less<Comparable>>

typedef Comparable Queue::BinaryHeap< Comparable, Compare >::value_type

Type of the elements.

Definition at line 45 of file BinaryHeap.h.

Constructor & Destructor Documentation

◆ BinaryHeap() [1/2]

template<typename Comparable , class Compare >

Queue::BinaryHeap< Comparable, Compare >::BinaryHeap	(	size_type	capacity = `100`,
		const Compare &	comp = `Compare{}`
	)

explicit

Construct a new Binary Heap object.

Parameters

capacity	容器的初始容量.
comp	函数对象（二元谓词）

数据范围array[1] ~ array[capacity]

Definition at line 203 of file BinaryHeap.h.

◆ BinaryHeap() [2/2]

template<typename Comparable , class Compare >

Queue::BinaryHeap< Comparable, Compare >::BinaryHeap	(	const List::seqList< value_type > &	items,
		const Compare &	comp = `Compare{}`
	)

explicit

Construct a new Binary Heap object.

Parameters

items	容器的初值来源
comp	函数对象（二元谓词）

Definition at line 237 of file BinaryHeap.h.

◆ ~BinaryHeap()

template<typename Comparable , class Compare = std::less<Comparable>>

Queue::BinaryHeap< Comparable, Compare >::~BinaryHeap ( )

default

Destroy the Binary Heap object.

Member Function Documentation

◆ buildHeap()

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::buildHeap

protected

Establish heap order property from an arbitrary arrangement of items.

Note: Run in linear time.

Definition at line 249 of file BinaryHeap.h.

◆ clear()

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::clear

清空队列

Definition at line 315 of file BinaryHeap.h.

◆ empty()

template<typename Comparable , class Compare >

bool Queue::BinaryHeap< Comparable, Compare >::empty

判队空

Returns: true 空; false 非空

Definition at line 209 of file BinaryHeap.h.

◆ percolateDown()

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::percolateDown ( size_type hole )

protected

Internal method to percolate down in the heap.

Parameters

hole	the index at which the percolate begins.

Definition at line 258 of file BinaryHeap.h.

◆ percolateUp()

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::percolateUp ( size_type hole )

protected

Internal method to percolate up in the heap.

Parameters

hole	the index at which the percolate begins.

Definition at line 283 of file BinaryHeap.h.

◆ pop() [1/2]

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::pop

队头元素出队

Definition at line 298 of file BinaryHeap.h.

◆ pop() [2/2]

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::pop ( Comparable * minItem )

队头元素出队，保存在minItem指向的空间中

Parameters

minItem 指向元素类型的指针

Definition at line 306 of file BinaryHeap.h.

◆ print_heap()

template<typename Comparable , class Compare = std::less<Comparable>>

void Queue::BinaryHeap< Comparable, Compare >::print_heap ( std::ostream & out ) const

inline

将二叉堆中元素顺序输出.

Parameters

out	输出流对象，可以是std::cout，或fout等.

Definition at line 181 of file BinaryHeap.h.

Referenced by main().

Here is the caller graph for this function:

◆ push()

template<typename Comparable , class Compare >

void Queue::BinaryHeap< Comparable, Compare >::push ( const_reference x )

将x入队

Parameters

x 新元素

Definition at line 221 of file BinaryHeap.h.

◆ size()

template<typename Comparable , class Compare >

BinaryHeap< Comparable, Compare >::size_type Queue::BinaryHeap< Comparable, Compare >::size

Return size.

Returns the number of elements in the priority_queue.\ This member function effectively calls member size of the underlying container object.

Returns: size_type The number of elements in the underlying container.\ Member type size_type is an unsigned integral type.

Definition at line 322 of file BinaryHeap.h.

Referenced by main().

Here is the caller graph for this function:

◆ top()

template<typename Comparable , class Compare >

BinaryHeap< Comparable, Compare >::const_reference Queue::BinaryHeap< Comparable, Compare >::top

返回队头元素值

Returns: const Comparable& 队头元素（最小）

Definition at line 215 of file BinaryHeap.h.

Referenced by main().

Here is the caller graph for this function:

Friends And Related Function Documentation

◆ operator<<

template<typename Comparable , class Compare = std::less<Comparable>>

std::ostream& operator<<	(	std::ostream &	out,
		const BinaryHeap< Comparable, Compare > &	heap
	)

friend

将二叉堆中元素顺序插到输出流对象out中.

Parameters

out	输出流对象，可以是std::cout，或fout等.
heap	二叉堆对象

Returns: std::ostream& 实参输出流对象的引用

Definition at line 195 of file BinaryHeap.h.

Member Data Documentation

◆ array_

template<typename Comparable , class Compare = std::less<Comparable>>

List::seqList<value_type> Queue::BinaryHeap< Comparable, Compare >::array_

protected

The heap array.

数据范围[1, current_size]

Definition at line 62 of file BinaryHeap.h.

Referenced by Queue::BinaryHeap< int, std::greater< int > >::print_heap().

◆ comp

template<typename Comparable , class Compare = std::less<Comparable>>

constexpr Compare Queue::BinaryHeap< Comparable, Compare >::comp = Compare{}

staticconstexprprotected

function object of type Compare

A binary predicate that takes two elements (of type T) as arguments and returns a bool.\ The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.\ The priority_queue uses this function to maintain the elements sorted in a way that preserves heap properties (i.e., that the element popped is the last according to this strict weak ordering).\ This can be a function pointer or a function object, and defaults to less<T>, which returns the same as applying the less-than operator (a<b).

Definition at line 73 of file BinaryHeap.h.

◆ const_reference

template<typename Comparable , class Compare = std::less<Comparable>>

const typedef value_type& Queue::BinaryHeap< Comparable, Compare >::const_reference

Definition at line 47 of file BinaryHeap.h.

◆ current_size_

template<typename Comparable , class Compare = std::less<Comparable>>

size_type Queue::BinaryHeap< Comparable, Compare >::current_size_

protected

Number of elements in heap.

Definition at line 55 of file BinaryHeap.h.

Referenced by Queue::BinaryHeap< int, std::greater< int > >::print_heap().

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

include/BinaryHeap.h

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Static Protected Attributes

Friends

Detailed Description

template<typename Comparable, class Compare = std::less<Comparable>> class Queue::BinaryHeap< Comparable, Compare >

Member Typedef Documentation

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ BinaryHeap() [1/2]

◆ BinaryHeap() [2/2]

◆ ~BinaryHeap()

Member Function Documentation

◆ buildHeap()

◆ clear()

◆ empty()

◆ percolateDown()

◆ percolateUp()

◆ pop() [1/2]

◆ pop() [2/2]

◆ print_heap()

◆ push()

◆ size()

◆ top()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ array_

◆ comp

◆ const_reference

◆ current_size_

template<typename Comparable, class Compare = std::less<Comparable>>
class Queue::BinaryHeap< Comparable, Compare >