220420_정렬_힙 정렬(Heap Sort) 구현

* 처리 과정을 바탕으로 구현해 보았음

https://hyrule.tistory.com/61

220420_정렬_힙 정렬(Heap Sort) 처리 과정

 

 

//HeapSort.h


/*
<힙 정렬>

* 힙정렬은 최대힙과 최소힙이 있다.
	- 최대힙으로 정렬하면 내림차순, 최소힙으로 정렬하면 오름차순으로 정렬됨.
	- 최대힙 -> 높은 수를 위로
	- 최소힙 - > 낮은 수를 위로

* 정렬 기준은 이전에 했던 방법인,
main에서 선언한 함수를 함수 포인터로 넘겨 대소여부를 비교하는 방식으로 구현함.
(main의 비교함수가 true를 반환하면 자리바꿈, 아니면 놔둠)
	- 이 방식으로 했을 때의 장점: 포인터나 클래스 등 대소판별이 어려운 객체들도
	함수에 판별기준을 추가하여 대소판별이 가능해진다.



* 실제 값의 저장은 배열에 한다.
	- 인덱스 번호를 통해 이진 트리에서의 위치와, 부모 노드의 번호, 자식 노드의 번호
	모두 구할 수 있다.

	- 인덱스로 부모 노드 찾기: (index - 1) / 2
	- 인덱스로 자식 노드 찾기: (index) * 2    + 1(왼쪽자식) or +2(오른쪽자식)

* 나중에 배울, 우선순위 큐와 동작 방식이 유사하다.


<최대 힙 알고리즘 순서>
[Push]
1.  이진 트리의 왼쪽 제일 끝부터 추가한다. 
	- 루트노드(인덱스 0) -> 루트노드 왼쪽(1) -> 루트노드 오른쪽(2) 
	-> 왼쪽 자식노드의 왼쪽(3) -> 왼쪽 자식노드의 오른쪽(4)
	-> 오른쪽 자식노드의 왼쪽 -> 오른쪽 자식노드의 오른쪽 -> ...

2. 값이 추가되면, 같은 부모를 가진 자식노드와 크기를 비교한다.


3. 둘중 큰 자식노드와 부모노드를 비교하여 부모노드보다 크면 해당 서로 스왑한다.
	3-1. 스왑이 일어났고, 위에 또 부모노드가 존재하면 해당 노드에서도 3번을 반복한다.(루트노드까지)
		- 자식간 비교 -> 큰 값과 부모노드와 비교 -> 자식이 더 큰 값을 가지면 부모노드와 스왑

[Pop]
1. 루트노드의 값을 뺀다.

2. 제일 끝에 있는 값을 루트로 올린다.

3. 루트 노드의 두 개의 자식노드 중 큰 값과, 루트 노드를 비교한다.
	5-1. 둘 중 큰 수를 루트노드로 올린다.(자리를 바꿔준다.)
	5-2. 자리 바꿈이 일어났으면 하위 노드도 4 ~ 5를 반복한다.

4. 1 ~ 3을 반복한다.


* 최소 힙 정렬은 최대 힙의 반대로 해 주면 된다.




* 제일 끝에 있는걸 
*
* 장점: 절반씩 잘라내므로 속도가 O(log2)
*/


#pragma once

#include <assert.h>

//일종의 우선순위 큐 구현 과정과 비슷하다.
template <typename T>
class CHeapSort
{
public:
	CHeapSort():
		m_Size(0),
		m_Capacity(4)
	{
		m_Data = new T[m_Capacity];

	}
	~CHeapSort()
	{
		delete[] m_Data;
	}

private:
	T* m_Data;
	int m_Size;
	int m_Capacity;
	bool (*m_Func)(const T&, const T&);


public:
	//main 함수에서 비교용으로 함수를 받아오고, 
	//해당 주소를 클래스의 m_Func 함수 포인터에 저장해 놓는다.
	void SetSortFunction(bool (*Func)(const T&, const T&))
	{
		m_Func = Func;
	}

	void push(const T& Data)
	{
		//용량이 꽉 차면 배열의 크기를 늘려주는 함수 구현
		if (m_Size == m_Capacity)
		{
			m_Capacity *= 2;
			T* Temp = new T[m_Capacity];
			for (int i = 0; i < m_Size + 1; ++i)
			{
				Temp[i] = m_Data[i];
			}

			delete[] m_Data;
			m_Data = Temp;
		}

		//배열의 크기가 충분하면 들어온 데이터를 추가
		m_Data[m_Size] = Data;

		//새로운 데이터가 추가된 인덱스를 인자로 넘겨서
		//데이터 순서 변경작업을 진행한다.
		//새로 추가하는 데이터의 배열 인덱스를 넘겨주어서
		//그 값이 어디에 들어갈지를 계산하는 함수.
		Insert(m_Size);

		//사이즈 1 증가
		++m_Size;

		
	}

