Swift에서의 힙(Heap) 자료구조

 

완전 이진 트리(Complete Binary Tree) 구조를 가지며, 우선순위 큐(Primary Queue)를 구현하는 데 자주 사용된다

• 완전이진트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 노드는 가장 왼쪽에 있는 트리
• 우선순위 큐: 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리되는 큐

 

 

Swift의 기본 자료구조에는 Heap이 포함되지 않으므로 직접 구현해야 한다

힙의 종류

• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드보다 항상 작거나 같음 → 가장 작은 값이 루트에 위치
• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드보다 항상 크거나 같음 → 가장 큰 값이 루트에 위치

 

https://www.geeksforgeeks.org/introduction-to-min-heap-data-structure/     

 

 

힙의 주요 연산

1. 삽입(insert): 새로운 요소를 추가하고 힙 속성을 유지하도록 정렬 (O(logN))
2. 삭제(pop): 루트 노드를 삭제하고 마지막 노드를 루트로 옮긴 후 정렬 (O(logN))
3. 조회: 루트 노드를 반환 (O(l))

 

 

데이터 스왑 애니메이션

MinHeap을 구현하기 전에 데이터 삽입, 제거를 트리로 표현해보면 더욱 쉽게 이해할 수 있다

아래 사이트에서 Heap에서 데이터 스왑 과정의 배열과 트리를 애니메이션으로 확인할 수 있다

 

https://www.cs.usfca.edu/~galles/visualization/Heap.html

Heap Visualization

 

 

 

MinHeap 구현

struct MinHeap {
    // 힙을 저장할 배열 (1-based index 사용)
    private var elements = [Int]() 
    
    // 현재 힙에 저장된 요소 개수 (0번째 인덱스를 제외)
    var count: Int {
        elements.count - 1  // 1-based index를 사용하므로 0번째 인덱스를 제외한 개수를 반환
    }
    
    // 힙이 비어있는지 여부 반환
    var isEmpty: Bool {
        count == 0  // 요소가 없으면 true
    }

    // 1-based index를 유지하기 위해, 0번째 인덱스를 채워줌
    init() { elements.append(0) }  
}

0-based index를 사용하면 부모 인덱스와 자식 인덱스를 구할 때 계산이 복잡해지므로,

편의를 위해 1-based index를 사용했다

1-based index를 유지하기 위해, init에서 0번째 인덱스를 채워주었다

 

Insert

힙에서 데이터 삽입은 배열의 마지막에 데이터를 추가하고

부모 노드와 비교하여 필요시 교환하는 방식으로 힙의 구조를 유지한다

MinHeap에서는 추가한 데이터가 부모 노드보다 작으면 교환하여 위로 올리고

MaxHeap에서는 추가한 데이터가 부모 노드보다 크면 교환하여 위로 올린다

반복문 조건으로 parentIndex > 0 를 추가하여 0번째 인덱스에 대한 예외 처리

    // 삽입
    mutating func insert(_ value: Int) {
        elements.append(value) // 새로운 값을 배열 끝에 추가
        
        var currentIndex = count     // 현재 삽입된 노드의 인덱스
        var parentIndex = currentIndex / 2 // 부모 노드의 인덱스 (완전 이진트리에서 부모 = 현재 인덱스 / 2)
        
        // 부모보다 작으면 계속 위로 이동
        // // Heapify Up (삽입 시 재정렬)
        while parentIndex > 0 && elements[currentIndex] < elements[parentIndex] {
            elements.swapAt(currentIndex, parentIndex) // 부모보다 작으면, 현재 노드와 부모 노드 교환
            currentIndex = parentIndex      // 현재 노드를 부모 노드로 이동
            parentIndex = currentIndex / 2  // 새로운 부모 노도 갱신
        }
    }

 

Pop

MinHeap에서의 pop은 최소값 꺼내기, MaxHeap에서는 최대값을 꺼낸다

루트 노드(최소값 또는 최대값)와 마지막 노드의 위치를 교환하고

교환한 최소값 또는 최대값을 배열에서 제거 후 반환한다

