자료 구조 Heap와 구현하기 (C++)

설명 :

 

최대 힙 (Max heap)

 

Heap의 구조

힙은 큐에서 변형된 것이라고 생각하면된다.

Priority Queue(우선순위 큐)라고 불린다.

큐가 앞으로 빼고 뒤로 넣는 자료 구조(First in First out)이면,

우선순위 큐는 그렇지 않고, 우선순위를 가진다.

 

힙(Heap)은 크게 두 가지로 나뉜다.

 

1. 최대 힙 : 루트 노드에서 단말 노드까지 우선순위가 높은 순서대로 내려오는 것

2. 최소 힙 : 루트 노드에서 단말 노드까지 우선순위가 낮은 순서대로 내려오는 것

 

위 사진을 배열로 나타내면 [11 , 7, 10 , 1, 3, 5, 9]와 같다.

 

여기서 자료를 넣는 방법과 빼는 방법을 구현해야 하는데 알고 있어야 하는 공식은 다음과 같다.

 

자식 노드에서 부모 노드로 가는 공식 : (Index-1)/2

부모 노드에서 왼쪽 자식 노드로 가는 공식 : 2 * Index + 1

부모 노드에서 오른쪽 자식 노드로 가는 공식 : 2 * Index + 2

 

다음은 시간복잡도에 대하여이다.

 

Add : O(log n)

Delete : O(log n)

Top : O(1)

Build Heap : O(n)

 

코드 : 

Heap.cpp :

 

#include<iostream>
#define MaxSize 8;
using namespace std;

class Heap
{
private:
int size; //배열 크기
int number; //현재 들어간 개수
int* heap;
public:

Heap() //생성자 함수
{
size = MaxSize;
heap = new int[size];
number = 1;
}

void max_heapify(int i) //힙화 해주는 함수
{
int largest = i; //부모 노드
int left = 2 * i; //왼쪽 자식 노드
int right = 2 * 1 + 1; //오른쪽 자식 노드

//부모노드와 자식 노드 비교
if (left <= number && heap[left] > heap[i])
largest = left;
if (right <= number && heap[right] > heap[largest])
largest = right;

//위의 경우를 만족한다면 값을 서로 바꾸고 다시 자식노드를 기준으로 힙화
if (largest != i)
{
int just;
just = heap[i];
heap[i] = heap[largest];
heap[largest] = just;
max_heapify(largest);
}
}

void Enqueue(int val) //넣는 함수
{
if (number == size)
cout << "The Heap is Full!!" << endl;

else
{
int i = number;
heap[i] = val;
number++;
while (i > 1 && (heap[i / 2] < heap[i]))
{
int temp=heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = temp;
i = i / 2;
}
}
}

void Denqueue() //빼는 함수
{
if (number == 1)
cout << "The Heap is Empty!!" << endl;

else
{
heap[1] = heap[number-1];
number--;
max_heapify(1);
}
}

void Print() //출력하는 함수
{
cout << "출력" << endl;

for (int i = 1; i <number; i++)
{
cout << heap[i] << endl;
}

}

};

Main.cpp :

#include <iostream>
#include "Heap.cpp"

using namespace std;

int main()
{
Heap a;

a.Enqueue(3);
a.Enqueue(7);
a.Enqueue(10);
a.Enqueue(1);
a.Enqueue(2);
a.Enqueue(5);
a.Enqueue(6);
a.Enqueue(9);
a.Print();

a.Denqueue();
a.Denqueue();
a.Denqueue();
a.Denqueue();
a.Print();

a.Denqueue();
a.Denqueue();
a.Denqueue();
a.Denqueue();

return 0;
}

출력 결과 :