뇌를 자극하는 알고리즘 - 7. 우선순위 큐와 힙: 힙(Heap)

구현소스

Heap.h

#ifndef HEAP_H
#define HEAP_H

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef int Element;

typedef struct tagHeapNode
{
	Element Data;
} HeapNode;


typedef struct tagHeap
{
	HeapNode* Nodes; // 힙 배열
	int Capacity;    // 최대 용량
	int UsedSize;    // 사용 용량
} Heap;
// Heap
// 1. Heap은 완전 이진 트리 구조
// 2. Heap에서 가장 작은 데이터를 갖는 노드는 Root 노드이다.
// 3. 완전 이진 트리를 유지하기 위해선 Node의 삽입 연산 수행시 최고 깊이, 최 우측에 새 노드를 추가 해야 한다.
//  - Linked List로 구현시 이를 찾기란 어려운 일이므로 배열로 구현한다.
// 4. 배열로 구현한 Heap 자료구조의 특징
//   - 깊이 n의 노드(2^n개)는 배열의 2^n - 1 ~ 2^(n+1) - 2 번 요소에 저장된다.
//   - k번 index에 위치한 node의 양쪽 자식 노드들의 인덱스
//     : Left Child = 2k + 1, Right Child = 2k + 2
//   - k번 index에 위치한 node의 부모 노드의 인덱스
//     : (k-1)/2 의 몫

// ex)           2
//          7        52
//      13     8   67   161
//    17 43  88 37
// - Array 
// index: 0  1  2   3   4  5    6   7   8   9   10 
//        2  7  52  13  8  67  161  17  43  88  37

//   7 Node의 Child Node = 2*1+1 (or 2*1+2) = 3(or 4)
// 161 Node의 Parent Node Index = (6-1)/2 = 2 (k=6)

Heap*	Heap_Create(int Init); // 초기 Node의 갯수 Init에 따른 Heap과 Node의 생성
void	Heap_Destroy(Heap* H);
void	Heap_Insert( Heap* H, Element NewData );
	// Heap의 삽입 연산 구현
  // - 최고 깊이, 최 우측에 새 노드를 추가 한 후 부모 노드와 크기 비교
//     - 부모노드보다 크면 연산 종료, 작으면 부모 노드와 새 노드와 위치 변경(데이터 변경)
//     - 그 이후 다시 Heap 구축 조건 체크.
void	Heap_DeleteMin( Heap* H, HeapNode* Root );
	// 최소값 삭제 (Root 노드)
  //  - Root 노드의 데이터를 삭제 후 최고 깊이, 최 우측에 있던 노드를 Root 노드로 옮겨온다. 
//     - 새로운 Root노드의 Left Child, Right Child 와 크기를 비교하고 둘 중 작은 자식과 위치를 교환한다.
//      (부모 노드는 양쪽 자식들보다 작은 값을 가져야 하므로..)
//     - 양쪽 노드보다 작은 값을 갖게 되거나, 자식이 없느 잎 노드가 되면 삭제 연산 종료. - 아니면 반복.

int		Heap_GetParent( int Index ); // Index에 해당 하는 노드의 Parent Node의  Index를 반환. (k-1)/2
int		Heap_GetLeftChild( Heap* H, int Index ); 
	// Index에 해당 하는 노드의 Left Child Node이 Index를 반환
	//  - 2k+1
	//  - Leaf Node의 Index를 넣거나, H->Capacity 이상의 값을 반환하게 되면 메모리 참조 오류가 발생하므로
	//  이를 방지하기 위해 Heap의 정보를 담는 Heap 구조체도 매개변수로 받음. - 일단 취소 -_-;
void	Heap_SwapNodes( Heap* H, int Index1, int Index2 );
	// Index1과 Index2의 Data를 Swap
void	Heap_PrintNodes( Heap* H);


#endif

------------------------------------------

Heap.cpp

#include "Heap.h"


