[자료구조](15)[우선순위 큐 & 힙]

 

우선순위 큐

가장 높은 우선순위를 가진 데이터부터 pop하는 자료구조
(일반 큐는 삽입 순서로, 우선순위 큐는 우선순위 기준으로 pop)

• 이용
  CPU의 작업 스케줄러: 중요한 것부터 처리
  네비게이션 길찾기: 사용자가 어떤 것에 초점을 맞추느냐를 반영
  응급실: 급한 환자부터 처리

우선순위 큐 ADT

• key (우선순위): 비교에 이용되는 값
• 데이터
• 연산
  생성
  삽입
  삭제 등...

-> 얘도 array, linked list, binary tree 등으로 구현 가능!

 

힙

부모보다 자식이 큰/작은 완전 이진트리
(이진 탐색트리 마냥 좌우까지 완벽한 정렬은 아니더라도 부모-자식간은 정렬이 되어 있어야 됨)
-> 각 데이터를 인덱스로 접근 가능해 매우 빠름!
종류

• Max heap: 큰 것이 가장 위에 있는 힙
• Min heap: 작은 것이 가장 위에 있는 힙
  연산
• bubbling up
  원소를 삽입할 때 발생
  삽입한 원소와 부모 노드를 비교하고 힙 성질에 따라 위로 이동
  
  예) 2를 삽입했을 때 bubbling up

    3           3           2
   /     ->    / \   ->    / \
  5           5   2       5   3

• bubbling down
  원소를 제거할 때 발생
  제거한 원소 자리에 맨 마지막 노드를 넣고
  그 노드와 자식을 비교하며 아래로 이동
  
  예) 2를 제거했을 때 bubbling down

      2            4             3
     / \          / \           / \
    5   3  ->    5   3     ->  5   4
   /
  4

힙 만들기

• 힙화 (heapify): 트리가 힙의 성질을 가지게 하는 과정
  정렬되지 않은 배열에서 힙을 만들려고 할 때
  새로운 요소를 넣을 때
  루트 노드를 삭제할 때

정렬되지 않은 배열에서 힙 만들기

• 맨 바닥부터 만들기
  힙에 요소들을 '추가'한다
  힙에 위배된다면 heapify 진행
  (bubbling up)
  -> 시간복잡도 = O(NlogN)
• 정렬되지 않은 트리에서 만들기
  마지막 부모 노드에서부터 루트까지 비교하며 heapify
  (bubbling down)
  -> 시간복잡도 = O(N)
  (자세한건 이거 참고)