19. 이진트리 -f. 힙(Heap)

힙

  # 힙이란 부모노드에 저장된 값이 자식노드의 값(혹은 우선순위)보다 항상 큰 (혹은 항상 작은) 완전이진트리이다.

  # 즉 힙은 다음의 세가지 조건을 만족하는 자료구조이다.

    1) 항상 완전이진트리의 형태이다.

    2) 부모 노드의 키값이 자식 노드의 각각의 키값보다 항상 크다. (혹은 항상 작다.) 

    3) 자식 노드의 키값은 자식 노드의 자식 노드보다 항상 크다. (혹은 항상 작다.) 즉 재귀적인 구조를 갖는다.

  # 힙에서 형제 노드끼리의 값은 비교하지 않는다.

  # 루트노드의 값이 항상 가장 큰 힙을 최대 힙 (Max Heap)이라 하고, 항상 가장 작은 힙을 최소 힙(Min Heap)이라 한다.

  # 힙과 이진탐색트리의 삽입, 삭제, 탐색시의 시간 복잡도를 비교해보면

     이진탐색트리는 평균적인 경우 삽입 : LogN, 삭제 : N^½, 탐색 : LogN, 최악의 경우 : 삽입 : N, 삭제 : N, 탐색 : N 의 시간복잡도를 갖지만

     힙은 언제나 삽입 : LogN, 삭제 : LogN, 탐색 : 1의 시간복잡도를 보장한다.

  # 힙의 구현을 우선하기 위해서 데이터형을 int로 한정했다.

  # 이를 노드가 임의의 데이터를 갖게 하고 임의의 테이터의 대소 비교의 기준이 되는 함수를 지정하는 형태로 확장할 수도 있을 것이다.

C++로 구현한 배열기반의 힙(Heap)

#pragma once
#include <math.h>

class Heap
{
	int* capacity;
	int iSize;

	int iCount;

	int* tRet;

private:
	int   ParentIndex(int index); // 지정한 노드의 부모 노드의 인덱스를 반환
	int   LeftIndex(int index);   // 지정한 노드의 왼쪽 노드의 인덱스를 반환
	int   RightIndex(int index);  // 지정한 노드의 오른쪽 노드의 인덱스를 반환

public:
	bool   AddNode(int data);
	int    DelNode();
	int    CheckRoot();

	int  getCount();
	int  getSize();


public:
	Heap(int size);
	virtual ~Heap();
};

//------------------------>

//private Function
// 지정한 노드의 부모 노드의 인덱스를 반환, -1은 없음을 의미.
int   Heap::ParentIndex(int index)
{
	if (index == 0) {
		return -1;
	}

	return (index - 1) / 2;
}

// 지정한 노드의 왼쪽 노드의 인덱스를 반환, -1은 없음을 의미.
int   Heap::LeftIndex(int index)
{
	int iRet = index * 2 + 1;

	if (iRet >= iCount) {
		return -1;
	}

	return iRet;
}

// 지정한 노드의 오른쪽 노드의 인덱스를 반환, -1은 없음을 의미.
int   Heap::RightIndex(int index)
{
	int iRet = index * 2 + 2;

	if (iRet >= iCount) {
		return -1;
	}

	return iRet;
}


//---------------------------->
//Public Function
Heap::Heap(int _size)
{
	iSize = _size;
	capacity = new int[iSize];
	iCount = 0;
	tRet = new int;
}

bool Heap::AddNode(int data)
{
	if (iCount == iSize) {
		return false;
	}

	capacity[iCount] = data;

	int nowIndex = iCount++;

	while (true) {

		if (capacity[ParentIndex(nowIndex)] > capacity[nowIndex]) {
			int temp = capacity[ParentIndex(nowIndex)];
			capacity[ParentIndex(nowIndex)] = capacity[nowIndex];
			capacity[nowIndex] = temp;
			nowIndex = ParentIndex(nowIndex);
		}
		else {
			break;
		}

	}

	return true;
}

int Heap::DelNode()
{
	if (iCount == 0) {
		tRet = nullptr;
	}


	*tRet = capacity[0];
	capacity[0] = capacity[--iCount];

	int nowIndex = 0;
	bool whilesw = true;

	if (iCount == 0) {
		*tRet = capacity[0];
		return *tRet;
	}


	while (whilesw) {

		int left = LeftIndex(nowIndex);
		int right = RightIndex(nowIndex);

		if (iCount > 1) {
			if (left == -1 || right == -1) {
				whilesw = false;
				break;
			}
		}
		else {
			if (*tRet > capacity[0]) {
				capacity[1] = *tRet;
				*tRet = capacity[0];
				capacity[0] = capacity[1];
				whilesw = false;
				break;
			}
			else {
				whilesw = false;
				break;
			}
		}

		if (capacity[left] < capacity[right]) {

			if (capacity[nowIndex] > capacity[left]) {
				int temp = capacity[nowIndex];
				capacity[nowIndex] = capacity[left];
				capacity[left] = temp;
				nowIndex = left;
			}
			else {
				break;
			}

		}
		else {

			if (capacity[nowIndex] > capacity[right]) {
				int temp = capacity[nowIndex];
				capacity[nowIndex] = capacity[right];
				capacity[right] = temp;
				nowIndex = right;
			}
			else {
				break;
			}

		}

	}
	return *tRet;
}

int Heap::CheckRoot()
{
	*tRet = capacity[0];

	return *tRet;
}

int  Heap::getCount()
{
	return iCount;
}

int  Heap::getSize()
{
	return iSize;
}

Heap::~Heap()
{

}