우선순위 큐는 트리구조로 insertion, pop에 O(lg n)의 시간복잡도를 가지고
최대, 최소값을 찾는데 O(1)의 시간복잡도를 갖는다.
우선순위 큐의 조건은
- 언제나 부모노드는 자식노드보다 크다
- 트리는 왼쪽부터 채워나간다
삽입의 동작 과정은
위와 같은 우선순위 큐가 있을 때 새로운 값 11이 들어오면
맨 끝 자식 노드에 추가한 뒤 부모노드와 비교해 부모노드가 더 작으면 교체하는 방식으로 동작한다.
다음으로 pop의 과정을 보면
위와 같이 우선순위 큐가 있을 때 pop을 하면 최상단 부모노드인 11이 사라지고
맨 오른쪽 끝 자식노드의 값이 그곳으로 들어간다
그 후 자식노드와 비교해 자식노드가 더 크면 그 값과 위치를 바꾼다
c++에서 우선순위 큐는 vector로 구현되어있는데
이렇게 차례대로 인덱스를 정한 뒤 인덱스 순으로 벡터에 넣는다
부모노드를 찾고싶다면
해당 원소의 인덱스 번호에서 위 식을 계산하면 구할 수 있다.
자식노드를 찾고싶다면
위의 식으로 구할 수 있다.
