(Swift) – 힙(Heap) – 자료구조에 대해
heap은 일종의 바이너리 트리를 단일 배열을 이용해서 구현한 구조로, 부모 자식 간의 직접적인 참조를 갖지 않고 배열의 인덱스에 의해서 위치 관계를 파악한다. 특히 내부 배열의 상태는 부분적으로 정렬되는 것과 비슷한데, 항상 “맨 앞의 원소를 꺼내었을 때 그 값이 최대 혹은 최소가 된다”는 특성을 가진다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다. 주로 자료 구조에서는 최대/최소 힙, 바이너리 힙, 힙 큐 혹은 우선순위 큐와 같은 이름으로 불린다.
참고로 이 자료 구조의 파이썬 구현은 [우선순위 큐 혹은 최소/최대힙]에서 한 번 설명한 바 있다.
힙으로 할 수 있는 일은 다음과 같다.
- 우선순위 큐를 만든다.
- 힙 정렬 수행
- 변경가능한 집합의 최소값(혹은 최대값)을 빈번히 계산해야 할 때 유용하다. (특히 최단거리 탐색 시)