힙 알고리즘에 대하여

힙 알고리즘

• 힙 트리 구조를 이용하는 정렬 방법

힙(Heap)이란?

• 완전 이진 트리의 종류로서 우선순위 큐를 위하여 만들어진 자료구조 입니다.
  • 이진 트리란?
    1. 데이터를 각 노드에 담은 뒤에 노드를 두개씩 이어 붙이는 구조를 말합니다.
    2. 즉 모든 노드의 자식 노드가 2개 이하인 노드입니다.
  • 완전 이진 트리?
    1. 데이터가 루트 노드부터 시작해서 자식 노드가 왼쪽 부터 순서대로 들어가는 이진트리를 말합니다.
    2. 즉 중간에 노드들이 비어있지 않고 가득 차 있는 구조로 되어 있습니다.
• 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 입니다.
• 즉 최솟값이나 최댓값을 빠르게 찾아내기 위한 완전 이진트리를 기반하는 트리입니다.
• 시간 복잡도는 O(logN) 입니다.
• 힙 트리에서는 중복된 값을 허용합니다.
  • 이진 탐색 트리는 중복 값 허용 X

완전 이진트리 vs 아닌 트리

• 왼쪽부터 차곡히 쌓인 이진트리를 완전 이진트리

• 그렇지 않은 경우 아닌 트리

  

• 완전 이진 트리의 부모노드와 자식 노드와의 관계

  1. 부모노드의 인덱스 번호 = (자식 노드 인덱스 번호) / 2
  2. 왼쪽 자식의 인덱스 = (부모 노드 인덱스 번호) * 2
  3. 오른쪽 자식의 인덱스 = (부모 노드 인덱스 번호) * 2 + 1

우선 순위 큐

• 우선순위의 개념을 큐에 도입한 자료 구조 입니다.
• 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터를 먼저 뽑습니다.
• 배열, 연결리스트, 힙으로 구현이 가능한데 대부분 힙으로 구현합니다.

힙의 종류

• 다음과 같이 2개가 있습니다.

1. 최대 힙(Max)
   • 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진트리
2. 최소 힙(Min)
   • 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진트리

Heap의 구현 방법

• 힙을 저장하는 표준적인 자료구조는 배열입니다.
• 노드들의 번호는 바뀌지 않습니다.

삽입

1. 모든 삽입은 맨 마지막 노드에 들어갑니다.
2. 그 뒤 노드들을 하나씩 거치며 부모 노드 값을 비교해 Max/Min 규칙에 맞게 자리를 찾습니다.

 

 

삭제

1. 모든 삭제는 최상위 노드, 즉 루트 노드에서 삭제됩니다.
2. 그 뒤, 맨 마지막 노드 값을 최상의 노드 값으로 채웁니다.
3. 그 후, 아래로 내려가며 Min/Max 규칙에 맞게 자리를 찾습니다.

 

 

 

시간 복잡도 비교

• 단순 하지만 효과적이지 않는 방법 - 삽입, 선택, 버블 정렬
• 복잡 하지만 효과적인 방법 - 퀵, 힙, 합병 정렬

참고

1. 자세한 내용을 알고 싶으면 여길 참고해 주시길 바랍니다. - 힙 정렬(heap sort) 이란?