[Swift Collections] Heap

Swift-Collections 패키지가 나오고

다른 언어에는 있지만  Swift 에는 없어서 직접 구현해야했던 자료구조들 (deque, heap..) 이 제공되고 있다. 

 

[Swift Collections] deque 에 이어서 heap 을 살펴보자. 

마찬가지로 이미 해당 자료구조를 내장 모듈로 제공하던 python 과 함께 살펴보자. 

 

 

[1]  python 의 heap 

python은 heap 과  PriorityQueue (heap을 통해 구현) 를 모두 제공한다. 

 

 

# heap 

 

✓ 파이썬의 heap은 min heap 이다. 

(min heap = 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리)

 

✓ 즉 모든 k에 대해

   heap[k] <= heap[2*k+1]     // 왼쪽 

  heap[k] <= heap[2*k+2]     // 오른쪽 

  인 배열을 사용한다. 

 

✓  0부터 시작하는 인덱싱을 사용한다.  heap[0] 은 가장 작은 항목이다. 

 

✓  heappush, heappop 인터페이스는 힙 불변성을 유지하면서 연산을 한다. 

 

✓   힙을 만들려면,  []로 초기화된 리스트를 사용하거나, 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환 할 수 있다. 

from heapq import heappush, heappop

heap = []
heappush(heap, 4)
print(heap) # [4]

heappush(heap, 1)
print(heap) # [1, 4]

heappush(heap, 7)
print(heap) # [1, 4, 7]

min_pop = heappop(heap)
print(min_pop)  # 1
print(heap) # [4, 7]

min = heap[0]
print(min)  # 4
print(heap) # [4, 7]

 

from heapq import heapify

list = [7,1,4]
heapify(list)
print(list) # [1, 7, 4]

 

 

# 우선순위큐 

 

(priority_number, data) 튜플 기반이다. 

from queue import PriorityQueue

queue = PriorityQueue()
queue.put((3, 4))
queue.put((2, 1))
queue.put((1, 7))

print(queue.get()) # (1, 7)
print(queue.get()) # (2, 1)
print(queue.get()) # (3, 4)

 

우선순위를 안넣으면 heap과 완전 같은 동작이다.  (작은 숫자일 수록 우선순위가 높다고 판단) 

from queue import PriorityQueue

queue = PriorityQueue()
queue.put(4)
queue.put(1)
queue.put(7)

print(queue.get()) # 1
print(queue.get()) # 4
print(queue.get()) # 7

 

또한 pop을 안하고 우선순위가 가장 높은 값을 구하려면 

queue.queue 로 접근해야한다. 

from queue import PriorityQueue

queue = PriorityQueue()
queue.put((3, 4))
queue.put((2, 1))
queue.put((1, 7))

print(queue.queue[0]) # (1, 7)

 

[2] Swift 의 Heap 

 

이제 Swift Collections의 Heap을 살펴보자 (참고: 문서)

우선 python처럼 PriorityQueue 는 같이 제공되지 않고 있다. 

또한 글쓰는 기준 1.0.4 버전이 최신인데, 여기에 아직 HeapModule이 포함안되어서 브랜치 기준으로 pacakge import 해줬다.

 

✓ Swift의 Heap은 min-max heap 이다

   (min-max heap은 min heap과 max heap을 합친 heap으로 min level, max level이 반복되는 heap이다.  그림 참고) 

 

✓  insert, popMin, popMax 인터페이스는 힙 불변성을 유지하면서 연산을 한다. 

 

✓  sequence 기반 이니셜라이저와 insert 메소드를 제공한다 (코드 참고) 

     heapfiy 가 internal 이라 직접 호출할 수는 없고 array 를 heap으로 변환하면 내부적으로 heapfiy 가 불리는 셈이다. 

import HeapModule

var heap = Heap<Int>()

heap.insert(4)
heap.insert(7)
heap.insert(1)

print(heap.min()) // Optional(1)
print(heap.max()) // Optional(7)

print(heap.popMin()) // Optional(1)
print(heap.popMax()) // Optional(7)

 

import HeapModule

let array = [4,7,1]
let heap = Heap(array)
print(heap.min()) // Optional(1)

 

시간복잡도는 다음과 같이 나와있는데 

기본적인 heap complexity 와 동일하다.

 

 

 

 

[3]  정리

	python	swift
Heap	min heap	min-max heap
PriorityQueue	제공	제공 X
heapfiy	public 인터페이스	internal 인터페이스. 이니셜라이저 / insert 같은 public 인터페이스를 이용하면 heapfiy를 수행할 수 있음
시간복잡도	기본적인 Heap 시간복잡도	기본적인 Heap 시간복잡도