3. 자료구조 (3) - 힙, 구조체

 

힙

힙은 이진 트리에서 특정한 조건을 이룬 구조입니다.

1. 이진 트리 T의 높이가 h라고 할때 h-1까지 완전 이진 트리이다.
2. 모든 잎 노드는 깊이가 h나 h-1이다.
3. 깊이 h의 모든 잎 노드들의 경로는 h-1의 모든 잎 노드보다 왼쪽에 있다.

힙은 역시 부분 순서 트리(Partial order tree)이기도 한데, 이는 모든 노드가 자식 노드보다 값이 크거나 같은 트리 ($key(parent)\geq key(child)$)입니다.
-> 완전 순서 트리 (Total order tree) = 완전 정렬된 트리.
이진 탐색 트리에서는 중복된 값이 불가능하나, 힙에서는 가능합니다.
부모가 자식의 키 값보다 작은 최대 히프(max heap), 부모가 자식 노드보다 작은 최소 히프 (min heap) 두 종류가 존재합니다.
배열로 구현 시 역시 루트 노드가 1부터 시작한다고 할 때, 그 자식 노드들은 부모 노드 *2, *2+1한 인덱스에 위치하는 방법으로 표현할 수 있습니다.

힙 삽입과정

heap_size = heap_size +1;

i = heap_size;

A[i] =key //A에서 i번째 맨 마지막에 키 삽입

while i != 1 and A[i] > A[PARENT] do //부모보다 크면 위치 바꾸기
	swap (A[i],A[PARENT])
	i = A[PARENT]

힙 삭제과정

item = A[l]	//루트 노드를 반환하여 item에 담음
A[l] = A[heap_size]	//말단 노드를 루트 노드로 옮김
heap_size = heap_size-1
i = 2;	
while i<= heap_size do	// 다시 힙을 구축하는 과정.
	if i<heap_size and A[i+1] > A[i]	//자식들 중 큰 자식을 찾기
		then largest = i+1;
		else largest = i
	if A[PARENT(largest)] > A[largest]	//부모가 더 크면 중지
		then break;
	swap (A[PARENT(largest)],A[largest])	//아니면 부모와 교환후
	i = CHILD(largest)	//다음 레벨 진행
return item

이러한 힙 구조체를 사용하여 정렬을 하거나, 허프만 코드 탐색등의 다양한 분야에 활용될 수 있습니다.

 

구조체

구조체는 여러 타입의 데이터들을 한데 묶어 놓는 자료형입니다.

C/ C#계열에서는 struct 키워드로 선언 후 사용, java에서는 따로 없음.

구조체(struct)와 클래스(class)의 차이점(in C#)

1. 클래스 : 참조형 / 구조체 : 값형 -> 클래스는 참조 복사, 구조체는 내용 복사
2. 클래스 객체는 힙에 저장, 구조체 객체는 스택에 저장
3. 구조체는 상속 불가능
4. 구조체 소멸자가 없음
5. 구조체 멤버는 초기값을 가질 수 없음