[자료구조] 힙(Heap)에 대해서 알아보자.

 

오늘은 힙(Heap)에 대해서 알아보는 시간을 갖도록 하겠다.

 

Heap

 

(1) 정의

 - 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

 

* 완전 이진 트리 : 노드를 삽일할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

 

(2) 특징

 - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸린다.

 - 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛)이 걸린다.

 - 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.

 - 최대값 또는 최소값을 구하기 위한 구조로 분류되어있다.

 - 완전 이진 트리 형태를 가진다.

 - 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)

 

 

(3) 이진 탐색 트리와 비교

 1) 공통점

  - 둘 다 이진 트리이다.

 

 2) 차이점

  - 힙은 각 노드의 값이 자식 노드보다 크거나 같다.

  - 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 크다.

  - 힙은 이진 탐색 트리의 조건인 잣기 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없다.

  - 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나이다.

 

 

(4) 기본 동작

 1) 삽입

  - 완전 이진 트리로서, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.

 

 - 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap 기준)

 - 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap)

 

 2) 삭제

  - 보통 삭제는 최상단 노드 (root node)를 삭제하는 것이 일반적이다.

  - 상단의 데이터 삭제시, 최하단부 왼쪽에 위치한 노드를 root 노드로 이동

  - root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함.

 

 

 

(5) 시간 복잡도

 - depth (트리의 높이)를 h라고 표기한다면, n개의 노드를 가지는 heap에 데에터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 ℎ=𝑙𝑜𝑔2𝑛에 가까우므로, 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛)