(Swift) – 힙(Heap) – 자료구조에 대해

heap은 일종의 바이너리 트리를 단일 배열을 이용해서 구현한 구조로,  부모 자식 간의 직접적인 참조를 갖지 않고 배열의 인덱스에 의해서 위치 관계를 파악한다. 특히 내부 배열의 상태는 부분적으로 정렬되는 것과 비슷한데, 항상 “맨 앞의 원소를 꺼내었을 때 그 값이 최대 혹은 최소가 된다”는 특성을 가진다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다. 주로 자료 구조에서는 최대/최소 힙, 바이너리 힙, 힙 큐 혹은 우선순위 큐와 같은 이름으로 불린다.

참고로 이 자료 구조의 파이썬 구현은 [우선순위 큐 혹은 최소/최대힙]에서 한 번 설명한 바 있다.

힙으로 할 수 있는 일은 다음과 같다.

  1. 우선순위 큐를 만든다.
  2. 힙 정렬 수행
  3. 변경가능한 집합의 최소값(혹은 최대값)을 빈번히 계산해야 할 때 유용하다. (특히 최단거리 탐색 시)

(Swift) – 힙(Heap) – 자료구조에 대해 더보기

우선순위 큐 혹은 최소/최대힙

우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다. 우선순위 큐 혹은 최소/최대힙 더보기