Heap, Hashmap, Set

Heap

C++에서는 priority_queue를 Heap으로 쓸 수 있다.

struct Node {
    int cost, x, y;
};

struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        return a.cost > b.cost;   // ex) 비용이 작은 게 top에 오도록
    }
};


int main() {
    // 선언
    priority_queue<int> pq; // 최대 힙

    // 추가
    pq.push(1);
    pq.push(2);
    pq.push(3);

    // 가장 큰 값
    pq.top();

    // 삭제
    pq.pop();

    // 작은 게 위로
    priority_queue<int, vector<int>, greater<int>> pq;

    // 내가 원하는 기준으로
    priority_queue<Node, vector<Node>, Cmp> pq;
}

삽입과 삭제에 O(log N), 최대/최소값 조회는 O(1)이 걸린다.
가장 큰 원소 K개를 구하려면, 최소 힙 (greater<int>)를 만든 뒤, 크기가 K가 넘어가면 pop을 해준다.
priority_queue는 queue처럼 직접 모든 원소를 빼는 것이 아니면 순회가 안된다.

 

Hashmap

C++에서는 unordered_map으로 만들 수 있다.

int main()
{
    // 선언
    unordered_map<string, int> mp; // <key, value>

    // 추가
    mp["apple"] = 3;
    mp["banana"] = 5;

    // 값 증가
    mp["apple"]++;

    // 키 확인
    if (mp.count("apple"))
    {

    }

    // 조회
    auto it = mp.find("banana");
    if (it != mp.end()) {
        cout << it->second;
    }

    // 삭제
    mp.erase("apple");

    // 순회
    for (auto &p : mp) 
    {
        cout << p.first << " : " << p.second << "\n";
    }
}

순회는 정렬된 순서가 아니다.
없는 원소에 대해 mp["hello"]를 조회하면 자동으로 추가되니 주의하자.

 

Set

unordered_set으로 중복 없는 원소와 빠른 접근(O(1))이 가능하다.

int main()
{
    // 선언
    unordered_set<int> s;

    // 삽입
    s.insert(10);

    // 확인
    if (s.count(10))
    {

    }

    // 삭제
    s.erase(10);

    // 순회
    for (auto x : s) 
    {
        cout << x << " ";
    }
}

마찬가지로 순회는 랜덤이다.