자료구조 힙(Heap)

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조

Heap

힙 정렬 알고리즘의 개념

• *최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법*
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
• 과정 설명 (내림차순 정렬 기준 설명)

  1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.

     → 주어진 트리, 즉 배열을 뒤에서 부터 부모보다 자식이 더 큰 경우 변경(반복) → 최대 힙

  2. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.

     1. 힙 트리(배열) 루트에 있는 요소를 꺼내서 새로운 배열에 저장하고
     2. 힙 트리(배열) 맨 뒤에 있는 노드와 루트를 변경한 뒤 맨 뒤의 요소는 삭제한다.
     3. 힙 트리(배열)를 루트에서 부터 부모의 자식 중에서 가장 큰 값과 변경한다. (모든 노드 수행)
     4. 위 과정을 반복 (힙 트리의 노드가 없어질 때 까지 반복) - 재귀

<aside> 💡

힙 트리(이진 트리)에서 부모와 자식간의 값 변경 방법 부모 노드의 인덱스 = 자식 노드 인덱스 / 2 왼쪽 자식 노드의 인덱스 = 부모 노드 인덱스 * 2 오른쪽 자식 노드의 인덱스 = 부모 노드 인덱스 * 2 + 1

</aside>

알고리즘 팁

<aside> 💡 주로 우선순위 큐와 BFS(while, if-else)를 묶은 형태의 알고리즘으로 작성하면 된다.

</aside>

ref: https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

ref: https://m.blog.naver.com/ndb796/221228342808