heap

heap은 완전 이진트리에 있는 노드 중에서 키값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만들어진 자료구조이다

최대 히프

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진트리
• 부모 노드의 키값 >= 자식 노드의 키 값
• Root 노드 : 키 값이 가장 큰 노드

최소 히프

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진트리
• 부모노드의 키값 <= 자식 노드의 키 값
• Root 노드 키 값이 가장 작은 노드

heap의 삽입 연산

1단계 : 완전 이진 트리의 조건이 만족하도록 다음자리를 확장
-노드가 n개인 완전 이진트리에서 다음 노드의 확장자리는 n+1번의 노드
-n+1 번 자리에 노드를 확장하고 , 그자리에 삽입할 원소를 임시 저장

2단계: 부모 노드와 크기 조건이 만족하도록 삽입 원소의 위치를 찾음

• 현재 위치에서 부모노드와 비교하여 크기 관계 확인
• 현재 부모노드의키값 >= 삽입 원소의 키값의 관계가 성립하지 않으면,
  현재 부모노드의 원소오 삽입원소의 자리를 서로 바꾼다

예시 1) : 17을 삽입하는 경우

예시 2): 23을 삽입하는 경우

heap 구현코드

heap 의 자료구조는 주로 배열을 이용한다
첫번째 index인 0은 사용하지 않을것이다(구현을 편하게 하기위함 )
특정 위치의 노드 번호는 새로운 노드가 추가되더라도 변하지 않는다

부모노드와 자식노드의 관계
왼쪽 자식의 인덱스 = 부모의 인덱스 2
오른쪽 자식의 인덱스 = 부모의 인덱스2 +1
부모의 인덱스 = 자식의 인덱스/2
인덱스는 정수형이기에 오른쪽 자식의 인덱스/2 를 하더라도 부모의 인덱스를 나타낼수있다

#include<iostream>
using namespace std;

#define MAX 8
template<typename T>
class Heap
{
private:
	int index;
	T buffer[MAX];
public:
	Heap()
	{
		index = 0;
		for (int i = 0; i < MAX; i++)
		{
			buffer[i] = NULL;
		}
	}
	void Insert(T data)
	{
		if (index >= MAX - 1)
		{
			cout << "Heap is Full" << '\n';
			return;
		}
		buffer[++index] = data;

		int child = index;
		int parent = child / 2;
		while (child > 1 && buffer[child] > buffer[parent])
		{
			swap(buffer[child], buffer[parent]);
			child = child / 2;
			parent = child / 2;
		}
	}
	T& Delete()
	{
		if (index <= 0)
		{
			cout << "Heap is Empty" << '\n';
			exit(1);
		}
		//root 제거 이니 buffer[1]; 
		T result = buffer[1];
		buffer[1] = buffer[index];
		buffer[index--] = NULL;
		int parent = 1;
		int child = parent * 2;
		while (parent * 2 <= index)
		{
			if (buffer[child] < buffer[child + 1]&&child+1<=index)// 자식 왼쪽 오른쪽 비교
			{
				child++;
			}
			
			if (buffer[parent] < buffer[child])swap(buffer[parent],buffer[child]);
			else break;
			parent = child;
			child = parent * 2;
		}
		return result;
	}
	void Print()
	{
		for (T element : buffer)
		{
			cout << element << ' ';
		}
		cout << '\n';
	}
};
int main()
{
	Heap<int>heap;
	heap.Insert(10);
	heap.Print();
	heap.Insert(20);
	heap.Print();

	heap.Insert(30);
	heap.Print();

	heap.Insert(40);
	heap.Print();

	heap.Insert(50);
	heap.Print();

	cout << "\n\n 삭제 과정\n\n";
	for (int i = 0; i < 5; i++)
	{
		cout << heap.Delete() << '\n';
		heap.Print();

	}
	return 0;
}

삽입과정

삽입은 다음과 같이 진행이 된다

삭제과정

heap 은 최댓값 heap 일경우 최댓값이 삭제되고 최솟값 heap 일경우 최솟값이 삭제되어야한다. 즉 루트가 지워져야한다


삽입과정은 마지막 인덱스와 루트인덱스의 값을 바꾸어준다 이후 마지막 인덱스의 노드를 null로 만들어 50을 삭제해준다 최댓값 heap 이 유지되기위해 위의 root 에서 부터 자식노드들과 비교하여 루트의 값이 자식노드의 값보다 작다면 swap을 해준다