우선순위큐, 최소 힙, 최대 힙
참고 : http://blog.naver.com/PostView.nhn?blogId=zxy826&logNo=220804468536&parentCategoryNo=32&categoryNo=&viewDate=&isShowPopularPosts=true&from=search
우선순위 큐 (Priority Queue)
우선순위를 가진 항목들을 저장하는 큐
FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 인출된다.
응용 분야
- 시뮬레이션 시스템
- 네트워크 트래픽 제어
- 운영 체제에서의 작업 스케쥴링
힙 (heap)
노드들이 저장하고 있는 키들이 다음의 조건을 만족하는 완전이진트리
- 최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전이진트리
key(부모 노드) >= key(자식 노드)
- 최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전이진트리
key(부모 노드) <= key(자식 노드)
힙 순서 속성
- 트리 내의 모든 자식 노드가 부모 노드보다 큰
최소 힙: 힙에서 가장 작은 데이터를 갖는 노드가 루트노드 - 모든 자식 노드가 부모 노드보다 작아야 하는
최대 힙: 힙에서 가장 큰 데이터를 갖는 노드가 루트노드
힙의 삽입 연산
- 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어서 삽입
- 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족한다.
최소 힙의 삽입 연산
- 힙의 가장 최고 싶이, 최우측에 새 노드를 추가한다.
- 완전 이진 트리를 유지하도록 하기위해
- 삽입한 노드를 부모 노드와 비교한다.
- 삽입한 노드가 부모 노드보다 크면 제 위치에 삽입된 것이므로 연산 종료
- 부모 노드보다 작으면 다음 단계 진행
- 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 서로 바꾼다.
- 위치를 바꾼 후 2번을 다시 진행한다.
힙의 삭제 연산
- 루트노드를 삭제한다.
- 마지막 노드를 루트노드로 이동한다.
- 루트에서부터 단말노드까지의 경로에 있는 노드들을 교환하여 힙의 성질을 만족시킨다.
최소 힙의 삭제 연산
루트노드가 최소값 노드이므로 루트노드를 삭제한다.
루트노드를 삭제한 후 힙 순서 속성을 유지하는 것이 삭제 연산의 관건이다.
- 힙의 루트에서 최고 깊이, 최우측에 있던 노드를 루트노드로 옮겨온다.
- 힙의 완전이진트리를 유지하는 반면 힙의 순서 속성이 파괴된다.
- 이를 복원하기 위한 작업을 다음 단계부터 시작한다.
- 옮겨온 노드의 양쪽 자식을 비교하여 작은 쪽 자식과 위치 교환을 한다.
- 힙 순서 속성이 지켜지려면 부모 노드는 양쪽 자식보다 작은 값을 가져야하기 때문이다.
- 옮겨온 노드가 더 이상 자식이 없는 잎노드가 되거나 양쪽 자식보다 작은 값을 갖는 경우에는 삭제 연산을 종료한다. 그렇지 않은 경우에는 2번을 반복한다.
힙의 구현 방법
힙은 배열을 이용하여 구현
왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
힙의 높이
n개의 노드를 가지고 있는 힙의 높이는 O(logn)
- 힙의 완전이진트리
- 마지막 레벨 h를 제외하고는 각 레벨 i에 2^(i-1)개의 노드 존재
http://postfiles15.naver.net/20160904_78/zxy826_1472965824970vSbuj_JPEG/20.PNG?type=w1