[자료구조 공부] 자바스크립트 힙(heap) #9

☘️ 힙(Heap)

우선순위 큐
우선 순위가 높은 요소가 먼저 나가는 큐

힙(Heap)은 우선순위 큐를 구현하기 위한 가장 적합한 자료구조이다.

 

그러면 힙(Heap)은 무엇일까?

힙(Heap)
이진 트리 형태
우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬됨
우선 순위가 높은 요소는 Root에 배치

여기서 우선순위 큐는 자료구조가 아닌 개념이고

힙은 우선순위 큐라는 개념을 구현하기 위한 자료구조이다.

 

만약 우선순위 큐를 힙이 아닌 배열을 사용하면 매번 우선순위에 따라 정렬이 되며,

단지 힙보다 효율이 떨어질 뿐이다.

우선순위 큐 != 힙

 

힙의 특징

우선 순위 먼저 나감

힙은 이진트리 형태로

우선 순위가 가장 높은 요소가 Root에 배치하고 항상 먼저 나간다.

최대 힙, 최소 힙

힙의 종류는 2가지가 있다.

1. 루트 값이 최대 값 - 최대 힙(Max Heap)
2. 루트 값이 최소 값 - 최소 힙(Min Heap)

직접 구현

다른 언어와 달리 자바스크립트는 Heap을 직접 구현해야 한다.

 

☘️ 힙(Heap) 동작 방식

힙은 추가, 삭제가 핵심 로직이다.

힙 요소 추가

힙 요소를 추가할 때에 알고리즘은 다음과 같다.

1. 트리의 가장 마지막 정점에 배치
2. 추가된 요소가 부모 정점보다 우선순위가 높으면 부모 정점과 순서 바꿈
3. 순서를 바꿀 수 없을 때까지 2번 과정을 반복

완전 이진 트리의 높이는 log N 이므로, 힙 요소 추가 알고리즘은 O(log N) 시간복잡도를 가진다.

 

힙 요소 제거

힙 요소를 제거할 때에 알고리즘은 다음과 같으며, 요소 제거는 Root 정점만 가능하다.

1. Root 정점 제거 후, 마지막 정점을 Root에 배치
2. Root 정점의 자식 정점 중, 우선순위가 높은 정점과 바꿈
3. 순서를 바꿀 수 없을 때까지 2번 과정을 반복

완전 이진 트리의 높이는 log N 이므로, 힙 요소 삭제 알고리즘은 O(log N) 시간복잡도를 가진다.

 

☘️ 힙(Heap) 구현 방법

힙을 자바스크립트로 구현하는 방법은 다음과 같다.

힙 요소 추가

힙 요소를 추가하는 방법은 아래 코드와 같다.

실행 결과

힙 요소를 추가하면 자동으로 정렬이 되어,

값이 가장 큰 요소인 70이 Root가 된다. (MaxHeap 이라서 가장 큰 요소가 Root)

그래서 그 다음으로 가장 큰 60과 65는 70(Root)의 자식이 된다.

(편의를 위해 0번 인덱스를 null로 함)

 

힙 요소 삭제

힙 요소를 삭제하는 방법은 아래와 같다.

힙 요소 추가 코드에 힙 요소 삭제 코드를 추가하고,

힙 요소를 삭제하고 heap을 출력하면

heap.pop();
console.log(heap.heap);

Root 값인 70이 사라지고 자식 정점인 60과 65중에 우선순위가 더 큰 65가 Root 가 된 것을 확인할 수 있다.

출력 결과

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript