Heap

Heap이란

우선 순위 큐(Priority Queue)를 위해 만들어진 자료구

우선 순위 큐

• 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다.
• 힙으로 구현하는 것이 가장 효율적이다. 배열 또는 연결 리스트를 이용한다면 O(n) 또는 O(1) 복잡도를 가지게 된다.
  • 삽입 : O(logN)
  • 삭제 : O(logN)

Heap

• 완전 이진트리의 일종
• 여러개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 반정렬 상태
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 힙 트리에서는 중복된 값을 허용

heap의 구현

• 힙을 저장하는 표준적인 자료구조는 배열
• 첫번째 인덱스인 0은 사용하지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
• 힙에서 부모 노드와 자식 노드와의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

힙 삽입

1. 새로운 노드를 힙의 마지막 노드에 삽입
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족 시킨다.

힙 삭제

1. 루트 노드 삭제
2. 루트 노드에 힙의 마지막 노드를 가져온다.
3. 힙을 재구성 → 최대힙의 경우 루트 노드를 자식 노드들과 비교하여 자신 보다 큰 쪽과 교환한다.(자식 노드들 중 더 큰 값과 교환)

참고

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