자료구조 - 힙(Heap) 그림으로 쉽게 이해하기

자료구조 - 힙(Heap) 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로

자료구조 - 힙(Heap) 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.

그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

바로 시작하겠습니다.

 

 

 

 

- 힙(Heap)

이번 포스팅에서는 힙(Heap)에 대해서 알아보겠습니다.
우리가 앞으로 다룰 힙은 자료구조에서의 힙을 의미하지만 자바에서 사용하는 메모리 영 역중에 '힙'이라는 메모리 공간이 있다는 것을 알고 계시면 좋습니다. 동일하게 '힙'이라는 용어를 사용하지만 아예 다른 개념이기 때문에 헷갈리시면 안됩니다. 그래서 나중에 면접에서 혹시

 

"자바 메모리 공간의 힙 영역에 대해서 설명해보세요"

 

라고 하면 자료구조의 힙을 말하면 안되고 자바 메모리 영역의 힙에 대한 답을 해야 합니다.

다시 한 번 말씀드리지만 자료구조의 힙과 자바 메모리 영역의 힙은 같은 용어를 사용하지만 아예 다른 개념입니다.

추가로 자바 메모리 공간에는 힙 말고도 스택이라는 영역도 있습니다. 스택도 앞에서 배운 자료구조 스택과는 다른 개념이기 때문에 헷갈리지 않도록 합니다.

 

 

- 힙(Heap)의 특성

자, 이제 오늘 다루게 될 자료구조 힙은 이진트리중에서도 완전 이진트리의 속성을 가지고 있습니다.

힙은 최대 힙 Max Heap과 최소 힙 Min Heap으로 구분할 수 있습니다. 최대 힙은 부모노드가 항상 자식 노드 보다 큰 값을 가지고 있기 때문에 루트 노드는 항상 트리의 최대값을 가지고 있게 됩니다. 반대로 최소 힙은 부모노드의 값은 항상 자식 노드보다 작기 때문에 루트 노드는 트리의 최소값이 들어있게 됩니다. 항상 그렇기 때문에 이 힙의 새로운 값이 추가되거나 삭제 되어도 특성은 유지가 되어야 합니다.

 

 

최대힙과 최소힙 트리 모양 예시

 

힙은 이진탐색트리와는 다르게 값의 중복을 허용하고, 또 이진탐색트리에서는 왼쪽 오른쪽을 기준으로 작은값과 큰값에 대한 제약이 있었다면, 힙은 좌우 노드간에는 값의 제약이 없고 상하 관계에서만 값의 제약을 받게 됩니다.

min heap과 max heap을 위의 그림으로 보면 왼쪽은 루트에 최소값 1을 가진 min heap인 것을 알 수 있습니다. 루트1의 자식인 6과 2는 둘다 부모노드보다 큰 값이 있게 되고, 6노드의 자식 노드들도 모두 6보다 큰 값이 있는 것을 볼 수 있습니다.

오른쪽은 루트에 가장 큰 값인 9를 가진 max heap입니다. 루트노드의 자식으로 자신보다 작은 값인 5와 7이 들어있고 5의 자식들도 5보다 작은 4와 2가 들어 있는 것을 볼 수 있습니다. 여기서 위아래가 아닌 좌우 노드간에는 크기관계의 제약이 없다는 것도 함께 확인 할 수 있습니다.

 

 

- 힙(Heap)의 시간복잡도

힙(Heap)은 자료구조에서 최대 혹은 최소값을 빠르게 가져오는게 중요한 상황에서 사용할 수 있습니다.
힙에서 최대 혹은 최대값의 위치는 항상 루트노드에 있기 때문에 시간 복잡도는 O(1) 상수값으로 찾을 수 있습니다. 찾는 연산과는 다르게 데이터의 삽입과 삭제는 O(logN)의 값을 갖는데 그 이유는 아래에서 다시 설명드리겠습니다.

 

 

- 힙(Heap)의 응용

힙의 대표적인 응용으로는 우선순위 큐 Priority Queue가 있습니다.
우리가 앞에서 배운 일반적인 큐는 먼저 들어온 데이터가 먼저 나가는 First in first out(FIFO)의 데이터 구조입니다. 우선순위 큐는 데이터가 들어온 순서에 상관없이 우선순위가 높은 데이터 순으로 처리하는 구조입니다. 대표적인 예시로는 운영체제의 작업 스케쥴링입니다. 우리가 뭔가 해야할 일이 있을 때 일이 들어온 순서대로 하는게 아니라 급한거라던지 혹은 중요도에 따라서 먼저 처리하는 것처럼 컴퓨터도 비슷한 과정으로 task를 처리하게 됩니다.

 

 

