Algorithm - is_heap_until()

원형)

//기본형
template <class RandomAccessIterator>
  RandomAccessIterator is_heap_until (RandomAccessIterator first,
                                      RandomAccessIterator last);
 
//사용자 정의형
template <class RandomAccessIterator, class Compare>
  RandomAccessIterator is_heap_until (RandomAccessIterator first,
                                      RandomAccessIterator last
                                      Compare comp);

의미)

[Iterator first, Iterator last)사이에 있는 데이터들이 최대힙으로 정렬되어있다고 생각했을 때 올바른 위치에 있지 않은 원소중 가장 처음에 발견되는 원소를 가리키는 Iterator를 리턴합니다.

소스)

#include<iostream>
#include<algorithm>
#include<vector>
 
void Print(const std::vector<int>& target)
{
    for (std::vector<int>::const_iterator iterPos = target.cbegin(); iterPos != target.cend(); iterPos++)
        std::cout << *iterPos << " ";
    std::cout << std::endl;
}
 
void main()
{
    std::vector<int> vector = { 10,5,20,15,30 };
    Print(vector);
    std::make_heap(vector.begin(), vector.end());
    Print(vector);
 
    std::vector<int>::iterator iter = std::is_heap_until(vector.begin(), vector.end());
    if (iter != vector.end())
        std::cout << *iter << std::endl;
    
    vector.push_back(99);
    Print(vector);
    iter = std::is_heap_until(vector.begin(), vector.end());
    if (iter != vector.end())
        std::cout << *iter << std::endl;
 
    vector.insert(vector.begin(), 6);
    Print(vector);
    iter = std::is_heap_until(vector.begin(), vector.end());
    if (iter != vector.end())
        std::cout << *iter << std::endl;
}
 

리턴값)

가장 처음으로 발견한 최대 힙에서의 바르지 않은 위치에 있는 데이터를 가리키는 Iterator를 리턴합니다. 모든 데이터들이 최대 힙으로 정렬이 되어있거나 2개 미만의 데이터를 가지고 있는 경우 Iterator last를 리턴합니다.

결과)