[자료구조] Priority Queue 우선순위 큐, Heap 힙

Priority Queue 우선순위 큐

들어온 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조

- 우선순위 큐는 heap이라는 자료구조로 구현

 

배열, 연결리스트로 구현하지 않는 이유?

-데이터 삽입 시 시간복잡도가 O(n)에 이르기 때문

-힙을 사용할 시 시간복잡도는 삽입, 삭제 시 모두 O(log2n)

 

Heap 힙

-힙은 완전이진트리

-모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 우선순위가 크거나 같음 (반정렬 상태)

-> 삽입 시 직접 연결된 부모, 자식 간의 우선순위만 비교하면 됨

-중복된 값 허용

 

Max Heap 최대 힙

-완전 이진트리이면서, 루트 노드로 올라갈수록 저장된 값이 커지는 구조

-우선순위는 값이 큰 순서대로 매김

 

Min Heap 최소 힙

-완전 이진트리이면서, 루트 노드로 올라갈수록 값이 작아지는 구조

-우선순위는 값이 작은 순서대로 매김

-최대 힙이던 최소 힙이던 루트 노드에는 우선순위가 높은 것이 자리잡게 됨

 

 

힙의 데이터 저장

 

자식노드를 구하고 싶을 때

-왼쪽 자식노드 index = (부모 노드 index) * 2

-오른쪽 자식노드 index = (부모 노드 index) * 2 + 1

부모노드를 구하고 싶을 때

-부모 노드 index = (자식노드 index) / 2

 

최소 힙에 데이터 삽입

-위와 같은 최소힙에 새로운 데이터가 저장된다고 가정

-제일 먼저, 들어올 새 노드를 ‘우선순위가 가장 낮다는 가정을 하고’ ‘맨 끝 위치’에 저장

-> 맨 끝 위치에 저장한다는 것도 완전 이진트리를 만족하는 틀 안에서 이루어져야 하므로,

    위 그림에서는 새로 들어올 노드가 노드 7의 left Child 로 들어가야 함

-부모 노드와 우선 순위를 비교해서 위치가 바뀌어야 하면 서로 위치를 바꿈

-> 위치가 맞을 때까지 계속 반복

 

-새로 들어올 노드의 값이 3이라고 가정

-힙은 주로 배열로 구현하고 인덱스는 0을 비우고 1부터 시작

 

최소 힙에서 데이터 삭제

-우선순위 큐에서의 pop = 우선순위가 높은 데이터를 빼낸다는 의미

-우선순위 큐의 pop을 힙에 대입해 본다면, 힙의 루트 노드를 반환(삭제) 하는 것

-힙에서 가장 우선순위가 높은 데이터는 루트노드인데, 이 루트 노드를 삭제하면서 힙의 구조를 그대로 유지해야함

 (이렇게 힙의 구조를 유지하는 과정을 heapify라고 함)

 

힙정렬 알고리즘

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨

과정 설명
i. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만들기

 -> 오름차순 정렬을 원할 시 내림차순으로 만듦
ii. 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장
iii. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬됨

 

-출처

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

https://suyeon96.tistory.com/31

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html