힙(heap)

개념

• 자료구조 힙(heap)은 완전 이진 트리(이진트리이면서 자식 노드가 빠짐없이 모두 달린 것).
• 우선순위 큐 자료구조를 위해 만들어진 자료형으로 최소, 최대 값을 빠르게 찾기 위함.

종류

• 종류는 최대힙, 최소힙 두가지가 있다.

최대힙	최소힙
부모노드가 가진 값이 자식노드가 가진 값보다 크거나 같음	부모노드가 가진 값이 자식노드가 가진 값보다 작거나 같음

형식

• 힙은 배열 형식으로 나타낼 수 있다.
  배열의 0번은 사용하지 않으며 루트 노드가 1, 왼쪽 자식노드는 2, 오른쪽 자식노드는 3 ... 이렇게 쭉쭉 나아간다.
• 인덱스 계산
  왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2
  오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
  부모 노드 인덱스 = 자식 노드 인덱스 / 2

삽입 방법

1. 배열의 마지막에 삽입.
2. 최대힙이라면 부모노드가 자식노드보다 크도록, 최소힙이라면 부모노드가 자식노드보다 작도록 하는 성질을 만족하며 새로 들어온 노드와 부모노드의 비교를 통해서 자리를 변경한다.

삭제 방법

1. 최대 힙은 최댓값을 삭제하는 것, 최소 힙은 최솟값을 삭제하는 것이므로 루트 노드(1번 인덱스 값)를 삭제한다.
2. 마지막 노드(마지막 인덱스 값)를 루트 노드에 넣는다.
3. 성질을 만족하며 각 노드들과 비교하며 자리를 변경한다. (자식 노드와 비교 시, 오른쪽 왼쪽 자식 노드 중 더 크거나(최대힙) 더 작은(최소힙) 것과 변경한다.

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

위 게시물을 참고하였습니다.