우선순위 큐

신춘 시즌이 끝나 다시 개발로 돌아왔다...!

Heap

• 피라미드 모양으로 쌓아 올린 더미
• 항상 가장 위에 있는 것을 우선 꺼내는 구조
• 부모 노드는 자식 노드보다 우선순위가 높음

힙은 트리 기반 자료구조다. 힙은 크게 두 가지로 나뉘는데 Max heap과 Min heap이 있다.

• Max heap : 부모 노드가 항상 자식 노드보다 크거나 같음
• Min heap : 부모 노드가 항상 자식 노드보다 작음 (루트가 전체 노드 중 최소값)

일반적으로 힙은 이진트리로 구현한다.

• 이진트리 : 각각의 부모 노드가 오직 두 개의 자식 노드만 가지는 트리.

힙은 완전 이진트리를 사용한다.

• 완전 이진 트리 : 트리의 가장 아래 층을 제외하고 모든 레벨이 완전히 채워진 트리

즉,

1. 부모 노드는 항상 자식 노드보다 값이 작다
2. 트리의 레벨에 모든 노드가 있어야 다음 레벨이 생성될 수 있다.

두 가지 조건을 지키는 자료구조가 힙(Min heap)이다.

힙은 이진트리지만 배열로도 구현할 수 있는데 아래와 같다.

(출처 : https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9)

why heap

힙은 이진탐색을 하기 때문에 O(logn)이 걸린다. 만약 배열/연결 리스트로 구현하게 되면 선형탐색으로 O(n)의 시간복잡도가 생기는 것에 비해 매우 효율적

Min heap은 항상 최상위 부모 노드에 최소값이 있다. 그래서 최상위 노드만 조회하면 최소 값을 얻을 수 있다. O(1)의 시간복잡도를 가진다. 특성상 우선순위 큐를 구현하는데 최적의 자료구조고 아래와 같은 곳에서 사용이 가능하다.

1. 우선순위 큐 구현
2. 운영체제에서 스케쥴링
3. 다익스트라 알고리즘

Min Heap 구현하기

• 최소값을 꺼내는 삭제는 아래와 같이 진행됨

1. 최상위 노드를 꺼냄
2. 배열 요소가 2개 이상이라면 끝에 있는 노드를 최상위 부모 노드로 만듦
3. 최근 자리가 최상위 부모로 바뀐 노드의 올바른 위치를 찾기 위해 위에서부터 아래로 내려가면서 찾는 함수 heapifyDown 실행

으렵네...

참고

https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9