[자료구조] 힙(heap) - 1.구조 이해

* 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다.

 

📌힙 (Heap) 이란

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

여기서 완전 이진 트리는 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다.

따라서 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.

완전 이진 트리

 

📌힙을 사용하는 이유

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

하지만 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다.

✔️ 이처럼 최대값 또는 최소값을 빨리 찾아야 하는 자료구조 및 알고리즘 구현에 활용된다.

 

📈 시간 복잡도

배열에 데이터를 넣는 시간 : O(1)

배열에서 최대/최소값을 찾는 시간 : O(n)

힙에 데이터를 넣는시간 : O(logn)

힙에서 최대/최소값을 찾는 시간 : O(1)

 

 

 

 

📌힙의 구조

힙은 두가지 구조가 있다

1. 최대 힙(Max Heap) : 최대값을 구하기 위한 구조

2. 최소 힙(Min Heap) : 최소값을 구하기 위한 구조

이 글에서는 최대 힙을 기준으로 설명할 것이다.

 

✔️힙의 두가지 조건

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

2. 완전 이진 트리 형태

 

 

 

📌힙과 이진 탐색 트리의 공통점과 차이점 

✔️공통점 : 이진 트리

 

✔️차이점

1. 힙 

• 각 노드의 값이 자식 노드보다 크거나 같음 (Max Heap)
• 이진 탐색 트리의 조건인, 자식 노드에서 작은 값은 왼쪽 큰값은 오른쪽 이라는 조건이 없음!
• 힙은 왼쪽 오른쪽중 어떤 값이 큰지 알 수 없고, 오직 부모 노드만 자식보다 큼(또는 같음)

2. 이진 탐색 트리

• 왼쪽 자식 노드의 값이 가장 작고, 오른쪽 자식 노드 값이 가장 큼

✏️이진 탐색 트리는 탐색을 위한 구조

✏️힙은 최대/ 최소값 검색을 위한 구조

 

 

 

 

📌힙 동작 (Max Heap)

✔️힙에 데이터 삽입하기

힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입된다.

 

1. 왼쪽 최하단부 노드에 삽입
2. 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복(swap)

insert

✔️힙에 데이터 삭제하기

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

✏️힙은 root노드로 접근해, 최대 최소값을 바로 쓸 수 있도록 하는게 목적임 => O(1)

1. root 노드를 삭제함
2. 가장 최 하단부 왼쪽에 위치한 노드(가장 마지막에 추가한 노드)를 root 노드로 이동함
3. root노드 값이 child node보다 작은 경우, swap동작을 반복함

delete