🎞️ 우선순위 큐
Priority Queue: 우선순위 개념을 도입한 큐
큐인데 우선순위가 높은 데이터 먼저 삭제됨 - 배열/연결리스트/힙으로 구현 가능
🎞️ Heap
힙: 완전 이진 트리(Complete BT)의 일종
종류: 최대 힙(Max heap), 최소 힙(Min heap)
- Max heap: 부모 노드의 키 값이 자식 노드의 키 값 이상
- Min heap: 부모 노드의 키 값이 자식 노드의 키 값 이하
🎞️ 힙을 배열로 구현
root 노드 - 배열의 인덱스 1에 저장
부모와 자식 노드
- 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
- 오른쪽 자식의 인덱스 = (부모의 인덱스)*2 + 1
- 부모의 인덱스 = (자식의 인덱스) // 2
🎞️ 힙의 삽입, 삭제
삽입
- 새 노드를 힙의 마지막 노드에 이어서 삽입
- 새 구조가 힙의 조건에 부합할 때까지 자식 노드와 부모 노드 교환 (heapify)
삭제
- 최대 힙에서 최댓값은 루트 노드라서 루트 노드가 삭제됨
- 삭제된 루트 노드에는 힙의 마지막 노드를 넣음
- 새 구조가 힙의 조건에 부합할 때까지 자식노드와 부모 노드 교환 (heapify)
힙 내 테이터가 변경(삽입/삭제)될 때마다 heapify 과정을 겪기 때문에 항상 정렬 상태 유지
🎞️ 힙 정렬의 시간복잡도
과정
- 정렬할 N개의 원소로 최대 힙 구성
- 최대 힙의 루트 노드와 마지막 원소 위치 교환
- 새 루트 노드에 대해 최대 힙 구성
- 원소 개수만큼 2~3 반복 수행
O(N * log N)
- heapify 알고리즘: O(log N)
- unstable
- 전체: heapify 알고리즘 전체 데이터 수 = O(N log N)
참고:
우당탕탕