자료구조 공부 #1 Heap

Heap

• 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료 구조
• 여러 값 중 최댓값과 최솟값을 빠르게 찾을 수 있음
• 느슨한 정렬상태를 유지

종류

최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
최소 힙 : 부모 노드의 키 값이 자식 노트의 키 값보다 작거나 같은 완전 이진 트리

구현

• 힙을 저장하는 표준 자료 구조는 배열
• 구현의 편의를 위해 첫 index 0은 사용되지 않음
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않음
  ex) 루트 노드의 오른쪽 자식 노드는 항상 index가 3
• 부모 노드와 자식 노드 간의 인덱스 관계
  - 왼쪽 자식 인덱스 = 부모 인덱스 * 2
  • 오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1

삽입

• 최소 힙은 반대!

삭제

최대 힙에서 삭제란 최댓값을 삭제
최댓값은 루트 노드이므로 루트 노드가 삭제된다.
이후 마지막 노드를 루트 노드 자리로 가져오고 이후, swap을 반복하여 정렬