[자료구조] 이진힙[힙](heap)

힙(Heap)

힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기반으로 한 자료구조다. 따라서 완전 이진트리의 속성을 가지고 있다.

완전 이진트리의 특징
1. 마지막 레벨을 제외하고 모든 노드가 채워져있어야한다.
2. 노드는 왼쪽에서 오른쪽 방향으로 채워져야한다.

 

힙은 최대힙(Max Heap)과 최소힙(Min Heap)으로 구분할 수 있다.

 

최대힙은 부모노드가 항상 자식노드보다 큰값을 가지고 있기 때문에, 루트노드는 항상 트리의 최대값이게 된다!

최대힙(Max Heap) 예시

 

 

이와 반대로 최소힙은 부모노드의 값은 항상 자식노드보다 작기 때문에, 루트노드는 항상 트리의 최소값이게 된다!

이런 최대힙과 최소힙의 특성은 힙에 새로운 값이 추가되거나 삭제되어도 이러한 특성이 항상 유지되어야한다!!

최소힙(Min Heap) 예시

 

힙은 이진탐색트리와는 다르게 중복을 허용하고,

이진탐색트리에서는 왼쪽 오른쪽을 기준으로 큰값과 작은값을 구분했지만, 힙은 좌우간에는 제약이 없고 상하관계에서만 제약이 있다.

 

 

 

 

힙(heap)의 시간복잡도

힙은 완전이진트리를 기반으로 한 자료구조이기때문에

최대값 혹은 최소값을 빠르게 가져오는게 중요한 상황에서 사용할 수 있다!

힙에서 최대,최소값의 위치는 항상 루트노드에 있기때문에, 시간복잡도는 O(1)이 된다.

시간복잡도가 O(1)이라는것은 입력한 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘을 의미하기 때문에, 가장 짧은 시간이 걸린다고 생각하면 된다.

그치만, 찾는 연산과는 다르게 데이터 삽입,삭제는 O(logN)의 시간복잡도를 갖는다.

 

 

 

 

힙(heap)의 응용

힙의 대표적인 응용으로는 우선순위 큐(Priority Queue)가 있다.

일반적인 큐(Queue)는 먼저 들어온 데이터가 먼저 빠지게 되는, 선입선출(First-in-first-out) 구조이다.

그치만 우선순위 큐(Priority Queue)는 데이터가 들어온 순서에 상관없이, 우선순위가 높은 데이터순으로 처리되는 구조이다.

우선순위 큐의 대표적인 예로는 운영체제의 작업 스케쥴링이 있다.

예를들어 CPU가 처리해야할 task가 여러개있다고 가정할때, 데이터가 들어온 순서대로 처리하는 것이 아니라,

어떠한 기준을 두고 그 기준에서 우선순위가 높은 작업들을 먼저 처리하는것이다. 이때 우선순위는 작업의 중요도가 될수도있고, 예상 소요시간이 가장 짧은 작업을 기준으로 한다던지 다양한 기준이 될 수 있을것이다.

 

힙 정렬(Heap sort)

정렬중에서 자료구조 힙의 특성을 활용한 힙정렬(Heap sort)이 있다.

힙정렬 예시

 

위 그림을 보면 왼쪽처럼 정렬되지 않은 데이터가 무작위로 주어졌을때, 주어진 데이터로 힙(heap)을 구성하게 된다.

min heap으로 구성되어있는 것을 볼 수 있다.

여기서 루트값을 가져오는 pop연산을 수행하면, 항상 힙에 있는 최소값이 출력되기 때문에 오른쪽처럼 데이터가 순서대로 정렬된 것을 확읺라 수 있다.

min heap이 아니라 max heap이였다면 내림차순으로 정렬된 결과를 얻을 수 있을것이다.

 

 

힙을 배열로 표현

힙을 1차원 배열로 표현

 

힙은 완전이진트리이기 때문에 중간에 빈값이 없는 1차원 배열로 표현이 가능하다.

 

 

 

 

Heapify 연산

힙의 연산에 있어서 가장 핵심이 되는 연산은 Heapify 이다.

힙의 데이터가 삽입,삭제 될 경우에도, 힙의 최대힙,최소힙의 속성이 유지되야한다.

그래서 아래 그림과같은 min heap이 있을때 루트값보다 더 작은값인 데이터 1을 삽입하려고하면,

min heap의 루트값이 바뀌기 때문에 하위의 트리구조도 다시 재구조화를 시켜줘야한다.

min heap의 최소값인 루트노드 3의 값을 삭제하는 경우에도 루드노드를 다시 채워주면서 min heap의 특성이 유지되도록 재구조화 해줘야한다.