- 힙(Heap)의 응용 예시

예를들어 CPU가 처리해야 할 task가 여러개가 들어왔다고 가정해봅시다.
실제로 컴퓨터에서는 내가 실행시키고 있는 프로그램 외에도 백그라운드에서 돌고있는 프로그램 까지 생각한다면 더 많겠죠. 이렇게 처리해야 할 여러 작업들이 들어왔을 때 단순히 들어온 순서대로 처리하는 것이 아니라 특정 기준을 두고 그 기준에 있어서 우선순위가 높은 작업들을 먼저 처리하게 됩니다. 이때 우선 순위는 들어온 작업의 중요도가 될 수도 있고 혹은 예상 소요시간이 가장 짧은 작업을 기준으로 할 수도 있습니다. 그 외에도 다양한 기준들이 있을 수 있습니다. 중요한 것은 들어온 순서가 아닌 데이터 간에 우선순위를 두어서 그 우선순위대로 처리한다는 점입니다.

 

힙정렬 예시

- 힙 정렬 (Heap sort)

우선순위 큐 말고도 자료구조 힙의 특성을 이용한 힙 정렬 Heap sort라는 것이 있습니다.
위 그림에서 보면 왼쪽처럼 정렬되지 않은 데이터가 무작위의 순서로 주어졌을 때 주어진 데이터로 힙을 구성하게 됩니다. 가운데 그림을 보면 min heap이 구성된 것을 볼 수 있죠. 여기서 루트의 값을 가져오는 pop연산을 수행하게 되면 항상 힙에 있는 최소값이 출력되기 때문에, 데이터가 순서대로 정렬된 결과를 얻을 수 있습니다. 여기서 min heap이 아닌 max heap을 구성하면 내림차순된 결과를 얻을 수 있게 되겠죠.

 

 

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

 

 

- 힙을 배열로 표현하기

힙은 완전이진트리이기 때문에 중간이 빈 값이 없는 1차원 배열로 표현이 가능합니다.
이때 배열의 0번째 인덱스부터 채우게 되지만 앞에서 설명드린 노드탐색의 용이성 때문에 보통 1번 인덱스부터 루트값을 채웁니다. 그럼 어느 특정 인덱스에 위치한 노드의 부모노드는 자신의 인덱스를 2로 나눈 인덱스에서 찾을 수 있고, 왼쪽 자식노드는 자신의 인덱스 곱하기2, 오른쪽 자식노드는 오른쪽 자식노드는 인덱스에 곱하기2 +1의 위치에 존재합니다.

 

 

heapify 연산

 

- 힙의 연산 Heapify

힙에 있어서 가장 핵심이 되는 연산은 Heapify입니다.
힙의 데이터가 추가가 되거나 삭제가 될 경우에도 앞에서 설명드린 힙의 데이터 최대힙(max heap), 최소힙(min heap)의 속성이 유지되어야 합니다. 그래서 그림과같은 min heap이 있을 때 루트값보다 더 작은 값인 데이터 1을 힙에 삽입하려고 한다면은 min heap의 루트값이 바뀌면서 하위의 트리 구조도 다시 재구조화를 시켜줘야합니다. 마찬가지로 min heap의 최소값인 루트 노드의 3 값을 삭제할 경우 루트 노드를 다시 채워주면서 min heap이 유지 될 수 있도록 해야 합니다. 이렇게 힙을 재구조화 해주는 연산을 heapify라고 합니다.

 

 

힙의 데이터 삽입

 

- 힙의 데이터 삽입

먼저 최소힙(min heap)에서 데이터가 삽입될 때 힙 내부에서 어떻게 처리되는지 알아보겠습니다.
위 그림과 같은 min heap에서 데이터 1을 min heap에 추가한다고 가정해보겠습니다. 힙은 완전이진트리의 형태를 유지해야하기 때문에 일단 leaf노드에 제일 먼저 데이터를 삽입을 하게 됩니다. 이 트리에서 완전이진트리 형태를 유지하는 leaf노드의 위치는 데이터 7이 들어있는 노드의 오른쪽 자식노드가 되겠죠. 그래서 일단 leaf노드에 데이터를 삽입한 후에 이 힙이 min heap의 조건을 만족하는지 확인합니다.

 

 

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

 

 

