💡 퀵 접속: cpp.kr/pop_heap

pop_heap

C++ 표준 라이브러리의 알고리즘으로, 힙의 최대/최소 요소를 힙의 마지막 위치로 이동시키고 나머지 요소들을 힙으로 재구성합니다. 기본적으로 최대 힙을 기준으로 하며, 커스텀 비교 함수를 사용하여 다른 힙 기준으로도 동작할 수 있습니다.

기본 사용법

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};
    
    // 벡터를 힙으로 변환
    std::make_heap(v.begin(), v.end());
    
    // 힙의 최대 요소를 마지막으로 이동
    std::pop_heap(v.begin(), v.end());
    
    // 최대 요소 출력 및 제거
    std::cout << "제거된 최대 요소: " << v.back() << std::endl;
    v.pop_back();
    
    // 남은 힙의 최대 요소 출력
    std::cout << "새로운 최대 요소: " << v.front() << std::endl;
    
    // 전체 힙 출력
    std::cout << "남은 힙의 요소들: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

실행 결과:

제거된 최대 요소: 9
새로운 최대 요소: 5
남은 힙의 요소들: 5 3 4 1 1

커스텀 비교 함수 사용

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9};
    
    // 벡터를 최소 힙으로 변환
    std::make_heap(v.begin(), v.end(), std::greater<int>());
    
    // 힙의 최소 요소를 마지막으로 이동
    std::pop_heap(v.begin(), v.end(), std::greater<int>());
    
    // 최소 요소 출력 및 제거
    std::cout << "제거된 최소 요소: " << v.back() << std::endl;
    v.pop_back();
    
    // 남은 힙의 최소 요소 출력
    std::cout << "새로운 최소 요소: " << v.front() << std::endl;
    
    // 전체 힙 출력
    std::cout << "남은 힙의 요소들: ";
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

실행 결과:

제거된 최소 요소: 1
새로운 최소 요소: 1
남은 힙의 요소들: 1 3 4 5 9

사용자 정의 타입에서 사용

#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 = {
        {"Alice", 20},
        {"Bob", 25},
        {"Charlie", 30},
        {"David", 35}
    };
    
    // 벡터를 힙으로 변환
    std::make_heap(people.begin(), people.end());
    
    // 힙의 최대 요소(가장 나이 많은 사람)를 마지막으로 이동
    std::pop_heap(people.begin(), people.end());
    
    // 최대 요소 출력 및 제거
    std::cout << "제거된 가장 나이 많은 사람: " << people.back().name 
              << " (" << people.back().age << "세)" << std::endl;
    people.pop_back();
    
    // 남은 힙의 최대 요소 출력
    std::cout << "새로운 가장 나이 많은 사람: " << people.front().name 
              << " (" << people.front().age << "세)" << std::endl;
    
    // 전체 힙 출력
    std::cout << "남은 사람들 (나이 순): ";
    for (const auto& person : people) {
        std::cout << person.name << "(" << person.age << "세) ";
    }
    std::cout << std::endl;
    
    return 0;
}

실행 결과:

제거된 가장 나이 많은 사람: David (35세)
새로운 가장 나이 많은 사람: Charlie (30세)
남은 사람들 (나이 순): Charlie(30세) Bob(25세) Alice(20세)

참고사항

  • pop_heap은 algorithm 헤더에 정의되어 있습니다.
  • 기본적으로 < 연산자를 사용하여 비교합니다 (최대 힙).
  • 커스텀 비교 함수를 제공할 수 있습니다.
  • 시간 복잡도는 O(log n)입니다 (n은 힙의 크기).
  • 최대/최소 요소는 힙의 마지막 위치로 이동됩니다.
  • 실제로 요소를 제거하려면 컨테이너의 pop_back()을 호출해야 합니다.
  • 힙에 새 요소를 추가하려면 push_heap을 사용하세요.
함수 설명
pop_heap(first, last) 기본 비교 연산자를 사용하여 최대 요소를 힙의 마지막으로 이동
pop_heap(first, last, comp) 커스텀 비교 함수를 사용하여 최대/최소 요소를 힙의 마지막으로 이동