[자료구조] Heap (힙) - 정의, 예제, 시간복잡도, 장단점

# 자료구조 시리즈

1. Array (배열)
2. Linked List (연결 리스트)
3. Stack
4. Queue
5. Tree (Binary / Segment)
6. Graph
7. Deque
8. Heap
9. Trie

---

자료구조(Data Structure)에서는 자료에 효율적으로 접근하고 수정할 수 있도록, 데이터를 구성하고 저장하는 방법을 공부합니다. 자료구조는 데이터의 형태에 따라 크게 선형과 비선형으로 구분됩니다. 선형 자료구조는 데이터가 일렬로 나열되어 있는 반면, 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다는 것이 핵심입니다. 전자의 예시로는 Array, Linked List, Stack, Queue 등이 있으며 후자에는 Tree, Graph 등이 있습니다.

 

Heap (힙)

---

1. 정의

  Heap(힙)는 노드가 왼쪽부터 차례대로 채워진 Complete Binary Tree(완전 이진 트리)의 일종으로, Priority Queue(우선순위 큐)를 위해 만들어진 자료구조 개념입니다. 최솟값 또는 최댓값을 빠르게 찾기 위해 고안되었으며, 부모 노드의 키 값이 자식 노드의 키 값보다 크냐 작냐에 따라 Max Heap(최대 힙)과 Min Heap(최소 힙)으로 나눌 수 있습니다. 이진 트리에서 중복된 값을 허용하지 않는 것과 다르게, 힙에서는 중복을 허용합니다.

  Priority Queue(우선순위 큐)의 내부 구조는 Heap을 이용하여 구성됩니다. FIFO 원칙을 따르는 Queue와 달리 높은 우선순위의 원소를 꺼냅니다. Deque의 연산과 비슷하게, 예외를 발생시키는 add, remove, element 연산과 항상 값(true, false, null)을 리턴하는 offer, poll, peek 연산이 존재합니다.

---

2. Heap의 시간복잡도

1. 삽입 : O(logN)
 - Heap에 새로운 원소가 삽입되면, 새로운 노드를 Heap의 마지막 노드에 생성합니다.
 - 이후, 노드의 원소값의 대소를 비교하여 노드끼리 swap하여 위치를 찾아줍니다.
 - 비교 노드의 index가 1/2씩 줄기 때문에 시간복잡도는 O(logN)입니다.

2. 삭제 : O(logN)
 - 최대 힙에서 최댓값은 root 노드이므로 삭제 연산 시 root 노드가 삭제됩니다.
 - 마지막 노드를 가져와 힙을 재구성합니다.
 - 삽입과 동일한 과정을 반대로 하는 것이므로 마찬가지로 시간복잡도는 O(logN)입니다.

* 우선순위 큐의 시간복잡도는 O(N*logN)입니다.

 

---

3. Heap의 장단점

  1) 장점

Pros of heap:

• Fast insertion and deletion of elements (the time complexity is O(log n), where n is the number of elements in the heap)
• Supports fast retrieval of the minimum (for a min heap) or maximum (for a max heap) element (the time complexity is O(1))

---

   2) 단점

1. Heap 경합
 - 멀티스레드에서 같은 데이터에 액세스하려고 하면 경합이 일어납니다. 멀티 프로세서 시스템에서 일어나는 대표적인 문제로 메모리 블록을 많이 사용하는 프로그램이나 DLL의 멀티스레딩과 같은 상황에서 발생합니다. Heap 경합으로 스레드와 프로세스의 context 전환 시 리소스 소모 또는 캐싱 데이터 손실의 문제가 생길 수 있습니다.

• No fast random access to the elements in the heap (the time complexity for accessing an arbitrary element in the heap is O(n))
• Uses more memory (compared to a sorted array)

 

 

---

참고자료 
 - https://yoongrammer.tistory.com/80
 - https://opentutorials.org/module/1335/8821 
 - https://gitub.com/Seogeurim/CS-study