Heap*	Heap_Create(int Init)
{
	Heap* NewHeap = (Heap*) malloc( sizeof(Heap) );

	NewHeap->Capacity = Init;
	NewHeap->UsedSize = 0;
	
	NewHeap->Nodes = (HeapNode*) malloc( sizeof(HeapNode) * (NewHeap->Capacity) );

	return NewHeap;
}
void	Heap_Destroy(Heap* H)
{
	free(H->Nodes);
	free(H);
}
void	Heap_Insert( Heap* H, Element NewData )
{
	// Heap의 삽입 연산 구현
  // - 최고 깊이, 최 우측에 새 노드를 추가 한 후 부모 노드와 크기 비교
//     - 부모노드보다 크면 연산 종료, 작으면 부모 노드와 새 노드와 위치 변경(데이터 변경)
//     - 그 이후 다시 Heap 구축 조건 체크.
		int CurrentPosition = H->UsedSize; // 현재의 size를 저장하고
	int ParentPosition = Heap_GetParent(CurrentPosition); 
	// 현재의 size에 해당하는 Parent Index를 얻는다.
	// - 부모노드와의 크기 비교를 위하여...

	if( H->UsedSize == H->Capacity )
	{ // 용량이 가득 찼을 시
		H->Capacity *= 2; 
		// 두배로 늘림.
		H->Nodes = (HeapNode*) realloc(H->Nodes , sizeof(HeapNode) * H->Capacity );

		// realloc 함수 정보
		// http://winapi.co.kr/clec/reference/realloc.gif
	}
	// 최고 깊이, 최 우측에 새 노드를 추가
	H->Nodes[CurrentPosition].Data = NewData;

	//     - 부모노드보다 크면 연산 종료, 작으면 부모 노드와 새 노드와 위치 변경(데이터 변경)
	//     - 그 이후 다시 Heap 구축 조건 체크.

	while( CurrentPosition > 0 
		&& H->Nodes[CurrentPosition].Data < H->Nodes[ParentPosition].Data)
	{  // 최고깊이 우 하단 부터 부모와의 크기를 비교해 나간다.
	   // 최악의 경우 Root Node의 Left나, Right Child Index까지 가지므로 
		// CurrentPosition > 0 의 조건을 달았다.
		Heap_SwapNodes( H, CurrentPosition, ParentPosition);

		// Root까지 거슬러 올라가기.
		CurrentPosition = ParentPosition;
		ParentPosition = Heap_GetParent(CurrentPosition); 
	}
	
	// 구축 조건을 만족시키는 Loop가 끝나면 Data Insert 작업이 끝나므로 UsedSize를 증가시킴.

	(H->UsedSize)++;
}
void	Heap_DeleteMin( Heap* H, HeapNode* Root )
{
	// 최소값 삭제 (Root 노드)
  //  - Root 노드의 데이터를 삭제 후 최고 깊이, 최 우측에 있던 노드를 Root 노드로 옮겨온다. 
//     - 새로운 Root노드의 Left Child, Right Child 와 크기를 비교하고 둘 중 작은 자식과 위치를 교환한다.
//      (부모 노드는 양쪽 자식들보다 작은 값을 가져야 하므로..)
//     - 양쪽 노드보다 작은 값을 갖게 되거나, 자식이 없는 잎 노드가 되면 삭제 연산 종료. - 아니면 반복.
	int ParentPosition = 0;
	int LeftPosition = 0;
	int RightPosition = 0;

	memcpy(Root, &H->Nodes[0], sizeof(HeapNode) ); // HeapNode* Root 타입에 Heap의 Root를 넣고
	memset(&H->Nodes[0], 0, sizeof(HeapNode) );    // Heap의 Root을 초기화 한다. (NULL 상태)
	
	H->UsedSize--; // 최고 깊이 최우측의 노드의 인덱스를 얻기 위하여 감소. 
	// - 실제로 최소값을 삭제시키므로 데이터 수 감소

	Heap_SwapNodes(H, 0, H->UsedSize);
	// 최고 깊이 최 우측 노드를 Heap의 Root으로 이동
	
	
	// 그 이후 Heap 자료구조의 법칙 적용
	LeftPosition = Heap_GetLeftChild(H,0);
	RightPosition = LeftPosition + 1;
	while(1)
	{
		int SelectedChild = 0;

		
		if( LeftPosition >= H->UsedSize )
			break; // LeftPosition이 현재 데이터 수를 넘어갈시 루프 종료
		

		if( RightPosition>= H->UsedSize )
		{
			SelectedChild = LeftPosition;
			// RightPosition이 현재 데이터 수와 같거나 넘을시
			// LeftPosition의 값이 마지막 데이터을 가리킴
		}

		else // 그외 경우 L값과 R값을 비교해 작은 값의 index를 SelectedChild에 넣음
		{
			if( H->Nodes[LeftPosition].Data  > H->Nodes[RightPosition].Data )
				SelectedChild = RightPosition;
			else
				SelectedChild = LeftPosition;
		}
		// 선택이 끝나면 이제 부모 노드와 L과 R값 중 작은 값을 비교하여
		// 부모노드보다 작다면 데이터를 교환.
		if( H->Nodes[SelectedChild].Data < H->Nodes[ParentPosition].Data)
		{
			Heap_SwapNodes(H,SelectedChild,ParentPosition);
			// 데이터를 교환 후 선택된 차일드들의 자식들과 또 한번 비교하기 위해
			// ParentPosition에 SelectedChild 을 대입
			ParentPosition = SelectedChild;

		}
		else // 부모노드보다 작지 않다면 힙 법칙이 성립하므로 Loop 탈출
			break;

		LeftPosition = Heap_GetLeftChild(H,ParentPosition);
		

		RightPosition = LeftPosition + 1;
	}

	// 지속적인 데이터 삽입과 삭제에 따른 메모리 관리를 위해
	// UsedSize와 Capacity를 비교하여 용량 조정
	if( H->UsedSize < (H->Capacity / 2) )
	{ // 데이터수가 최대용량의 1/2 한거보다 작다면 용량을 1/2로 감소시킴

		H->Capacity /= 2;
		H->Nodes = (HeapNode*) realloc( H->Nodes, sizeof(HeapNode) * H->Capacity );
	}
}

