#include <adjustable_k_ary_heap.h>

Public Types
using	Aggregate = std::pair<Priority, Index>

using	HeapIndex = Index

Public Member Functions
	AdjustableKAryHeap ()

	AdjustableKAryHeap (const std::vector< Aggregate > &elements, HeapIndex universe_size)

	AdjustableKAryHeap (const std::vector< Index > &indices, const std::vector< Priority > &priorities, HeapIndex universe_size)

void	Clear ()

void	Load (const std::vector< Aggregate > &elements, HeapIndex universe_size)

void	Load (const std::vector< Index > &indices, const std::vector< Priority > &priorities, HeapIndex universe_size)

void	Pop ()

Index	TopIndex () const

Priority	TopPriority () const

HeapIndex	heap_size () const
	Returns the number of elements in the heap.

bool	IsEmpty () const
	True iff the heap is empty.

void	Insert (Aggregate element)
	Insert an element into the heap.

bool	Remove (Index index)

void	Update (Aggregate element)
	Change the value of an element.

bool	Contains (Index index) const
	Checks if the element with index is in the heap.

bool	CheckHeapProperty () const
	Checks that the heap is well-formed.

Detailed Description

template<typename Priority, typename Index, int Arity, bool IsMaxHeap>
class AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. Adjustable k-ary heap for std::pair<Priority, Index> classes containing a priority and an index referring to an array where the relevant data is stored.

The comparator is the default comparator for pairs, i.e. the index is used as a tie-breaker for the priority, thus making the code more repeatable.

Because the class uses indices and vectors, it is much faster than AdjustablePriorityQueue, even in the binary heap case.

k-ary heaps are useful when SiftDown() (aka Decrease) is called more often than Pop() (aka Extract).

Namely, Pop() has a complexity in O(k * log_k (n)), while SiftDown() is in O(log_k(n)), even when k = 2. This explains the small gain.

In the implementation below, k is denoted as Arity.

Definition at line 43 of file adjustable_k_ary_heap.h.

Member Typedef Documentation

◆ Aggregate

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

using AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Aggregate = std::pair<Priority, Index>

Definition at line 45 of file adjustable_k_ary_heap.h.

◆ HeapIndex

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

using AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::HeapIndex = Index

Definition at line 46 of file adjustable_k_ary_heap.h.

Constructor & Destructor Documentation

◆ AdjustableKAryHeap() [1/3]

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::AdjustableKAryHeap ( )

inline

Definition at line 52 of file adjustable_k_ary_heap.h.

◆ AdjustableKAryHeap() [2/3]

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::AdjustableKAryHeap	(	const std::vector< Aggregate > &	elements,
		HeapIndex	universe_size )

inlineexplicit

Construct a k-heap from an existing vector, tracking original indices. universe_size is the maximum possible index in elements.

Definition at line 56 of file adjustable_k_ary_heap.h.

◆ AdjustableKAryHeap() [3/3]

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::AdjustableKAryHeap	(	const std::vector< Index > &	indices,
		const std::vector< Priority > &	priorities,
		HeapIndex	universe_size )

inlineexplicit

Definition at line 61 of file adjustable_k_ary_heap.h.

Member Function Documentation

◆ CheckHeapProperty()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

bool AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::CheckHeapProperty ( ) const

inline

Checks that the heap is well-formed.

Definition at line 174 of file adjustable_k_ary_heap.h.

◆ Clear()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

void AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Clear ( )

inline

Definition at line 67 of file adjustable_k_ary_heap.h.

◆ Contains()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

bool AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Contains ( Index index ) const

inline

Checks if the element with index is in the heap.

Definition at line 169 of file adjustable_k_ary_heap.h.

◆ heap_size()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

HeapIndex AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::heap_size ( ) const

inline

Returns the number of elements in the heap.

Definition at line 122 of file adjustable_k_ary_heap.h.

◆ Insert()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

void AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Insert ( Aggregate element )

inline

Insert an element into the heap.

Definition at line 128 of file adjustable_k_ary_heap.h.

◆ IsEmpty()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

bool AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::IsEmpty ( ) const

inline

True iff the heap is empty.

Definition at line 125 of file adjustable_k_ary_heap.h.

◆ Load() [1/2]

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

void AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Load	(	const std::vector< Aggregate > &	elements,
		HeapIndex	universe_size )

inline

Definition at line 73 of file adjustable_k_ary_heap.h.

◆ Load() [2/2]

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

void AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Load	(	const std::vector< Index > &	indices,
		const std::vector< Priority > &	priorities,
		HeapIndex	universe_size )

inline

Definition at line 84 of file adjustable_k_ary_heap.h.

◆ Pop()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

void AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Pop ( )

inline

Removes the top element from the heap (smallest for min-heap, largest for max-heap), and rearranges the heap. This will CHECK-fail if the heap is empty (through Top()).

Definition at line 99 of file adjustable_k_ary_heap.h.

◆ Remove()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

bool AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Remove ( Index index )

inline

Removes the element at index. Returns false if the element does not appear in the heap.

Definition at line 147 of file adjustable_k_ary_heap.h.

◆ TopIndex()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

Index AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::TopIndex ( ) const

inline

Returns the index of the top element, without modifying the heap.

Note: this does not remove the element from the heap, Pop() must be called explicitly.

Definition at line 107 of file adjustable_k_ary_heap.h.

◆ TopPriority()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

Priority AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::TopPriority ( ) const

inline

Returns the index of the top element, without modifying the heap.

Note: this does not remove the element from the heap, Pop() must be called explicitly.

Definition at line 116 of file adjustable_k_ary_heap.h.

◆ Update()

template<typename Priority , typename Index , int Arity, bool IsMaxHeap>

void AdjustableKAryHeap< Priority, Index, Arity, IsMaxHeap >::Update ( Aggregate element )

inline

Change the value of an element.

Definition at line 155 of file adjustable_k_ary_heap.h.

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

ortools/algorithms/adjustable_k_ary_heap.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ Aggregate

◆ HeapIndex

Constructor & Destructor Documentation

◆ AdjustableKAryHeap() [1/3]

◆ AdjustableKAryHeap() [2/3]

◆ AdjustableKAryHeap() [3/3]

Member Function Documentation

◆ CheckHeapProperty()

◆ Clear()

◆ Contains()

◆ heap_size()

◆ Insert()

◆ IsEmpty()

◆ Load() [1/2]

◆ Load() [2/2]

◆ Pop()

◆ Remove()

◆ TopIndex()

◆ TopPriority()

◆ Update()