C++기초
220420_정렬_힙 정렬(Heap Sort) 구현
hyrule
2022. 4. 27. 14:27
* 처리 과정을 바탕으로 구현해 보았음
220420_정렬_힙 정렬(Heap Sort) 처리 과정
hyrule.tistory.com
//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);
}
}
};