[자료구조] Heap (힙)

 

Heap 이란?

 

Heap 자료구조는 이진트리 중에서도 완전이진트리의 속성을 가지고 있다. 

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

 

힙은 이진탐색트리와는 다르게 값의 중복이 허용되고, 좌우 노드 간의 관계가 아닌 상하 관계에서만 값의 제약을 받게 된다.

 

힙의 시간 복잡도

 

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

힙에서 최대 혹은 최소값의 위치는 항상 루트노드에 있기 때문에 시간 복잡도는 O(1)로 찾을 수 있다.

그런데 삽입할 때는 조정을 해주기때문에 O(logN)의 값을 가짐.

 

우선순위 큐 Priority Queue

 

일반적인 큐는 먼저 들어온 값이 먼저 나가는 FIFO 규칙을 따르지만 우선순위 큐는 데이터가 들어온 순서에 상관없이 우선순위가 높은 데이터 순으로 처리하는 구조이다. 대표적인 예시로는 운영체제의 작업 스케줄링이 있다. 우리가 뭔가 해야 할 일이 있을 때 일이 들어온 순서대로 하는 게 아니라 중요도에 따라서 처리해야 할 때 우선순위 큐로 처리를 한다.

 

힙 정렬

 

힙의 특성을 이용한 정렬

정렬되지 않은 어떤 데이터가 주어졌을 때 이 데이터들로 힙을 구성하고 데이터의 길이만큼 힙에서 pop연산을 하면 결과는 오름차순이든 내림차순이든 항상 순서대로 정렬된 결과를 얻을 수 있다.

 

삽입과 삭제

 

힙에 데이터가 삽입되거나 삭제 될 경우에도 힙의 속성 (Max or Min)의 속성이 유지되어야 한다.

그럼 아래 그림 같은 최소 힙에  1이 삽입되는 경우는 어떨까??

 

 

 

일단 힙은 완전이진트리이므로 적절한 리프노드에 값을 삽입해야 한다.

 

유일한 빈자리인 6의 오른쪽에 1이 삽입된다.

하지만 최소 힙의 규칙에 따르면 자식노드에는 부모노드보다 작은 값이 올 수 없다.

따라서 1과 6의 위치를 아래처럼 바꿔준다.

 

 

하지만 아직도 루트노드인 3보다 1의 값이 작기 때문에 문제가 발생한다.

1과 3도 바꿔줘야 한다.

 

 

이 과정까지 하면 최소 힙의 규칙을 어기지 않고 1을 삽입한 것이다.

 

이런 식으로 삽입할 때 힙의 규칙에 맞지 않으면 부모와 자식 위치를 바꿔주는 연산을 해주면 될 것 같다.

 

그럼 삭제할 때는?

 

가장 작은 값인 1을 pop 하는 상황을 살펴보자.

 

 

1을 pop 하고 루트노드의 자리가 비었다.

그럼 리프노드 중에서 가장 마지막 값을 가져온다.

 

가장 마지막 값인 6을 가져왔다.

하지만 6이 자식 노드보다 크기 때문에 재조정을 해줘야 한다.

6과 3을 바꿔주고 조정이 끝난다.

 

이런 식으로 삭제는 루트 노드를 제거하고 리프노드 중 가장 마지막 값을 가져온 다음, 규칙에 맞게 조정해 주면 된다.

 

주의점?

 

자료구조의 Heap과 자바 메모리 상의 Heap은 다르다!!!

 

https://devkingdom.tistory.com/226