힙을 유지하기 위해 새로운 루트 노드를 다시 자식 노드와 비교하여 교환을 반복하면서 힙을 유지한다

MinHeap에서는 루트 노드의 자식 노드가 루트 노드보다 작으면 교환하는 작업을 반복한다

    // 최소값 삭제
    mutating func pop() -> Int? {
        if isEmpty { return nil } // 힙이 비어있으면 nil 반환
        
        elements.swapAt(1, count)   // 루트 노드(최소값)와 마지막 노드 위치 변경
        let returnValue = elements.removeLast() // 최소값을 꺼낸 후 배열에서 제거
        var currentIndex = 1    // 루트 노드부터 재정렬 (루트 노드로 올라온 값의 위치를 찾아줌)
        
        // Heapify Down (삭제 시 재정렬)
        while true {
            let leftChildIndex = 2 * currentIndex // 왼쪽 자식 노드 인덱스
            let rightChildIndex = 2 * currentIndex + 1 // 오른쪽 자식 노드 인덱스
            var swapIndex = currentIndex    // 현재 위치에서 교체할 인덱스
            
            // 왼쪽 자식이 존재하고, 현재 노드보다 작으면 교체 대상으로 설정
            if leftChildIndex < count && elements[leftChildIndex] < elements[swapIndex] {
                swapIndex = leftChildIndex
            }
            
            // 오른쪽 자식이 존재하고, 현재 노드보다 작으면 교체 대상으로 설정
            if rightChildIndex < count && elements[rightChildIndex] < elements[swapIndex] {
                swapIndex = rightChildIndex
            }
            
            if swapIndex == currentIndex { break } // 현재 노드보다 작은 자식 노드가 없으면 종료
            elements.swapAt(currentIndex, swapIndex) // 현재 노드와 가장 작은 자식 노드 교환
            currentIndex = swapIndex // 현재 노드를 내려간 위치로 갱신
        }
        
        return returnValue // 제거된 최소값 반환
    }

 

 

 

아래는 MinHeap을 트리 구조로 표현한 그림이다

1-based index를 사용하기 위해 init에서 Int.max 값을 넣어두었다 (0번째 인덱스 채우기)

위 코드에서는 0으로 했지만, 아래에서는 Int.max로 진행

 

1. insert(1)
   • 부모 노드가 없기 때문에 1이 루트노드가 됨
2. insert(23)
   • 부모 노드인 1보다 23이 작지 않으므로 왼쪽 자식 노드가 된다
3. insert(10)
   • 10도 마찬가지로 부모 노드(1) 보다 작지 않으므로 오른쪽 자식 노드가 된다
4. insert(11)
   • 배열의 끝에 11을 추가하면 23의 왼쪽 자식 노드가 된다
   • 11이 부모노드(23)보다 작으므로 Swap을 진행한다
   • 23과 11이 Swap한 후 11의 부모노드(1)과 비교하지만, 부모노드보다 작지 않으므로 종료된다
5. insert(6)
   • 배열의 끝에 6을 추가하면 11의 오른족 자식 노드가 된다
   • 6이 부모노드(11)보다 작으므로 Swap한다
   • 6과 11을 Swap한 후 6의 부모노드(1)과 비교하지만, 부모 노드보다 작지 않으므로 종료한다
6. insert(-1)
   • 배열의 끝에 -1을 추가하면 10의 왼쪽 자식 노드가 된다
   • -1은 부모 노드(10)보다 작으므로 Swap한다
   • 스왑한 후 -1의 부모 노드인 1보다 -1이 작으므로 부모노드와 스왑한다
   • 결국 루트 노드가 -1이 되어 최소값이 1번째 인덱스가 되어 힙을 유지할 수 있다
