[자료구조] Heap, 히프, 최대히프, 최소히프

2009년 글...

re: Heapsort 질문

 

우선 히프(heap)가 뭔지에 대해서 생각해보죠.

 

히프란, 기본적으로 '완전 이진 트리'입니다.

보통 우리가 말하는 히프란 최대 히프를 말합니다.

 

최대히프 : 부모노드의 키 값이 자식노드의 키 값보다 작지 않은 완전 이진 트리(complete binary tree)

최소히프 : 부모노드의 키 값이 자식노드의 키 값보다 크지 않은 완전 이진 트리(complete binary tree)

 

또한 히프는 중복이 가능합니다.

 

정리하면...

 

1. 완전이진트리

2. 최대히프, 최소히프

3. 중복가능

이 세가지가 중요 요소입니다.

 

완전이진트리는 번호를 생각해봤을때, 1부터 순서대로 채워나가기 때문에,

순차표현을 쓰는것이 효율적입니다. 배열을 사용했을때 중간중간 빈 공간이 없기때문이죠.

 

자, 이정도 사전 지식을 갖춘상태에서

10,8,12,7,10,3,5,9,4을 공백 최대 히프에 삽입한다고 했을 때,

결론적으론 아래와 같은 모양이 됩니다.

 

 

 

위에서의 숫자는 배열의 인덱스 입니다.

트리를 배열로 표현했을 때, 0번 공간은 비워놓고 사용합니다. ^^ 

 

삽입횟수	배열[1]	배열[2]	배열[3]	배열[4]	배열[5]	배열[6]	배열[7]	배열[8]	배열[9]
첫번째	10
두번째	10	8
3	12	8	10
4	12	8	10	7
5	12	10	10	7	8
6	12	10	10	7	8	3
7	12	10	10	7	8	3	5
8	12	10	10	9	8	3	5	7
9	12	10	10	9	8	3	5	7	4

 

이 표에서 파란색은 그 횟수에 새로 삽입된 원소값, 빨간색은 삽입 때문에 바뀐 원소값입니다.

(삽입을 했을때는 최대히프의 성질을 유지하기 위해 정렬을 하게 됩니다.)

 

 

bool ismaxheap(int a[], int n)

{

pre: a[0,...n-1] is an array of ints

post: returns true if array a is a valid max heap and otherwise false

}

 

이 함수는

ADT(Abstract data type)에 있다고 가정하고(정확히 있는지 모르겠어서...) 생각해보면,,

heap가 최대 heap(즉, max heap)인지 검사하는 함수 입니다.

배열( a[] )과 원소의 갯수( n )를 매개변수로 넘겨주는군요.

pre와 post는... 전, 후라는 의미인데..

여기서는 그냥 함수의 기능이나 그 전에 정의되어야하는 것들에 대해서 설명을 해 주는군요.

 

배열 a[]는 int형 배열이어야 한다. 라는 것과

만약 배열이 최대히프라면 true를 리턴하고 아니면 false를 리턴하라는 것.

이 두가지에 대해서 얘기하고 있네요.

 

bool ismaxheap(int a[], int n) 에서

bool은 boolean형으로 값으로는 true나 false 두가지만을 가질 수 있습니다.

함수에서 제일 앞에 오는 형(type)은 return 할 값의 데이터 타입을 의미 합니다.