Heap

생성일: 2021년 11월 23일 오후 11:14

Heap.h

• 주의해야할 점 : 여기서 나오는 root, bottom 등의 변수는 기존과는 다르게 객체가 아니라 어레이의 인덱스 번호이다.

#pragma once

template <class ItemType>
void swap(ItemType& one, ItemType& two);

template <class ItemType>
struct HeapType
{
	void ReheapDown(int root, int bottom);
	void ReheapUp(int root, int bottom);

	ItemType* elements; //동적할당 할 어레이
	int numElements; //length 트래킹
};

template <class ItemType>
void swap(ItemType& one, ItemType& two)
{
	ItemType temp;
	temp = one;
	one = two;
	two = temp;
}

template <class ItemType>
void HeapType<ItemType>::ReheapDown(int root, int bottom) //여기서 bottom은 rightmost node(가장 아래 level의 오른쪽 노드), root와 bottom 모두 어레이의 인덱스 번호이다.(객체 X)
{
	int maxChild;
	int rightChild;
	int leftChild;
	//주의 : 위의 변수 전부 인덱스 번호 (객체 X)
	leftChild = root * 2 + 1;
	rightChild = root * 2 + 2;

	if (leftChild <= bottom) //base case는 leftChild > bottom 이다. 이것은 어레이에서 가장 끝 번호인 bottom 보다 leftChild 번호가 더 커질 때, 즉 length를 넘어서 leftChild가 접근할 때이다.
	{
		if (leftChild == bottom) // 한개의 child 가 존재할 때
			maxChild = leftChild;
		else
		{
			if (elements[leftChild] <= elements[rightChild])
				maxChild = rightChild;
			else
				maxChild = leftChild;
		}
		if (elements[root] < elements[maxChild])
		{
			swap(elements[root], elements[maxChild]);
			ReheapDown(maxChild, bottom); //재귀적으로 계속 실행하여 heap 전체의 순서를 바로 잡기
		}
	}
}

template <class ItemType>
void HeapType<ItemType>::ReheapUp(int root, int bottom) // 여기서 bottom은 rightmost node(가장 아래 level의 오른쪽 노드), root와 bottom 모두 어레이의 인덱스 번호이다.(객체 X)
{
	int parent;
	
	if (bottom > root)
	{
		parent = (bottom - 1) / 2;
		if (elements[parent] < elements[bottom])
		{
			swap(elements[parent], elements[bottom]);
			ReheapUp(root, parent);
		}
	}
}