💡 퀵 접속: cpp.kr/is_heap_until

is_heap_until

C++ 표준 라이브러리의 알고리즘으로, 주어진 범위에서 힙 속성이 깨지는 첫 번째 위치를 찾습니다. 기본적으로 최대 힙을 기준으로 하며, 커스텀 비교 함수를 사용하여 다른 힙 기준으로도 검사할 수 있습니다.

기본 사용법

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {9, 5, 4, 2, 1, 3, 7};
    
    // 힙 속성이 깨지는 첫 번째 위치 찾기
    auto it = std::is_heap_until(v.begin(), v.end());
    
    if (it != v.end()) {
        std::cout << "힙 속성이 깨지는 첫 번째 요소: " << *it << std::endl;
        std::cout << "위치: " << std::distance(v.begin(), it) << std::endl;
    } else {
        std::cout << "전체 범위가 힙입니다." << std::endl;
    }
    
    return 0;
}

실행 결과:

힙 속성이 깨지는 첫 번째 요소: 7
위치: 6

커스텀 비교 함수 사용

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 9, 7};
    
    // 최소 힙 기준으로 힙 속성이 깨지는 첫 번째 위치 찾기
    auto it = std::is_heap_until(v.begin(), v.end(), std::greater<int>());
    
    if (it != v.end()) {
        std::cout << "최소 힙 속성이 깨지는 첫 번째 요소: " << *it << std::endl;
        std::cout << "위치: " << std::distance(v.begin(), it) << std::endl;
    } else {
        std::cout << "전체 범위가 최소 힙입니다." << std::endl;
    }
    
    return 0;
}

실행 결과:

최소 힙 속성이 깨지는 첫 번째 요소: 7
위치: 6

사용자 정의 타입에서 사용

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Person {
    std::string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Charlie", 30},
        {"Bob", 25},
        {"Alice", 20},
        {"David", 15},
        {"Eve", 10},
        {"Frank", 35}  // 힙 속성을 깨는 요소
    };
    
    // 나이 기준으로 힙 속성이 깨지는 첫 번째 위치 찾기
    auto it = std::is_heap_until(people.begin(), people.end());
    
    if (it != people.end()) {
        std::cout << "힙 속성이 깨지는 첫 번째 사람: " << it->name 
                  << " (나이: " << it->age << ")" << std::endl;
        std::cout << "위치: " << std::distance(people.begin(), it) << std::endl;
    } else {
        std::cout << "전체 범위가 힙입니다." << std::endl;
    }
    
    return 0;
}

실행 결과:

힙 속성이 깨지는 첫 번째 사람: Frank (나이: 35)
위치: 5

참고사항

is_heap_until은 algorithm 헤더에 정의되어 있습니다.
기본적으로 < 연산자를 사용하여 비교합니다 (최대 힙).
커스텀 비교 함수를 제공할 수 있습니다.
시간 복잡도는 O(n)입니다 (n은 범위의 크기).
반환된 반복자가 범위의 끝이면 전체 범위가 힙입니다.
힙인지 여부만 확인하려면 is_heap을 사용하세요.

함수	설명
is_heap_until(first, last)	기본 비교 연산자를 사용하여 힙 속성이 깨지는 첫 번째 위치 찾기
is_heap_until(first, last, comp)	커스텀 비교 함수를 사용하여 힙 속성이 깨지는 첫 번째 위치 찾기