Heap과 Priority Queue

Heap

우선순위 큐에 대해 알아보기 전에, 우선순위 큐를 위하여 만들어진 자료구조인  Heap에 대해 먼저 알아보자.

heap의 특징은 다음과 같다.

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다
  큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
  
  

힙의 종류에는 최소 힙과 최대 힙이 있는데, 최대 힙의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이고, 최소 힙의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리다.

 

우선순위 큐(Priority Queue)

일반적인 큐가 FIFO(First in First Out) 구조인 것과 달리, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조를 말한다.

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하지만 이 중에서 앞서 설명한 힙으로 구현하는 것이 가장 효율적이다.

 

우선순위 큐가 힙으로 구현되는 이유

만일 배열이나 연결리스트로 구현하는 경우,

우선순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지 않다. 그러나 우선순위가 중간인 것이 들어가야 하는 삽입 과정에서는 탐색 과정과, 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 하는 상황이 발생하여 최악의 경우 시간 복잡도는 O(n)이 된다.

 

그러나 우선순위 큐를 힙으로 구현한다고 가정하면,

힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어진다. 즉 삭제나 삽입 모두 최악의 경우에는 O(logn) 의 시간 복잡도를 가지기 때문에, 힙으로 구현 시 시간 복잡도는 삭제 시 O(logn), 삽입 시 O(logn)이다.

이처럼 배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현한다.

 

우선순위 큐의 동작 원리

삽입

 

삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입된다

 

삽입 이후에는 루트 노드까지 거슬러 올라가면서 최대 힙을 구성

추가된 원소 9가 부모 노드보다 크므로 바꿔주고, 바꾼 후 또 그 부모보다 크므로 바꿔주면서 최대 힙을 유지한다

 

삭제

삭제 할 때는 루트 노드를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 옮겨준다

삭제 후 리프 토드까지 내려가면서 최대 힙을 구성 

 

https://velog.io/@april_5/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queue

🌈 자료구조:: 우선순위 큐(Priority Queue)

https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)