💡 퀵 접속: cpp.kr/is_heap

is_heap

C++ 표준 라이브러리의 알고리즘으로, 주어진 범위가 힙(heap)인지 확인합니다. 기본적으로 최대 힙을 기준으로 하며, 커스텀 비교 함수를 사용하여 다른 힙 기준으로도 검사할 수 있습니다.

기본 사용법

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

int main() {
    std::vector<int> v1 = {9, 5, 4, 2, 1, 3};
    std::vector<int> v2 = {1, 2, 3, 4, 5, 9};
    
    // v1이 힙인지 확인
    bool is_heap1 = std::is_heap(v1.begin(), v1.end());
    std::cout << "v1은 " << (is_heap1 ? "힙입니다." : "힙이 아닙니다.") << std::endl;
    
    // v2가 힙인지 확인
    bool is_heap2 = std::is_heap(v2.begin(), v2.end());
    std::cout << "v2는 " << (is_heap2 ? "힙입니다." : "힙이 아닙니다.") << std::endl;
    
    return 0;
}

실행 결과:

v1은 힙입니다.
v2는 힙이 아닙니다.

커스텀 비교 함수 사용

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 9};
    
    // 최소 힙인지 확인
    bool is_min_heap = std::is_heap(v.begin(), v.end(), std::greater<int>());
    std::cout << "v는 " << (is_min_heap ? "최소 힙입니다." : "최소 힙이 아닙니다.") << std::endl;
    
    return 0;
}

실행 결과:

v는 최소 힙입니다.

사용자 정의 타입에서 사용

#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}
    };
    
    // 나이 기준으로 힙인지 확인
    bool is_heap = std::is_heap(people.begin(), people.end());
    std::cout << "people은 나이 기준으로 " << (is_heap ? "힙입니다." : "힙이 아닙니다.") << std::endl;
    
    return 0;
}

실행 결과:

people은 나이 기준으로 힙입니다.

참고사항

  • is_heap은 algorithm 헤더에 정의되어 있습니다.
  • 기본적으로 < 연산자를 사용하여 비교합니다 (최대 힙).
  • 커스텀 비교 함수를 제공할 수 있습니다.
  • 시간 복잡도는 O(n)입니다 (n은 범위의 크기).
  • 빈 범위나 단일 요소 범위는 항상 힙으로 간주됩니다.
  • 힙이 아닌 첫 번째 위치를 찾으려면 is_heap_until을 사용하세요.
함수 설명
is_heap(first, last) 기본 비교 연산자를 사용하여 범위가 힙인지 확인
is_heap(first, last, comp) 커스텀 비교 함수를 사용하여 범위가 힙인지 확인