태그 보관물: data structure

힙(Heap) – 자료구조 (Swift)

heap은 일종의 바이너리트리로, 단일 배열을 이용해서 구현하며, 각 노드간의 포인터를 가지지 않는다. 트리는 내부적으로 부분적으로 정렬된 상태를 유지한다. 따라서 루트 요소를 꺼내면 정렬된 상태를 얻을 수 있다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다.

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

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

배열의 인덱스가 0부터 시작한다고 가정하면, 다음과 같은 방식으로 배열을 이진트리로 바꿀 수 있다.

  1. 인덱스 0인 요소가 루트가 된다.
  2. 루트의 왼쪽 자식의 인덱스는 1 (0 * 2 + 1), 오른쪽 자식은 오른쪽 자식은 2 (0 * 2 + 2)가 된다.
  3. 특정 인덱스의 부모요소의 인덱스는 (i – 1) / 2 로 구할 수 있다.

힙에 원소를 추가하면 배열의 맨 뒤에 원소를 붙이고, 해당 자리에서 부모보다 그 원소가 작으면 부모와 위치를 교환한다. 이 과정을 더 이상 올라갈 수 없을 때 까지 반복하면 된다.

힙에서 루트를 꺼내는 경우에는 배열의 맨 마지막 요소를 루트 자리에 넣는다. 그런다음 좌/우 자식 중에서 더 작은 요소가 자신보다 작으면 위치를 교환한다. 이 과정을 더 이상 계속할 수 없을 때까지 반복한다.

기본 구성

힙의 기본구성은 데이터를 저장할 배열과, 각 원소간의 순서를 비교할 평가함수이다. 이 둘은 외부에 노출될 필요는 없다. T가 Comparable 프로토콜을 따르는 타입이어도 되지만, 여기서는 커스텀한 비교 장치를 따로 가질 수 있도록 한다.


public struct Heap<T> {
    public typealias Comparator = (T, T) -> Bool
    private var __isOrderedBefor: Comparator
    private var elements: [T] = []

    init(comparator: Comparator) {
        __isOrderedBefor = comparator
    }
}

프로퍼티

힙이 비어있는지, 가장 상위에 올라와 있는 요소가 무엇인지와 같은 프로퍼티도 만들어준다. 물론 힙이 비어있는 경우 이 값은 nil이 될 수 있다.


var isEmpty: Bool { return elements.isEmpty }
var peak: T? { return elements.isEmpty ? nil : elements[0] }

그런데 위에서 정의했듯이 peak 은 그냥 배열의 .first 아닌가.


var peak: T? { return elements.first }

이렇게 수정한다. Continue reading “힙(Heap) – 자료구조 (Swift)” »

Parse Tree

이진트리 애플리케이션

파스 트리

트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다.

http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png

다음은 간단한 수학식을 트리로 표현한 것이다.

             *
           /   \
          +     -
         / \   / \
        7   3  5  2

> ( 7 + 3) * ( 5 - 2 )

Continue reading “Parse Tree” »