c++ stl heap 기록

stl의 heap 기능을 활용해서 임의의 벡터를 힙 구조로 변경해 줄 수 있다.

std::make_heap(first iter, last iter)를 활용해서 벡터를 힙으로 변경 가능하다. (시간복잡도 : O(N))

std::pop_heap(first iter, last iter)를 활용해서 벡터의 최댓값을 맨 아래로 정렬 가능하다. (시간복잡도 : O(LogN)

vector.pop_back()을 활용해서 맨 아래 있는 원소를 제거 가능하다.

vector.emplace_back(element)를 활용해서 힙에 원소를 넣어줄 수 있다.

std::push_heap(first iter, last iter)을 사용하면 emplace_back으로 넣은 원소가 포함된 벡터를

힙으로 바꿔줄 수 있다. 

 

코드 >>

#include <iostream>
#include <queue>
 
int main()
{
    std::cout << "Max heap:\n";
    std::vector<int> v{ 1,3,5,7,9,11 };
    std::cout << "initially, v: ";
    for (auto i : v)
    {
        std::cout << i << ' ';
 
    }
    std::cout << '\n';
 
    // Heap으로 바꾼다.
    //Time complexity O(n)
    std::make_heap(v.begin(), v.end()); // {11,9,5,7,3,1}, time_complexity O(N)
    for (auto i : v)
    {
        std::cout << i << ' ';
 
    }
    std::cout << std::endl;
 
    std::pop_heap(v.begin(), v.end()); // 원소를 제거하지 않고 트리만 만듦 O(logn)
    std::cout << "after pop_heap, v:" << std::endl; // {9,7,5,1,3,11}
    for (auto i : v)
    {
        std::cout << i << ' ';
 
    }
    std::cout << std::endl;
    
    v.pop_back();
    std::cout << "After pop back : " << std::endl;
    for (auto i : v)
    {
        std::cout << i << ' ';
 
    }
    std::cout << std::endl;
    
    v.emplace_back(10);
    std::cout << "After emplace back : " << std::endl;
    for (auto i : v)
    {
        std::cout << i << ' ';
 
    }
    std::cout << std::endl;
 
 
    std::push_heap(v.begin(), v.end()); // O(logn)
    std::cout << "After push_heap : " << std::endl;
    for (auto i : v)
    {
        std::cout << i << ' ';
 
    }
    std::cout << std::endl;
    return 0;
}