Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Functions
Saf::Algo::Struct::Heap Namespace Reference

The heap data structure and related operations. More...

Functions

template<class RanIter , class Pred >
void BalanceDown (RanIter begin, Diff node, Diff bottom, Pred pred)
 Percolate the element node to the bottom of a heap.
template<class RanIter , class Pred >
void BalanceUp (RanIter begin, Diff top, Diff node, Pred pred)
 Percolate the element node up in the heap if the heap property is not satisfied.
template<class RanIter , class Pred >
bool IsHeap (RanIter begin, RanIter end)
 Check whether the range [begin, end) is a max-heap.
template<class RanIter >
bool IsHeap (RanIter begin, RanIter end)
 Check whether the range [begin, end) is a max-heap.
template<class RanIter , class Pred >
void MakeHeap (RanIter begin, RanIter end, Pred pred)
 Convert the range [begin, end) to a max-heap.
template<class RanIter >
void MakeHeap (RanIter begin, RanIter end)
 Convert the range [begin, end) to a max-heap.
template<class RanIter , class Pred >
void PopHeap (RanIter begin, RanIter end, Pred pred)
 Pop the maximum from a heap.
template<class RanIter , class Pred >
void PopHeap (RanIter begin, RanIter end)
 Pop the maximum from a heap.
template<class RanIter , class Pred >
void PushHeap (RanIter begin, RanIter end, Pred pred)
 Insert a new element to a heap.
template<class RanIter >
void PushHeap (RanIter begin, RanIter end)
 Insert a new element to a heap.
template<class RanIter , class Pred >
void SortHeap (RanIter begin, RanIter end, Pred pred)
 Sort the elements in a heap range [begin, end).
template<class RanIter >
void SortHeap (RanIter begin, RanIter end)
 Sort the elements in a heap range [begin, end).

Detailed Description

The heap data structure and related operations.

Function Documentation

template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::BalanceDown ( RanIter  begin,
Diff  node,
Diff  bottom,
Pred  pred 
) [inline]

Percolate the element node to the bottom of a heap.

The element at index node is moved down to the very bottom of the heap (to a leaf node). In each iteration it exchanges its position with the larger of its two childs.

Parameters:
[in]beginRandom-access iterator to the beginning of the sequence containing the heap (the root element).
[in]nodeThe index of the element to be moved down.
[in]bottomThe index of the element one behind the last element in the heap.
[in]predBinary comparison predicate.
template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::BalanceUp ( RanIter  begin,
Diff  top,
Diff  node,
Pred  pred 
) [inline]

Percolate the element node up in the heap if the heap property is not satisfied.

The element at index node is moved up in the heap while it does not satisfy the heap property, i.e., while pred(begin[node], begin[parent]) == true. The percolation stops at index top.

Parameters:
[in]beginRandom-access iterator to the beginning of the sequence containing the heap (the root element).
[in]topSentinel index, i.e., the root of the subtree in which the operation is performed. The node is not pushed above this element in the heap.
[in]nodeThe index of the element to be moved up.
[in]predBinary comparison predicate.
template<class RanIter , class Pred >
bool Saf::Algo::Struct::Heap::IsHeap ( RanIter  begin,
RanIter  end 
) [inline]

Check whether the range [begin, end) is a max-heap.

For any index i > 0 of element in the range [begin, end) the property !pred(begin[(i - 1) / 2], begin[i]) must be satisfied for the range to be a max-heap.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\mathrm{Distance(begin, end)|}) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
bool Saf::Algo::Struct::Heap::IsHeap ( RanIter  begin,
RanIter  end 
) [inline]

Check whether the range [begin, end) is a max-heap.

For any index i > 0 of element in the range [begin, end) the property begin[(i - 1) / 2] < begin[i] must be satisfied for the range to be a max-heap.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\mathrm{Distance(begin, end)|}) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::MakeHeap ( RanIter  begin,
RanIter  end,
Pred  pred 
) [inline]

Convert the range [begin, end) to a max-heap.

The elements in the range [begin, end) are reordered such that for any index i > 0 in the range it holds that pred(begin[(i - 1) / 2], begin[i]) == false.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\mathrm{end} - \mathrm{begin}) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
void Saf::Algo::Struct::Heap::MakeHeap ( RanIter  begin,
RanIter  end 
) [inline]

Convert the range [begin, end) to a max-heap.

The elements in the range [begin, end) are reordered such that for any index i > 0 in the range it holds that !(begin[(i - 1) / 2] < begin[i]).

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\mathrm{end} - \mathrm{begin}) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::PopHeap ( RanIter  begin,
RanIter  end,
Pred  pred 
) [inline]

Pop the maximum from a heap.

Extracts the maximum from a heap range [begin, end). The maximum is placed at the position end - 1 and the heap property in [begin, end - 1) is restored.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\log(\mathrm{end} - \mathrm{begin})) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
See also:
MakeHeap, PushHeap.
template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::PopHeap ( RanIter  begin,
RanIter  end 
) [inline]

Pop the maximum from a heap.

Extracts the maximum from a heap range [begin, end). The maximum is placed at the position end - 1 and the heap property in [begin, end - 1) is restored.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\log(\mathrm{end} - \mathrm{begin})) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
See also:
MakeHeap, PushHeap.
template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::PushHeap ( RanIter  begin,
RanIter  end,
Pred  pred 
) [inline]

Insert a new element to a heap.

This function inserts a new element into a heap. The inserted element is *(end - 1) and it is assumed that the range [begin, end - 1) is already a heap.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\log(\mathrm{end} - \mathrm{begin})) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
See also:
MakeHeap, PopHeap.
template<class RanIter >
void Saf::Algo::Struct::Heap::PushHeap ( RanIter  begin,
RanIter  end 
) [inline]

Insert a new element to a heap.

This function inserts a new element into a heap. The inserted element is *(end - 1) and it is assumed that the range [begin, end - 1) is already a heap.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(\log(\mathrm{end} - \mathrm{begin})) $
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
See also:
MakeHeap, PopHeap.
template<class RanIter , class Pred >
void Saf::Algo::Struct::Heap::SortHeap ( RanIter  begin,
RanIter  end,
Pred  pred 
) [inline]

Sort the elements in a heap range [begin, end).

Assuming the range [begin, end) is a heap the elements in the range are sorted according to the pred predicate.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{end} - \mathrm{begin} $.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
[in]predBinary comparison predicate.
template<class RanIter >
void Saf::Algo::Struct::Heap::SortHeap ( RanIter  begin,
RanIter  end 
) [inline]

Sort the elements in a heap range [begin, end).

Assuming the range [begin, end) is a heap the elements in the range are sorted in an increasing order.

Properties:

  • Minimum iterator category: Random-access.
  • Worst-case time complexity: $ \mathcal{O}(n \log n) $ where $ n = \mathrm{end} - \mathrm{begin} $.
Parameters:
[in]beginIterator to the beginning of the sequence.
[in]endIterator to the end of the sequence.
Generated on Tue May 8 2012 18:51:21 for Simple Application Framework by   doxygen 1.8.0