목록힙 (1)

Doby's Lab

[자료구조] 우선순위 큐 (Priority Queue) 개념, C++ STL

우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 배열같은 선형적인 구조로 생각할 수 있다. 하지만, 우선순위 큐는 트리의 관점에서 접근해야 한다. 우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만 이를 사용하지 않는 이유가 있다. 데이터를 삽입하거나 삭제하는 과정에서 배열이나 연결 리스트의 메모리를 밀고 당기는데에서 성능 저하를 일으키기 때문에 일반적으로 힙을 사용하여 구현하기 때문이다. (힙이 트리로 이루어졌기 때문) 그리고, 힙에서 데이터를 삽입하거나 삭제할 때는 시간 복잡도가 O(log N)이다. (+ 힙 정렬이 N개의 데이터를 하나씩 다 빼오기(삭제)..
C++ 2021. 10. 7. 08:03
이전 Prev 1 Next 다음