[자료구조] Heap - 우선스택 큐

치치·2025년 1월 5일

자료구조

자료구조C++

목록 보기

12/17

Heap

힙을 저장하는 건 주로 배열로 구성한다
- 완전 이진트리의 한 종류로 우선순위 큐를 구현할 수 있는 자료구조
- 중복된 값을 허용한다 ( 이진탐색트리에선 불가하다)
- 주로 최대값과 최소값을 찾아낼때 사용된다
- 우선순위 큐 : 데이터들이 우선순위를 가지고, 우선순위가 높은 데이터가 먼저 나가는 구조

[힙의 주요 특징]

힙은 완전 이진트리 구조이기 때문에 왼쪽부터 차례대로 채워져있는 구조이다

- 왼쪽부터 차례대로 데이터가 들어온다
즉, 특정위치의 노드 번호가 새로운 노드를 추가하여도 변하지 않는다
- 새로운 노드는 항상 마지막의 줄의 왼쪽부터 채워지기 때문에, 기존 노드 순서가 유지가 된다!
- 아래의 사진을 보면 부모가 인덱스 1일 경우, 왼쪽 자식은 parent 2 인덱스이고, 오른쪽 자식은 parent 2 + 1 인덱스이다
- 이건 노드가 더 추가되어도 변하지 않고 유지되는 인덱스 번호이다
- parent가 갱신되어 [2]으로 가도 2의 자식은 부모의 2배, 2배 + 1이 된다

인덱스가 0부터가 아니라 1부터 시작한다

힙 자료구조의 구현을 쉽게 하기 위해서 0번째 인덱스는 사용하지 않는다 (비워둔다는 의미)
- 힙 자료구조를 배열로 구현할 것이기 때문에 배열로 구성해보면 아래의 그림처럼 나온다
- 이렇게 배열의 인덱스가 힙의 부모 - 자식 관계를 명확하게 정의 해준다 -> 배열의 인덱스가 위의 힙 트리 구조에서 확인된다

최소 힙

부모노드의 값이 항상 자식노드보다 작아야 한다
-> root가 제일 작은값이 된다 (최소값)

최대 힙

부모노드의 값이 항상 자식노드보다 커야한다
-> root가 제일 큰 값이 된다 (최대값)

최대 힙을 구하는 Heap 구현

template를 사용하여 클래스를 구현하였다
현재 들어온 값의 번호인 index 변수와 T타입 SIZE 크기의 배열 생성
생성자에서 초기화 해준다

#include <iostream>
#include <algorithm>
#define SIZE 8

using namespace std;

// Heap
// 최댓값 최솟값 구할때 사용
// 데이터를 뽑을때 노드 한번에 뽑을 수 있어서(인덱스) 상수시간

template <typename T>