이렇게 힙을 재구조화해주는 연산을 Heapify연산 이라고 한다.

 

 

 

 

데이터 삽입

먼저 최소힙에서 데이터가 삽입될때 연산이 어떻게 처리되는지 예시를 통해 볼것이다.

 

위 그림과 같은 min heap구조에서 데이터 1을 삽입한다고 가정해볼것이다.

힙은 완전이진트리의 형태를 유지해야 되기 때문에 일단 leaf노드에 제일 먼저 데이터를 삽입을 하게된다.

이 트리에서는 7의 오른쪽 자식노드에 1을 삽입하게 될것이다

 

제일먼저 leaf노드에 데이터삽입

 

이렇게 먼저 leaf노드에 데이터를 삽입하고, 이 힙이 min heap의 조건을 만족하는지 확인을 한다.

만약 최소힙(min heap)의 조건을 충족한다면 더이상 연산을 할 필요가 없기때문에 삽입연산을 종료한다.

 

하지만 지금과 같은 경우에는 min heap의 조건을 만족하지 못하기 때문에,

삽입된 노드를 부모노드와 바꿔주는 연산을 해야한다!!

여기서는 1과 7의 위치가 바뀌게 될것이다.

 

삽입된 노드를 부모노드와 바꿔주기

 

이렇게 삽입된 노드와 부모노드를 바꿔준 후에, 다시 최소힙(min heap)의 조건을 만족하는지 확인한다.

아직 최소힙의 조건을 충족하지 못하기 때문에, 한번 더 부모노드와 값을 바꿔준다.

1의 부모노드는 3이기때문에, 1과 3의 위치가 바뀌게 될것이다.

 

삽입된 노드를 부모노드와 바꿔주기

 

min heap의 조건을 충족하는지 확인해보면, 만족하는 것을 확인할 수 있다.

따라서 min heap의 조건을 충족하기 때문에 삽입연산을 종료하게 된다.

 

따라서 힙의 삽입연산을 할때는

먼저 leaf노드에 데이터를 추가한 다음에, 추가한 노드가 heap의 조건을 만족하는지 확인하고 만족할때까지 부모노드와 값을 바꾸는 동작을 계속 진행하는 과정으로 삽입연산이 진행된다.

max heap의 경우에도 부등호의 방향만 반대로 바뀌고 동일한 방법으로 데이터의 삽입이 이뤄진다.

 

 

 

 

데이터 삭제

힙은 최소값이나 최대값을 빠르게 찾아내기위한 자료구조이기 때문에, 최소힙이든 최대힙이든 루트노드에서만 삭제연산이 이뤄지는 경우에 대해서 알아볼것이다.

최대힙(max heap)에서 데이터 삭제를 하는 과정을 살펴보겠다.

 

 

위의 그림에서 루트노드인 9를 삭제해볼것이다.

여기서도 역시 최대힙의 속성이 유지되어야하기 때문에, 완전이진트리의 가장 마지막에 위치한 노드인 5를 루트노드로 가져오면서 원래 루트노드였던 9를 삭제한다.

 

 

5를 누트노드로 가져오고, 기존 루트노드였던 9삭제

 

 

이제는 삽입할때와 비슷하게, 힙의 조건을 만족하는지 확인하고 조건을 만족할때까지 자식노드와 위치를 바꿔주면 된다.

삽입할때는 부모노드와 자리를 바꿨다면, 삭제할때는 자식노드와 자리를 바꾸면서 heapify의 연산을 한다고 보면 된다!!

 

지금 그림을 봤을때, 방금 들어온 루트노드 5의 값이 max heap의 조건을 만족하지 않기 때문에

자식노드인 7과 위치를 바꿔준다.

 

삽입된 노드와 자식노드 바꿔주기

 

이렇게 하고나서 다시 힙의 조건을 만족하는지 확인해야할것이다.

max heap의 조건을 만족하기때문에 삭제연산이 종료되게 된다.

 

 

 

 

힙(heap)의 시간복잡도

위에서 잠깐 말했듯이 힙에서 최소값, 최대값을 찾는 연산자체는 항상 루트에 있는 값이 되기때문에 이때의 시간복잡도는 O(1)이 된다.

하지만 힙에서 데이터의 삽입,삭제 연산을 할때는 이진트리에 데이터 N개가 있을때 1/2씩 인덱스를 줄여나가면서 삽입,삭제의 위치를 찾아나가기 때문에, 이때 시간복잡도는 O(logN)이 된다!!