만약 최소힙(min heap)의 조건을 충족한다면 추가적인 연산을 할 필요가 없기 때문에 삽입 연산을 바로 종료합니다.

하지만 지금 이 경우에서는 추가된 노드가 min heap의 조건을 만족하지 못하고 있기 때문에 다음 단계로 넘어가게 됩니다.

 

다음 단계는 삽입된 노드를 부모 노드와 바꿔주는 연산을 하게 됩니다.

여기서는 1과 7의 데이터의 위치가 바뀌게 되겠죠. 그 다음에 다시 최소힙(min heap)의 조건을 만족하는지 확인합니다. 

 

 

삽입된 노드를 부모 노드와 바꿔주는 연산

 

 

여기서 최소힙의 조건을 충족한다면 삽입 연산을 종료하고, 그렇지 못하다면 다시 부모노드와 값을 바꾸게됩니다.

그런데 여전히 최소힙(min heap)의 조건을 충족하지 못하기 때문에 한 번더 부모노드와 값을 바꾸게 됩니다. 그러면 이번에는 1과 3의 위치가 바뀌게 되겠죠. 그 다음으로 다시 min heap의 조건을 충족하는지 확인합니다.

 

 

1과 3의 위치가 바꾼 모습

 

 

이번에는 최소힙의 조건을 만족하고 있기 때문에 삽입 연산을 종료하게 됩니다.

그래서 삽입 연산을 할 때에는 우선 leaf노드에 데이터를 추가한 다음에 추가된 노드가 heap의 조건을 만족하는지 확인을 해서 힙의 조건을 만족할 때까지 부모노드와 값을 바꾸는 동작을 계속하게 됩니다. max heap도 부등호의 방향만 반대로 바뀌고 동일한 방법으로 데이터의 삽입이 이뤄지게 됩니다.

 

 

- 힙의 데이터 삭제

이번에는 힙에서 데이터의 삭제 연산을 알아보도록 하겠습니다.
힙은 최소값이나 최대값을 빠르게 찾아내기 위한 자료구조이기 때문에 최소힙(min heap)이든 최대힙(max heap)이든 루트 노드에서만 삭제연산이 이뤄지는 케이스에 대해서 알아보겠습니다. 이번에는 max heap을 예시로 들어보겠습니다.

 

 

맥스힙 예시

여기서도 완전이진트리가 유지되어야 하는 조건은 동일하기 때문에 완전 이진트리의 가장 마지막에 위치한 노드를 루트로 가지고 오면서 마지막 노드를 삭제합니다. 그러면 아래 그림과 같은 모양으로 max heap의 값이 변경이 됩니다.

 

 

max heap의 값이 변경된 모습

 

이제 이 상태에서 삽입할 때와 동일하게 힙의 조건을 만족하는지 확인하고 조건을 만족하지 않는다면 조건을 만족할 수 있게끔 자식노드와 위치를 바꿔주면 됩니다. 삽입할 때는 부모노드와 자리는 바꾸었다면 삭제할 때는 자식 노드와 자리를 바꿔가면서 heapify의 연산을 한다고 보시면 됩니다.

 

이 경우에서는 방금 들어온 이 루트노드의 5의 값이 max heap의 조건을 만족하지 않기 때문에 자식 노드인 7노드와 위치를 바꿔주게 됩니다.

 

 

자식 노드인 7노드와 위치를 바꿔준 모습

 

그러면 이런식으로 최대힙(max heap)의 그림이 바뀌게 되고 다시 힙의 조건을 만족하는지 확인합니다.이때 힙의 조건을 만족하기 때문에 여기서 삭제 연산이 종료됩니다.

 

 

- 힙(Heap)의 시간복잡도

그리고 힙에서 최소값 혹은 최대값을 찾는 연산 자체는 루트에 있는 값만 가져오면 되기 때문에 시간복잡도는 O(1)입니다. 하지만 힙에서 데이터의 삽입과 삭제 과정에서는 이진트리에 데이터가 N개가 있을때 1/2씩 인덱스를 줄여나가면서 자신의 위치를 찾기 때문에 시간복잡도는 logN이 됩니다.

 

 

오늘은 이렇게 자료구조 - 힙(Heap) 그림으로 쉽게 이해하기에 대해서 알아보았습니다.

다음 포스팅도 더 쉽고 재밌는 포스팅으로 다시 돌아오겠습니다.

감사합니다.