[C++/자료구조] 힙(Heap)

Heap : 힙

- 특징

1) 완전 이진 트리 형태
2) 부모 노드와 자식 노드 간의 대소관계가 정해진 완전 이진 트리 구조
3) 루트 노드는 항상 최솟값 또는 최대값을 가진다
4) 최소 힙 또는 최대 힙이 있다.
- 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작은 경우
- 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 큰 경우

- 장점

1) 최소값 또는 최대값을 상수시간 O(1)에 찾을 수있다.
2) 정렬, 우선순위 큐 등에서 유용하게 사용
3) 이진 탐색 트리보다 간단하고 빠르게 구현할 수 있다.

- 단점

1) 중복된 값의 처리가 어렵다.
2) 삽입, 삭제, 연산에 시간 복잡도가 O(log n)이 소모된다.

Heap.h

#pragma once

void DoHeap();

class Heap
{
public:
	Heap(int maxSize);
	~Heap();

	void Insert(DataType data);
	DataType Pop();
	void clear();

	bool IsEmpty();
	bool IsFull();

	void PrintHierarchy();
	const DataType GetData(int i) { return Data[i]; }

private:
	int GetParent(int index);
	int GetLeftChild(int index);
	int GetRightChild(int index);

	void HeapifyUp(int index);		// 힙의 상향식 재정렬
	void HeapifyDown(int index);		// 힙의 하향식 재정렬
	void PrintHierarchy(int index, string indent, bool last);

private:
	DataType* Data;
	int MaxSize;
	int Size;
};

Heap.cpp

#include "stdafx.h"
#include "Heap.h"

void DoHeap()
{
	Heap h(10);

	cout << "Insert Heap" << endl;

	for (int i = 0; i < 10; i++)
		h.Insert(rand() % 90);

	h.PrintHierarchy();

	cout << endll << "Array" << endl;
	for (int i = 0; i < 10; i++)
		cout << "Data [ " << i << " ]  " << h.GetData(i) << endl;

	cout << "Pop Heap" << endl;
	for (int i = 0; i < 10; i++)
		cout << h.Pop() << " ";

	h.clear();

	Pause;
}

Heap::Heap(int maxSize)
{
	Data = new DataType[maxSize];
	MaxSize = maxSize;
	Size = 0;
}

Heap::~Heap()
{
	delete[] Data;
}

void Heap::Insert(DataType data)
{
	if (IsFull())
		return;

	Data[Size] = data;
	HeapifyUp(Size);
	Size++;
}

DataType Heap::Pop()
{
	if (IsEmpty())
		return -1;

	cout << endl;
	PrintHierarchy();
	cout << endl;

	DataType RootData = Data[0];

	// 마지막 노드의 데이터를 루트 노드로 옮기고 크기를 줄임
	Data[0] = Data[Size - 1];
	Size--;

	// 루트 노드를 기준으로 힙 구조를 유지하도록 HeapifyDown 함수 호출
	HeapifyDown(0);

	return RootData;
}

void Heap::clear()
{
	delete[] Data;
	Data = new DataType[MaxSize];
	Size = 0;
}

bool Heap::IsEmpty()
{
	return Size == 0;
}

bool Heap::IsFull()
{
	return Size == MaxSize;
}

void Heap::PrintHierarchy()
{
	PrintHierarchy(0, "", true);
}

int Heap::GetParent(int index)
{
	return (index - 1) / 2;
}

int Heap::GetLeftChild(int index)
{
	return index * 2 + 1;
}

int Heap::GetRightChild(int index)
{
	return index * 2 + 2;
}

/*
새로운 원소를 삽입하거나 기존 원소를 수정한 후,
힙 조건을 만족하도록 부모 노드와 자식 노드를 비교하여 교환하는 함수
*/
void Heap::HeapifyUp(int index)
{
	int parentIndex = GetParent(index);

	// 현재 노드가 루트 노드가 아니고, 부모 노드보다 큰 경우
	if (index > 0 && Data[index] > Data[parentIndex])
	{
		// 현재 노드와 부모 노드의 값을 교환
		swap(Data[index], Data[parentIndex]);
		// 부모와 현재 노드가 교환되었으므로, 부모 노드를 기준으로 다시한번
		// 함수를 호출
		HeapifyUp(parentIndex);
	}
}

/*
루트 노드를 제거한 후, 마지막 노드를 루트 노드로 옮긴 후,
자식 노드와 비교하여 교환하면서 힙 조건을 만족하도록 하는 함수
*/
void Heap::HeapifyDown(int index)
{
	// 왼쪽 자식 노드와 오른쪽 자식 노드를 불러오기
	int leftIndex = GetLeftChild(index);
	int rightIndex = GetRightChild(index);
	// 현재 노드를 가장 큰 값으로 초기화
	int largestIndex = index;

	// 왼쪽 자식 노드가 힙의 크기를 넘지 않고, 현재 노드보다 큰 경우
	if (leftIndex < Size && Data[leftIndex] > Data[largestIndex])
		largestIndex = leftIndex;

	// 오른쪽 자식 노드가 힙의 크기를 넘지 않고, 현재 노드보다 큰 경우
	if (rightIndex < Size && Data[rightIndex] > Data[largestIndex])
		largestIndex = rightIndex;

	// 제일 큰 인덱스가 현재 노드와 다른 경우
	// 즉, 자식 노드 중 하나가 더 큰 경우
	if (largestIndex != index)
	{
		// 현재 노드와 largestIndex 위치의 값을 교환
		swap(Data[index], Data[largestIndex]);
		// largestIndex 위치로 이동한 원소를 기준으로 HeapifyDown을 다시 호출
		HeapifyDown(largestIndex);
	}
}

void Heap::PrintHierarchy(int index, string indent, bool last)
{
	// 출력할 노드의 위치와, 마지막 노드인지 여부에 따라 출력할 문구 설정
	cout << indent;
	if (last)
	{
		// 마지막 노드인 경우 출력
		cout << "└─ ";
		// indent에 2칸 공백 추가
		indent += "  ";
	}
	else
	{
		// 마지막 노드가 아닌 경우 출력
		cout << "├─ ";
		// indent에 |와 공백 추가"
		indent += "| ";
	}

	// 현재 노드의 값을 출력
	cout << Data[index] << endl;

	// 오른쪽 자식 노드를 방문하여 계층 구조를 출력
	if (2 * index + 2 < Size)
	{
		bool lastRight = false;
		if (2 * index + 1 >= Size)
			lastRight = true;
		PrintHierarchy(2 * index + 2, indent + (last ? "  " : "| "), lastRight);
	}

	// 왼쪽 자식 노드를 방문하여 계층 구조를 출력
	if (2 * index + 1 < Size)
	{
		PrintHierarchy(2 * index + 1, indent + (last ? "  " : "| "), true);
	}
}