[자료구조] Heap (재구현)

이전에 힙을 구현한적이 있는데 다시 정리해서 구현한 글입니다.

---

힙?

힙이란? '이진트리'이면서 '완전 이진트리'입니다.

힙은 max heap, min heap으로 나뉩니다.

중요한 점은 heap은 '완전 이진트리'라는 점입니다.

 

이진트리는 자식의 최대 개수가 두개인 트리의 형태를 의미합니다.

완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진트리입니다.

트리에 대한 개념은 https://code-lab1.tistory.com/8 <- 를 참고해주세요 ㅎㅎ

 

힙이 완전 이진트리이기 때문에 중요한 특징을 가집니다.

- 부모의 왼쪽 자식 노드 인덱스 : parentIdx * 2

- 부모의 오른쪽 자식 노드 인덱스 : parentIdx * 2 + 1

위의 특징을 가집니다.

 

알아두어야 할 점들!

- heap자체 자료구조를 std::vector를 사용하여 구현하였습니다.

- 빠른 구현을 위해 min, max heap은 코드내에 Less, Greater 함수 포인터를 Heap생성자에 넘겨 구현하였습니다.

- 빠른 구현을 위해 루트는 1번 노드로 가정하고 구현하였습니다.

- 마지막 인덱스는 완전 이진트리이기 때문에 항상 numberOfData + 1입니다. (마지막 데이터가 있는 곳의 위치는 vec[numberOfData]) 입니다)

 

삽입

1. 새로 들어온 데이터는 우선순위가 제일 낮다고 가정한다. 그리고 가장 마지막 위치에 데이터를 저장한다.

2. 부모노드와 우선순위를 비교하여 새로들어온 데이터의 우선순위가 높다면 부모와 자리를 바꾼다.

3. 1, 2번을 반복해서 루트까지 올라갑니다.

 

삭제

우선순위가 가장 높은 데이터를 삭제합니다. 삭제하고 나서도 완전 이진트리의 형태를 유지하는 것이 핵심입니다.

1. root노드의 데이터를 삭제한다. 그리고 가장 마지막 노드의 데이터를 root노드의 자리로 옮긴다.

2. root노드의 자리에 들어간 가장 마지막 데이터와 root노드 인덱스 기준으로 왼/오 자식의 우선순위를 비교하여 높은 우선순위를 가지는 자식인덱스의 데이터와 root노드위치에 위치한 마지막 데이터를 비교한다.

3. root오 올라간 마지막 데이터의 우선순위가 낮다면 우선순위가 높은 자식과 자리를 바꾼다. (그렇지 않다면, root로 올라간 마지막 데이터의 우선순위가 더 높다면 그대로 놔둔다.)

4. 1~3번을 반복합니다. 

 

Code

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <memory>
using namespace std;

const int heapSize = 100;

class Heap
{
public:
	Heap(int size, bool (*comp)(int, int))
		:
		vec(vector<int>(size, 0)),
		comp(comp)
	{
		cout << "Heap 생성!, size : " << size << endl;
	}

public:
	// 현재 힙의 데이터 개수 반환
	inline const int GetHeapDataCnt() const { return numberOfData; }

	// 현재 인덱스를 기준으로 부모 인덱스 반환
	inline const int GetParentIdx(const int currentIdx) const
	{
		return int(currentIdx / 2);
	}

	// 부모 인덱스를 기준으로 Left Child 인덱스 반환
	inline const int GetLCIdx(const int parentIdx) const
	{
		return parentIdx * 2;
	};

	// 부모 인덱스를 기준으로 Right Child 인덱스 반환
	inline const int GetRCIdx(const int parentIdx) const
	{
		return parentIdx * 2 + 1;
	};

	// 현재 인덱스를 기준으로 comp에 따라 우선순위가 높은 인덱스 반환
	inline const int GetPrioirityChildIdx(const int idx) const
	{
		int leftIdx = GetLCIdx(idx);
		int rightIdx = GetRCIdx(idx);

		// 왼쪽 자식의 인덱스가 데이터 개수보다 크다 ==
		// 현재 인자로 들어온 idx의 왼쪽 자식이 없다
		// 0 을 반환해서 while문을 종료 시킨다.
		if (leftIdx > numberOfData)
		{
			return 0;
		}
		// 완전 이진트리이기 때문에 leftIdx가 데이터 개수와 같다면 왼쪽자식인덱스를 반환한다.
		else if (leftIdx == numberOfData) return leftIdx;
		// 왼/오 둘다 자식이 있기 때문에 비교를 진행한다.
		else
		{
			if (comp(vec[leftIdx], vec[rightIdx])) return leftIdx;
			else return rightIdx;
		}
	}

	// 데이터 삽입
	void Insert(const int data)
	{
		// 현재 인덱스를 가져옵니다.
		int currentIdx = GetHeapDataCnt() + 1;

		// 현재 인덱스가 1(부모가)이 아닐때 까지 반복한다.
		// 1이라서 부모 인덱스를 currentIdx가 가르키면 노드이기 때문에 반복하지 않는다.
		while (currentIdx != 1)
		{
			// 비교 조건에 따라 비교를 진행한다.
			if (comp(data, vec[GetParentIdx(currentIdx)]))
			{
				// 비교조건에 일치한다면 데이터를 스왑(변경)한다.
				vec[currentIdx] = vec[GetParentIdx(currentIdx)];
				currentIdx = GetParentIdx(currentIdx);
			}
			else break;
		}

		vec[currentIdx] = data;
		++numberOfData;
	}

	// 데이터 삭제후 삭제한 데이터 반환
	const int Delete()
	{
		// 삭제할 데이터 보관 (반환용)
		int retData = vec[1];

		// 마지막 인덱스의 값을 가져온다.
		int lastData = vec[GetHeapDataCnt()];

		int parentIdx = 1;
		int priChildIdx;

		// 부모를 기준으로 왼/오 중에 누가 우선순위가 높은 인덱스를 가져온다.
		// 왼쪽 자식이 없을 때 까지 반복한다.
		while (priChildIdx = GetPrioirityChildIdx(parentIdx))
		{
			// 비교조건에 따라 마지막 인덱스와 우선순위가 높은 인덱스의 값과 비교를 진행한다.
			// true 경우 마지막 인덱스가 우선순위가 높다는 뜻이기에 종료.
			if (comp(lastData, vec[priChildIdx])) break;

			vec[parentIdx] = vec[priChildIdx];
			parentIdx = priChildIdx;
		}

		vec[parentIdx] = lastData;
		--numberOfData;

		return retData;
	}

private:
	std::vector<int> vec;
	bool (*comp) (int, int);

public:
	int numberOfData{ 0 };
};

bool Less(const int a1, const int a2)
{
	return a1 < a2;
}

bool Greater(const int a1, const int a2)
{
	return a1 > a2;
}

int main()
{
	srand(time(NULL));

	Heap* heap = new Heap(heapSize, Greater);
	for (int i = 0; i < 50; ++i)
	{
		heap->Insert(rand() % 2000 + 1);
	}

	for (int i = 0; i < 50; ++i)
	{
		cout << heap->Delete() << " ";
	}
	cout << endl;

	cout << heap->numberOfData << endl;

	delete heap;
	return 0;
}