// Index에 해당 하는 노드의 Parent Node의  Index를 반환. (k-1)/2
int		Heap_GetParent( int Index )
{
	int Parent_Index =(int)( (Index-1) / 2 );
	return Parent_Index;

}

// Index에 해당 하는 노드의 Left Child Node이 Index를 반환
	//  - 2k+1
	//  - Leaf Node의 Index를 넣거나, H->Capacity 이상의 값을 반환하게 되면 메모리 참조 오류가 발생하므로
	//  이를 방지하기 위해 Heap의 정보를 담는 Heap 구조체도 매개변수로 받음.
int		Heap_GetLeftChild( Heap* H, int Index )
{
	int LeftChild_Index = (2 * Index) + 1;

	/*
	if(H->Capacity < LeftChild_Index)
	{
		//printf("   - Memory Access Error !!!\n");
		return 0;
	}*/
	// 취소. while문에서 처리함..

	return LeftChild_Index;
}

// Index1과 Index2의 Data를 Swap
void	Heap_SwapNodes( Heap* H, int Index1, int Index2 )
{
	HeapNode Temp;

	Temp.Data = H->Nodes[Index1].Data ;
	H->Nodes[Index1].Data  = H->Nodes[Index2].Data;
	H->Nodes[Index2].Data  = Temp.Data;

}
void	Heap_PrintNodes( Heap* H)
{
	int i;
	
	for( i=0 ; i < H->UsedSize ; i++)
		printf("%d ", H->Nodes[i].Data);

	printf("\n");
}

-----------------------------------------

main.cpp

#include "Heap.h"

int main()
{
	Heap *H = Heap_Create(10);
	HeapNode MinData;

	Heap_Insert(H, 30);	
	// - Heap 
	//     30

	Heap_Insert(H, 51);
	// - Heap
	//     30
	//   51

	Heap_Insert(H, 2);
	// - Heap
	//     30                2
	//   51  2   ===>     51  30

	Heap_Insert(H, 100);
	// - Heap
	//       2
	//    51   30
	// 100

	Heap_Insert(H, 70);
	// - Heap
	//       2
	//    51   30
	// 100  70   

	Heap_Insert(H, 36);
	// - Heap
	//        2                   
	//     51    30  
	//  100 70 36      
	Heap_Insert(H, 5);
	// - Heap
	//        2                     2     
	//     51   30    ===>    51          5
	//  100 70 36 5       100   70     36   30
	Heap_Insert(H, 171);
	// - Heap
	//              2     
	//       51          5
	//    100   70     36  30
	//  171
	
	printf( "Heap Data : ");  
	Heap_PrintNodes(H);

	printf( "Heap's Minimum Data : "); 
	Heap_DeleteMin(H,&MinData);
	printf("%d\n", MinData.Data);
	printf( "Heap Datas : ");  
	Heap_PrintNodes(H);
	// - Heap
	//          171                          5                        5
	//      51       5      ===>       51        171   ===>       51     30
	//  100   70  36   30          100    70   36   30         100  70  36 171
	
	printf( "Heap's Minimum Data : "); 
	Heap_DeleteMin(H,&MinData);
	printf("%d\n", MinData.Data);
	printf( "Heap Datas : ");  
	Heap_PrintNodes(H);

	printf( "Heap's Minimum Data : "); 
	Heap_DeleteMin(H,&MinData);
	printf("%d\n", MinData.Data);
	printf( "Heap Datas : ");  
	Heap_PrintNodes(H);

	Heap_Destroy(H);

	return 0;
}

----------------------------------------

실행 결과