[자료구조] 11강 히프

히프 추상 데이터 타입

히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조이다.

최대히프는 킷값이 가장 큰 노드를 찾기 위한 완전이진 트리이며 부모 노드의 킷값은 자식 노드의 킷값보다 항상 크거나 같다. 따라서 루트노드는 킷값들 중 가장 큰 노드가 된다.

최소히프는 킷값이 가장 작은 도르르 찾기 위한 완전이진 트리로 부모 노드의 킷값이 자식 노드의 킷값보다 항상 작거나 같다. 따라서 루트노드는 킷값들 중 가장 작은 노드가 된다.

 

ADT HEAP

데이터 : n개의 원소로 구성된 완전 이진트리로서 각 노드의 킷값은 그의 자식 노드의 킷값보다 크거나 같다. (부모 노드의 킷값>=자식 노드의 킷값)

 

createHeap() : 공백 히트를 생성하는 연산

isEmpty(heap) : 히프가 공백인지 검사하는 연산

deleteHeap(heap) : 히프에서 킷값이 가장 큰 원소 및 가장 작은 원소를 삭제하고 반환하는 연산

 

2. 우선순위 큐

<배열로 표현된 우선순위 큐>

일반적인 큐는 선입 선출(FIFO)의 원칙에 의해 먼저 들어온 데이터가 먼저 나가게 된다. 반면에 우선순위 큐는 원소들 간의 우선순위를 미리 정하여 우선순위가 높은 데이터가 먼저 나가게 된다.

우선순위 큐는 운영체제의 작업 스케줄링이나 수치 해석적인 계산들에 사용된다.

최소 우선순위 큐는 가장 우선순위가 낮은 요소를 먼저 삭제하는 것이고 최대 우선순위 큐는 가장 우선순위가 높은 요소를 먼저 삭제하는 큐이다.

우선순위 큐를 구현하는 방법에는 배열이나 연결 리스트를 이용하는 방법과 히프를 이용하여 구현하는 방법이 있다.

배열을 구현하는 방법은 각 배열의 원소들을 우선순위에 따라 오름차순으로 정렬하여 가장 우선순위가 큰 레코드는 항상 배열의 마지막에 위치하는 방법

삭제하는 연산은 항상 마지막 레코드에 대하여 반환함으로 시간 복잡 도는 O(1)가된다.

 

<연결 리스트로 표현된 우선순위 큐>

연결리스트로 표현방법은 정렬이 안 된 배열에 대해서는 새로운 레코드를 무조건 배열 끝에 삽입하므로 삽입에 대한 효율은 O(1)이다.

연결 리스트로 표현된 레코드들은 우선순위를 기준으로 내림차순 정렬한다.

우선순위가 가장 높은 레코드를 헤드 포인터가 직접 가리키도록 하고, 삭제 연산이 요구되면 헤드 포인터가 가리키는 첫 번째 원소를 삭제 반환하게 된다.

배열로 된 우선순위 큐와 다르게 삭제 연산을 위해서 이동하는 시간이 없다.

우선순위 큐를 표현하는 방법은 히프를 이용하는 방법이 있는데 우선순위 큐를 구현하기 위해 우선순위가 부여된 레코드들을 최대 히프로 구성하여 삭제 연산을 진행하는 경우는 루트 노드를 삭제 반환한다.

 

3. 최대 히프에서의 삽입

최대 히프에서의 원소의 삽입은 이미 구성된 완전이진 트리를 유지하면서 새로 삽입되는 노드를 임시로 저장한 후, 삽입된 원소와 이미 구성된 완전이진 트리와의 크기 관계를 비교하여 원소 이동을 통해 다시 최대 히프로 된 완전이진 트리를 생성

이동은 현재 부모노드의 킷값과 삽입하는 원소의 크기를 비교하여 부모 노드가 크거나 같다는 조건을 만족하지 않으면 서로 값을 교환하고 교환된 자식노드는 다시 상위 부모노드와 크기 관계를 비교반복 수행

 

4. 최대 히프에서의 삭제

최대 히프에서의 원소 삭제 연산은 루트 노드를 삭제 반환한 후에도 최대 히프로 구성된 완전이진 트리로 재구성하는 부가적인 작업이 필요

최대 히프에서 루트노드를 삭제 반환한 후에 완전이진 트리의 마지막 원소를 루트 노드에 임시저장한후 임시 저장된 원소를 가진 이진 트리를 다시 최대 히프로 재구성하기 위해서 자식 노드들과 비교하여 가장 큰 원소와 교환하고 다시 교환되어진 원소와 자식 노드들 간의 크기를 관계를 비교하여 가장 큰 원소와 교환하고 다시 교환되어진 원소와 자식 노드들 간의 크기 관계를 비교하여 자식 노드들 중에서 가장 큰 원소와 교환한다. 이후 반복 수행