[자료구조] 힙(Heap) 이란 뭘까?

 

힙(Heap) 이란?

 

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

 

• 우선순위 큐를 위해 만들어진 자료구조 이기도 하다
• 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 반정렬 성태를 유지 -> 부무 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작다
• 이진 탐색 트리와는 다르게 중복된 값이 허용 된다

 

종류

• 최대 힙 (max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)
• 최소 힙 (min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) <= key(자식 노드)

최대 힙 (max heap)

최소 힙 (min heap)

 

💡 왜 사용할까?

• 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 반복문을 한번 돌려서 O(n) 만큼 시간이 걸린다
• 힙을 사용하면 O(logn)이 걸리므로 더 빠르게 구할 수 있다

 

💡 완전 이진 트리는 무엇 일까?

• 이진 트리에 노드를 삽입할 때는 왼쪽부터 차례대로 삽입한다
• 그래서 완전 이진트리는 왼쪽 노드가 없으면 오른쪽 노드도 없어야한다 
• 만약 왼쪽 노드가 비어있고 오른쪽 노드가 있으면 그냥 이진트리라고 한다

 

힙과 이진 탐색 트리

일단 이진탐색 트리는 무엇일까? (Binary Search Tree)

 

• 이진 탐색과 연결리스트를 결합한 자료구조의 일종이다 
• 왼쪽 자식 노드는 부모 노드보다 작은 값으로 오른쪽 자식 노드는 부모 노드보다 큰 값으로 이루어져 있다

 

힙 vs 이진 탐색 트리

• 일단 둘다 완전 이진 트리이다

 

차이점은 

• 힙은 부모 노드가 자식노드 보다 크거나 같고 작거나 같아야한다
• 이진 탐색트리는 부모 노드가 왼쪽 자식 노드보다 커야하고 오른쪽 자식노드보다 작아야 한다 
• 힙은 왼쪽, 오른쪽 자식 노드의 값이 크거나 작거나 상관없다
• 힙은 최대, 최소 겁색을 위한 것
• 이진 탐색 트리는 탐색을 위한 것

 

동작

힙의 삽입 

1. 우선 힙에 데이터를 넣으면 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다
2. 새로운 노드를 부모 노드들과 비교해서 swap 하거나 하지 않는다 -> 이런 동작을 하여 힙의 성질을 만족

최대 힙(max heap) 데이터 삽입 과정

 

위 그림을 보면

1. 우선 5를 삽입한다 
2. 7를 일단 제일 하단 부분에 이어서 삽입을 한다
3. 7의 부모노드인 5와 비교를 한다 비교를 했을때 최대 힙이므로 7이 더 크니까 둘이 swap한다
4. 4를 삽입한다 그리고 부모노드와 비교를 했을때 7이 더 크므로 그대로 둔다 

 

 

힙의 삭제

1. 일단 힙은 최대값과 최솟값을 알아내는게 목적이다
2. 그래서 최댓값 아니면 최솟값이 루트 노드가 삭제가 된다
3. 삭제가 된 후 가장 마지막 노드를 가져와서 루트 노드 자리에 둔다
4. 그 후에 힙을 재구성 한다

최대 힙(max heap) 데이터 삭제 과정

 

위 그림을 보면

1. 우선 루트 노드인 7를 삭제한다
2. 마지막 노드인 4를 루트 노드 자리로 가져온다
3. 그 후에 5와 4를 비교해서 힙을 재구성한다