	int size() const
	{
		return m_Size;
	}

	bool empty() const
	{
		return m_Size == 0;
	}

	//TOP 함수
	const T& Top() const
	{
		if (empty())
		{
			assert(false);
		}


		return m_Data[0];
	}

	//CLEAR 함수
	void Clear()
	{
		delete[] m_Data;
		m_Capacity = 4;
		m_Data = new T[m_Capacity];
		m_Size = 0;
	}

	//POP 함수
	void Pop()
	{
		//비어있는데 pop하면 경고문
		if (empty())
		{
			assert(false);
		}

		//배열에 딱 하나만 들어있을 경우(m_Size == 1) 해당 값 반환
		else if (1 == m_Size)
		{
			m_Size = 0;
			return;
		}

		--m_Size;

		//가장 마지막에 추가되어있는 값을 루트로 올려주고 제거
		m_Data[0] = m_Data[m_Size];
		

		//값이 제거되었으므로 루트노드부터 리프노드까지 규칙에 맞게 순서LeftIndex를 다시 설정.
		Delete(0);
	}
//여기까지 public/////////////////////////////////

private:
	void Insert(int Index)
	{
		/*
		* 배열의 인덱스를 통해 이진트리의 child 연결시키기
			- 0 = 루트
			- 1, 2 = 루트의 child 노드	->	0 * 2 + 1 or 2
			- 3, 4 = 1의 child 노드		->	1 * 2 + 1 or 2

			- 역으로 child 노드로 부모 노드 구하기
			-3, 4의 부모 = 1 --> (3 - 1)/2, (4 - 1)/2 = 2
			--> (자식 인덱스 - 1) / 2

		* 삽입할 때는 부모 노드와만 비교한다.
		
		*/

		if (0 == Index)
			return;


		//인자로 들어온 인덱스의 부모 인덱스를 구해준다.
		int ParentIndex = (Index - 1) / 2;


		//부모 인덱스와 현재 인덱스를 인자로 비교 함수에 넘겨서
		//true면 서로 스왑한다.
		if (m_Func(m_Data[Index], m_Data[ParentIndex]))
		{
			T Temp = m_Data[ParentIndex];
			m_Data[ParentIndex] = m_Data[Index];
			m_Data[Index] = Temp;

			//스왑이 일어났을 경우, 새로 부모가 된 인덱스와, 
			//그 부모 인덱스끼리 비교한다(재귀함수 호출)
			Insert(ParentIndex);
		}
	}

	void Delete(int Index)
	{
		//삭제할 떄는 기준 노드부터 리프 노드까지
		//자식들 중 더 작은 녀석과 부모 노드를 비교하고
		//자식이 더 작을 경우 부모 노드와 스왑한다.

		//왼쪽 자식노드의 인덱스를 구해준다.(= x2 + 1)
		int LeftChild = Index * 2 + 1;

		//자식 노드가 없으면 종료한다.
		if (LeftChild >= m_Size)
			return;

	
		//오른쪽 자식노드의 인덱스를 구해준다.(= x2 + 2)
		int RightChild = LeftChild + 1;

		//오른쪽 자식노드가 존재 한다면 
		//규칙에 의해 왼쪽 자식노드는 무조건 존재할수밖에 없다
		//오른쪽과 왼쪽의 값을 비교하여 둘 중 어떤 자식노드와 
		//현재노드를 비교해줄지를 결정해준다.


		//값을 비교하고, 교체될 인덱스를 저장하는 변수(기본값: LeftChild)
		int ChildIndex = LeftChild;


		//배열의 최댓값 안에 RightChild가 있으면
		//LeftChild도 무조건 존재한다는 뜻이다.
		//먼저 자식들간의 비교를 한다.
		if(RightChild < m_Size)
		{ 
			//왼쪽 자식과 오른쪽 자식을 비교하고 L < R이면
			//ChildIndex를 RightChild로 바꾸어 준다.
			if (m_Func(m_Data[RightChild], m_Data[LeftChild]))
			{
				ChildIndex = RightChild;
			}
		}

		//ChildIndex에 들어온 자식노드를 부모노드와 비교한다.
		//자식노드가 더 작을 경우 자리를 교체하고 재귀호출을 통해 끝까지 타고들어간다.
		if (m_Func(m_Data[ChildIndex], m_Data[Index]))
		{
			//왼쪽 자식이 부모보다 크면 자리를 교체해준다.
			T Temp = m_Data[ChildIndex];
			m_Data[ChildIndex] = m_Data[Index];
			m_Data[Index] = Temp;

			//교체가 일어났을 경우 자식 인덱스를 기준으로
			//재귀호출하여 계속 비교 확인한다.
			Delete(ChildIndex);
		}

		

	}
};