Heap

개요

 힙이란 힙 속성을 충족하는 완전 이진 트리 형태의 자료구조로, 최소값이나 최대값을 빠르게 찾아내는데 유용하다.

특징

힙 속성

 간단하게 말하자면 부모와 자식 간에 대소관계가 일정할 것을 조건으로 하는 것이다.
 트리의 형태로 보자면, 부모 노드 vs 두 자식 노드의 관계에서 어느 한 쪽이 작던지, 크던지 해야하는 것이다(자식 노드간의 대소는 가리지 않는다). 이런 조건으로 인해, 힙 속성을 충족하는 트리는 첫번째 노드(Root Node)가 가장 작거나, 큰 값을 가지게 된다.
 꼭 숫자의 대소를 따지지 않더라도 조건의 일정함이 유지된다면 힙 속성을 충족한다고 할 수 있다.

완전 이진 트리

 트리의 모든 레벨에 자식 노드가 채워져 있고, 가장 아래층에는 가장 왼쪽부터 노드가 채워져 있는 상태를 완전 이진 트리라고 한다.

 마지막 층의 자식 노드가 하나만 있더라도, 왼쪽 노드들이 전부 채워져 있다면 완전 이진 트리라고 부른다.

마지막 층 노드가 왼쪽부터 채워지지 않았으므로 완전 이진 트리가 아니다

자식 노드가 하나 뿐이지만 왼쪽부터 채워졌으므로 완전 이진 트리다

 

삽입/삭제를 해도 순위를 유지한다

 힙 속성을 유지해야 하기 때문에, 삽입과 삭제에 O(log n)이라는 시간이 소요된다(배열 리스트는 O(n)이니 이쪽이 더 빠르다). 삽입/삭제에 걸리는 시간이 길지 않은데, 항상 최소/최대값이 루트 노드에 저장되므로 특정 상황에서 유리하다고 할 수 있다.

메모리를 낭비하지 않는다

 배열로도, 연결 리스트로도 구현할 수 있기 때문에, 힙을 사용하는 데 있어 추가적인 메모리를 할당받을 필요가 없다.

어떤 때에 쓰이나

 우선순위 큐를 구현할 때 사용된다. 이미 많은 컴퓨터 언어에서 우선순위 큐의 형태로 힙 자료구조를 제공하고 있다.
 최소/최대값을 항상 알 수 있기 때문에, 정렬 알고리즘을 구현할 때에도 사용할 수 있다. 이를 힙 정렬이라고 하며, O(n log n)의 시간이 걸린다.