class Heap
{
private:
	int index;
	T array[SIZE];

public:
	// 생성자
	Heap()
	{
		index = 0;

		for (int i = 0; i < SIZE; i++)
		{
			array[i] = NULL;
		}
	}

InSert( )함수 : 최대힙에서 값 삽입

void Insert(T data)
{
	// 인덱스가 사이즈보다 커지면 오버플로우
	if (index + 1 >= SIZE)
	{
		cout << "Heap OverFlow" << endl;
	}
	else
	{
		array[++index] = data;

		int child = index;
		int parent = child / 2;

		//  child가 부모보다 큰지 비교 (반복문), 크면 스왑
		// 자식은 무조건 부모보다 작아야함
		// 부모와 자식 노드 관계만 중요함

		// 힙 정렬
		while (child > 1)
		{
			if (array[child] > array[parent])
			{
				swap(array[parent], array[child]);
			}
			child = parent;
			parent = child / 2;
		}
	}
}

힙 오버플로우 조건이 index + 1 >= SIZE인 이유
-> 값을 넣는 범위가 [1] 부터 시작하기 때문에 index = 7 일 경우
7 + 1 >= SIZE 가 성립되기 때문에 힙 오버플로우가 발생한다
-> 쉽게 말하자면, 시작 위치가 [1] 즉, index + 1 범위부터 시작하기 때문이다
-> 원래라면 index >= SIZE 였겠죠
index의 가장 마지막 번호에 새로운 요소를 삽입한다
index값이 SIZE보다 작으면 새로 넣은 값을 부모의 값과 비교하면서 root쪽으로 이동한다
while(child > 1) 조건은 child 즉, 자식이 1보다 클 경우에 실행한다
-> child가 root가 아닐경우에 실행하는 것
-> 1은 root노드를 뜻하는 데, root노드는 부모가 없기 때문에 굳이 스왑을 할 이유가 없어서 child가 1 이상일때로 조건을 정했다
부모와 자식의 위치를 swap
child의 위치를 기존의 parent의 위치로 이동
-> 이동된 child 위치를 기준으로 새로운 parent를 정한다

Remove( )함수 : 최대힙에서 값 삭제

최대값이 root노드를 뽑아서 상수로 리턴한다
최대값을 가진 요소를 삭제하고, 삭제된 root 노드는 힙의 마지막 노드를 가져와서 재구성한다

// 최대값 뽑기 -> return 
const T& Remove()
{
	// 데이터가 없다면
	if (index <= 0)
	{
		cout << "Heap is Empty" << endl;
		exit(0);
	}

	else
	{
		// 임시변수 (담아주기)
		// 젤 마지막 노드를 가져와서 뺀 자리 덮어씌우기
		// 마지막 노드 자리는 NULL로 

		// 빼낸 값을 return 해야하기 때문에 임시변수 save 필요
		T save = array[1];

		array[1] = array[index];

		array[index--] = NULL;

		// 힙 정렬 (left = parent * 2 , right = parent * 2 + 1)
		int parent = 1;

		// 부모는 왼 오 둘중 큰 값과 스왑

		while (parent * 2 <= index)
		{
			int child = parent * 2;

			if (array[child] < array[child + 1])
			{
				child++;
			}
			if (array[child] < array[parent])
			{
				break;
			}
			else
			{
				swap(array[parent], array[child]);

				parent = child;
			}
		}
		return save;
	}

}

index가 0보다 작거나 같다는 것은 힙이 비어있다는 것
힙이 비어있지 않다면
-> root노드는 최대값이 들어있기 때문에 임시변수를 만들고 [1] 인덱스의 값을 저장시켜둔다 (root노드에 저장된 값)
-> root 노드에 마지막 index의 값을 대입시켜준다
-> 마지막 노드의 값을 NULL로 만들어주고 index를 감소시킨다 (현재 인덱스 6)
이 상태에서는 힙 구조의 규칙에 맞지 않는다
-> root노드가 제일 값이 커야하지만 지금 제일 작다
-> 따라서 하향로직을 실행해서 높은 값과 스왑해주는 과정이 필요하다
parent[ ] 는 root노드인 1 부터 시작
-> child은 parent * 2
while(parent * 2 <= index) 조건은 child가 index의 값보다 작을 경우 실행한다는 의미이다
-> 즉, 불만족하는 조건은 child가 index값을 넘어가는 경우인데 이러면 힙을 초과한다는 의미기 때문
예를 들어, 아래의 힙 구조는 처음에 parent값과 child값을 비교한 뒤 스왑해준다
-> parent의 위치와 child의 위치값이 갱신되어 변한다
-> child의 값은 6으로 index보다 작거나 같아서 반복문 실행이 가능하다
-> 하지만 다음 parent의 위치가 6이 되었을때 parent * 2가 12가 되면서 index값을 넘어버리기 때문에 조건이 거짓이 된다 (반복문 실행X)

Remove 조건식 하나씩 살펴보자

왼쪽 자식과 오른쪽 자식을 비교하여 오른쪽 자식이 더 큰 경우 child값을 증가
아래 사진의 경우 child의 값 30, child + 1의 값 40 으로 오른쪽 자식의 값이 더 큼

child를 오른쪽 자식으로 바꿔준다 child++

if (array[child] < array[child + 1])
{
				child++;
}

child값과 parent 값을 비교하여 부모가 더 크다면 힙 조건이 성립하기 때문에 break문으로 탈출한다
```
if (array[child] < array[parent])
{
				break;
}
```
만약 child의 값이 parent 값보다 크다면 서로의 값을 바꿔주어야 함
그리고 parent의 위치를 새로 바꿔주어야 한다
아래의 예시에서 child값이 부모보다 더 크기 때문에 서로 swap 해준 뒤 parent의 위치를 기존의 child 위치로 옮겨준다 (스왑된 값이 아래와 또 비교해야하기 때문이다)
새로운 parent의 위치가 정해졌으면 child값도 새로운 parent * 2의 위치가 된다
```
else
{
				swap(array[parent], array[child]);
				parent = child;
}
```
마지막으로 내가 save변수에 저장해두었던 기존의 root 노드 값인 최대값을 반환하면 된다

Show( ) 함수

힙을 배열로 저장했기 때문에 인덱스에 접근해서 값 바로 확인할 수 있다

void Show()
{
	for (int i = 1; i <= index; i++)
	{
		cout << array[i] << " ";
	}
}

메인 함수

데이터가 하나씩 들어갈때마다 즉시 값을 비교하고 스왑하여 힙 구조를 만들어간다
메인함수에서 10, 20, 30 데이터를 삽입하였고 구조는 아래와 같다

int main()
{
	Heap <int> heap;

	heap.Insert(10);
	heap.Insert(20);
	heap.Insert(30);
	heap.Show();

	cout << endl;

	// 큰거 부터 뽑힘
	cout << heap.Remove() << endl;
	cout << heap.Remove() << endl;
	cout << heap.Remove() << endl;

	heap.Show();

	return 0;
}