Heap

[자료구조 및 프로그래밍] 11. 우선순위 큐와 Heap

우선순위 큐 우선순위 큐는 우선순위를 가지는 아이템들을 가지는 큐이다. 일반적인 큐와 마찬가지로 push(), pop() 두가지 기능을 제공하지만, 우선순위 큐는 데이터를 저장할 때 단순히 데이터의 값 뿐만 아니라 데이터의 우선순위를 같이 저장하는 점이 다르다. 그래서 우선순위 큐에는 push(x, p) 와 같은 형태로 데이터를 저장한다. x 는 저장하는 데이터, p 는 저장하는 데이터의 우선순위이다. 그리고 pop을 할 때는 우선순위가 높은 데이터부터 나온다. 우선순위 큐의 구현 우선순위 큐의 개념은 간단하다. 그런데 우선순위 큐의 구현은 간단하지 않다. 만약 일반적인 큐를 구현할 때처럼 연결 리스트를 사용한다면 어떨까? 데이터를 pop 할 때, 우선순위가 높은 순부터 뽑아야 하므로 아래 2가지 방법중..