7. pop()
   • 루트 노드가 항상 최소값이므로 -1과 배열의 마지막 10을 스왑한다
   • 스왑된 -1을 배열의 맨 마지막이므로 removeLast()를 통해 빠르게 제거된다
   • 스왑된 루트노드의 10은 힙을 유지하기 위해 다시 자식노드와 비교하여 작은 값과의 스왑을 반복한다
   • 자식 노드인 6과 1 중 작은 값으로 스왑하여 결과적으로 루트 노드에 1이 오게 된다
   • 만약 1 아래에 다른 노드들이 있었다면, 1과 스왑한 10은 다시 자식 노드와의 비교를 반복하게 된다

 

MinHeap 전체 코드

struct MinHeap {
    // 힙을 저장할 배열 (1-based index 사용)
    private var elements = [Int]()
    
    // 힙에 저장된 요소 개수 (0번 째 인덱스 제외)
    var count: Int {
        elements.count - 1  // 1-based Index 이기 때문에 count에서 0번째 인덱스 제외
    }
    
    // 힙이 비어있는지 여부 반환
    var isEmpty: Bool {
        count == 0
    }

    // 1-based Index를 위해 0번째 인덱스를 채워줌
    init() { elements.append(0) }
    
    // 힙 요소 출력
    func show() {
        print(elements)
    }
    
    // 최소 값 조회
    func getMinValue() -> Int? {
        if isEmpty { return nil } // 힙이 비어있으면 nil 리턴
        else { return elements[1] } // 1-based Index이므로 1번째 요소가 최소값
    }
    
    // 삽입
    mutating func insert(_ value: Int) {
        elements.append(value) // 새로운 값을 배열 끝에 추가
        
        var currentIndex = count     // 현재 삽입된 노드의 인덱스
        var parentIndex = currentIndex / 2 // 부모 노드의 인덱스 (완전 이진트리에서 부모 = 현재 인덱스 / 2)
        
        // 부모보다 작으면 계속 위로 이동
        // // Heapify Up (삽입 시 재정렬)
        while parentIndex > 0 && elements[currentIndex] < elements[parentIndex] {
            elements.swapAt(currentIndex, parentIndex) // 부모보다 작으면, 현재 노드와 부모 노드 교환
            currentIndex = parentIndex      // 현재 노드를 부모 노드로 이동
            parentIndex = currentIndex / 2  // 새로운 부모 노도 갱신
        }
    }
    
    // 최소값 삭제
    mutating func pop() -> Int? {
        if isEmpty { return nil } // 힙이 비어있으면 nil 반환
        
        elements.swapAt(1, count)   // 루트 노드(최소값)와 마지막 노드 위치 변경
        let returnValue = elements.removeLast() // 최소값을 꺼낸 후 배열에서 제거
        var currentIndex = 1    // 루트 노드부터 재정렬 (루트 노드로 올라온 값의 위치를 찾아줌)
        
        // Heapify Down (삭제 시 재정렬)
        while true {
            let leftChildIndex = 2 * currentIndex // 왼쪽 자식 노드 인덱스
            let rightChildIndex = 2 * currentIndex + 1 // 오른쪽 자식 노드 인덱스
            var swapIndex = currentIndex    // 현재 위치에서 교체할 인덱스
            
            // 왼쪽 자식이 존재하고, 현재 노드보다 작으면 교체 대상으로 설정
            if leftChildIndex < count && elements[leftChildIndex] < elements[swapIndex] {
                swapIndex = leftChildIndex
            }
            
            // 오른쪽 자식이 존재하고, 현재 노드보다 작으면 교체 대상으로 설정
            if rightChildIndex < count && elements[rightChildIndex] < elements[swapIndex] {
                swapIndex = rightChildIndex
            }
            
            if swapIndex == currentIndex { break } // 현재 노드보다 작은 자식 노드가 없으면 종료
            elements.swapAt(currentIndex, swapIndex) // 현재 노드와 가장 작은 자식 노드 교환
            currentIndex = swapIndex // 현재 노드를 내려간 위치로 갱신
        }
        
        return returnValue // 제거된 최소값 반환
    }
}

var minHeap = MinHeap()

for i in 1...10 {
    minHeap.insert(Int.random(in: -100...100))
    minHeap.show()
}
print("-------------")
for i in 1...10 {
    minHeap.pop()
    minHeap.show()
}

