[자료구조] Heap에 대해 알아보고 구현해보기 (Swift)

Heap이란?

Heap은 트리를 사용하고, 트리 중 에서도 완전이진트리를 기본으로 한 자료구조입니다.
주로 최솟값과 최댓값을 빠르게 찾기 위해서 사용하는데,
루트노드를 최댓값으로 사용하면 최대힙이되고, 최소값으로 사용하면 최소힙이 됩니다.

시간 복잡도

• 삽입 : $O(log_n)$
• 삭제 : $O(log_n)$

구현

array를 사용하여 구현하고, 값을 비교하기 위해 Comparable 프로토콜을 채택한 자료형에 대해서만 요소로 사용할 수 있도록 구현하였습니다.

삽입

1. 완전 이진 트리의 마지막 요소에 삽입 (append 사용)
2. 삽입된 요소를 부모노드와 비교
   1. 최대힙이라면, 부모노드보다 더 크다면 swap
   2. 최소힙이라면, 부모노드보다 더 작다면 swap
3. 루트노드가 될 때 까지 반복

삭제

1. 힙의 루트 노드와 마지막 노드와 swap
2. 마지막 노드 삭제
3. 루트 노드와 자식 노드와 비교
   1. 최대힙이라면, 자식노드보다 더 작다면 swap
   2. 최소힙이라면, 자식노드보다 더 크다면 swap
4. 3번 반복

위의 코드는 최대힙으로 구현을 했는데,
힙을 애초에 생성할 때, 비교 연산자를 클로저로 입력받아 최대힙과 최소힙으로 정해주로독 구현하였습니다.

후기

여러자료들을 참고하여 구현하였는데,
Heap의 동작을 이해하고, 차근차근 구현한다면 금방 구현할 수 있다는.. 근자감이 생겼다..
코딩테스트 환경에서 우선순위큐를 사용할 일이 있을 때도 머릿속으로 떠올려서 풀 수 있지 않을까..?