[자료구조] Heap

🎞️ 우선순위 큐

Priority Queue: 우선순위 개념을 도입한 큐
큐인데 우선순위가 높은 데이터 먼저 삭제됨 - 배열/연결리스트/힙으로 구현 가능

🎞️ Heap

힙: 완전 이진 트리(Complete BT)의 일종

종류: 최대 힙(Max heap), 최소 힙(Min heap)

• Max heap: 부모 노드의 키 값이 자식 노드의 키 값 이상
• Min heap: 부모 노드의 키 값이 자식 노드의 키 값 이하

🎞️ 힙을 배열로 구현

root 노드 - 배열의 인덱스 1에 저장
부모와 자식 노드

• 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
• 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1
• 부모의 인덱스 = (자식의 인덱스) // 2

🎞️ 힙의 삽입, 삭제

삽입

1. 새 노드를 힙의 마지막 노드에 이어서 삽입
2. 새 구조가 힙의 조건에 부합할 때까지 자식 노드와 부모 노드 교환 (heapify)

삭제

1. 최대 힙에서 최댓값은 루트 노드라서 루트 노드가 삭제됨
2. 삭제된 루트 노드에는 힙의 마지막 노드를 넣음
3. 새 구조가 힙의 조건에 부합할 때까지 자식노드와 부모 노드 교환 (heapify)

힙 내 테이터가 변경(삽입/삭제)될 때마다 heapify 과정을 겪기 때문에 항상 정렬 상태 유지

🎞️ 힙 정렬의 시간복잡도

과정

1. 정렬할 N개의 원소로 최대 힙 구성
2. 최대 힙의 루트 노드와 마지막 원소 위치 교환
3. 새 루트 노드에 대해 최대 힙 구성
4. 원소 개수만큼 2~3 반복 수행

O(N * log N)

• heapify 알고리즘: O(log N)
  • unstable
• 전체: heapify 알고리즘 전체 데이터 수 = O(N log N)

---

참고:

• [자료구조] 힙(heap)이란
• [자료구조] 힙(heap) 자료구조