/*
 Insert 
 [0, -94]
 [0, -94, 13]
 [0, -94, 13, 28]
 [0, -94, 13, 28, 85]
 [0, -94, 13, 28, 85, 29]
 [0, -94, 13, -39, 85, 29, 28]
 [0, -94, 13, -40, 85, 29, 28, -39]
 [0, -94, 13, -40, 69, 29, 28, -39, 85]
 [0, -94, 13, -40, 48, 29, 28, -39, 85, 69]
 [0, -94, -54, -40, 48, 13, 28, -39, 85, 69, 29]
 -------------
 Pop
 [0, -54, 13, -40, 48, 29, 28, -39, 85, 69]
 [0, -40, 13, -39, 48, 29, 28, 69, 85]
 [0, -39, 13, 28, 48, 29, 85, 69]
 [0, 13, 29, 28, 48, 69, 85]
 [0, 28, 29, 85, 48, 69]
 [0, 29, 69, 85, 48]
 [0, 48, 69, 85]
 [0, 85, 69]
 [0, 69]
 */

 

 

 

MaxHeap은 insert, pop에서 교체 대상을 선택할 때 조건만 바꿔주면 된다

MaxHeap

struct MaxHeap {
  
  ...
    
    // 삽입
    mutating func insert(_ value: Int) {
				...
        // 부모보다 크면 계속 위로 이동
        // // Heapify Up (삽입 시 재정렬)
        while parentIndex > 0 && **elements[currentIndex] > elements[parentIndex]** {
            elements.swapAt(currentIndex, parentIndex) // 부모보다 크면, 현재 노드와 부모 노드 교환
            currentIndex = parentIndex      // 현재 노드를 부모 노드로 이동
            parentIndex = currentIndex / 2  // 새로운 부모 노도 갱신
        }
    }
    
    // 최대값 삭제
    mutating func pop() -> Int? {
				... 
        // Heapify Down (삭제 시 재정렬)
        while true {
            let leftChildIndex = 2 * currentIndex // 왼쪽 자식 노드 인덱스
            let rightChildIndex = 2 * currentIndex + 1 // 오른쪽 자식 노드 인덱스
            var swapIndex = currentIndex    // 현재 위치에서 교체할 인덱스
            
            // 왼쪽 자식이 존재하고, 현재 노드보다 크면 교체 대상으로 설정
            if leftChildIndex < count && **elements[leftChildIndex] > elements[swapIndex]** {
                swapIndex = leftChildIndex
            }
            
            // 오른쪽 자식이 존재하고, 현재 노드보다 크면 교체 대상으로 설정
            if rightChildIndex < count && **elements[rightChildIndex] > elements[swapIndex]** {
                swapIndex = rightChildIndex
            }
         ....
    }
}

var maxHeap = MaxHeap()

for i in 1...10 {
    maxHeap.insert(Int.random(in: -100...100))
    maxHeap.show()
}
print("-------------")
for i in 1...10 {
    maxHeap.pop()
    maxHeap.show()
}

/*
 [0, 33]
 [0, 53, 33]
 [0, 53, 33, -81]
 [0, 85, 53, -81, 33]
 [0, 85, 53, -81, 33, -8]
 [0, 85, 53, -40, 33, -8, -81]
 [0, 85, 53, 71, 33, -8, -81, -40]
 [0, 85, 69, 71, 53, -8, -81, -40, 33]
 [0, 85, 69, 71, 53, -8, -81, -40, 33, -35]
 [0, 85, 69, 71, 53, 62, -81, -40, 33, -35, -8]
 -------------
 [0, 71, 69, -8, 53, 62, -81, -40, 33, -35]
 [0, 69, 62, -8, 53, -35, -81, -40, 33]
 [0, 62, 53, -8, 33, -35, -81, -40]
 [0, 53, 33, -8, -40, -35, -81]
 [0, 33, -40, -8, -81, -35]
 [0, -8, -40, -35, -81]
 [0, -40, -81, -35]
 [0, -35, -81]
 [0, -81]
 [0]
 */