[Swift] 자료구조 - 힙(Heap)

안녕하세요~

 

오늘은 힙 자료구조에 대해서 정리하겠습니다.

 

힙(Heap)이란?

 

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전이진트리를 기본으로 한 자료구조입니다.

 

완전이진트리

아래의 이미지처럼

왼쪽 자식 노드부터 채워가며 마지막 레벨을 제외하고

모든 자식 노드가 채워져 있는 트리를 말합니다.

 

완전 이진 트리

 

힙의 종류

 

위의 설명에서 힙은

최댓값과 최솟값을 빠르게 찾기 위해서 만들어진 자료구조라고 했는데

 

여기서 최댓값과 최솟값을 빠르게 찾기 위해서

힙은 두가지가 존재합니다.

 

 

최대 힙

자식 노드의 값이 자신의 값보다 작거나 같은 힙을 말합니다.

따라서 루트 노드의 값은 항상 최댓값이 됩니다.

 

최소 힙

자식 노드의 값이 자신의 값보다 크거나 같은 힙을 말합니다.

따라서 루트 노드의 값은 항상 최솟값이 됩니다.

 

 

위의 두가지 모두 BST(Binary Search Tree)와는 다르게 왼쪽 자식, 오른쪽 자식 노드 간의 대소는 상관없습니다.

즉, 왼쪽이든 오른쪽이든 크거나 작아도 상관없다는 이야기입니다.

 

✔︎ Swift로 구현해 보기

왼쪽 노드부터 값을 채워가는 특징으로 인해

힙은 배열로 구현이 가능합니다.

 

따라서 노드의 순서를 index로 표현할 수 있게 됩니다.

 

인덱스 

위의 이미지를 기준으로 설명해 보면

 

값이 4인 노드의 index는 2입니다.

왼쪽 자식 노드는 (부모노드의 인덱스 * 2)인 4가 되고 

오른쪽 자식 노드는 (부모노드의 인덱스 * 2 + 1)인 5가 됩니다.

 

반대로 자식노드를 기준으로

부모노드는 (자식노드의 인덱스 / 2)로 ( 4 / 2, 5 / 2)인 2가 됩니다.

 

이러한 특성으로 인해 첫 번째 인덱스를 0번이 아닌

1번 인덱스부터 사용하여

코드의 복잡성을 해소시킵니다.

 

1.  Heap

class Heap<T: Comparable> {
    var heap: Array<T> = []
 
    init() { }
    init(data: T) {
        // 위에서 설명했던 것처럼 0번 인덱스는 사용하지 않기 떄문에 처음 받은 데이터로 채워둡니다.
        // 루트노드가 아닙니다.
        heap.append(data)
        // 1번 인덱스
        // 루트 노드입니다.
        heap.append(data)
    }
}

 

2. 삽입

삽입은 완전이진트리이므로

가장 하위의 왼쪽 노드에 먼저 데이터를 넣습니다.

 

이후에 자신의 부모노드와 값을 비교하면서 자신이 들어갈 위치를 결정하게 합니다.

 

최대힙일 경우 자신보다 부모가 값이 작다면 서로의 위치를 스위칭하고

최소힙일 경우 자신보다 부모의 값이 크다면 서로의 위치를 스위칭하게 되는 것입니다.

 

아래의 코드는 최대힙을 기준으로 작성했습니다.

 

func insert(_ data: T) {
   if heap.count == 0 {
    	heap.append(data)
        heap.append(data)
        return
    } 
    
    heap.append(data)
    heapifyUp()
}

func heapifyUp() {

    var index = heap.count - 1 
    // 추가된 데이터는 가장 하위노드의 왼쪽 노드. 즉, 인덱스의 가장 끝입니다.
    var parent = Int(i / 2) 
    // 앞서 설명한 것 처럼 부모노드는 자신의 인덱스 / 2 입니다.
    
    // 최대힙
    while True {
        // 자신보다 부모노드의 값이 더 작다면 둘의 자리를 바꿔줍니다.
        if heap[index] > heap[parent] { 
            heap.swapAt(index, parent)
            // 자신의 인덱스가 부모의 인덱스로 변경되었으니 부모의 인덱스를 자신의 인덱스로 변경합니다.
            index = parent 
            // 다음 비교할 부모인덱스를 계산합니다.
            parent = Int(i / 2) 
        } else {
            // 부모노드의 값이 크다면 루프에서 탈출합니다.
            break 
        }
    }
}

 

3. 추출

최대힙은 최댓값을 꺼내는 것을 말하고 

최소힙은 최솟값을 꺼내는 것을 말합니다.

 

따라서 루트노드의 값을 꺼내고

가장 하위노드의 오른쪽 노드를 최상위 노드로 옮깁니다.

 

이후에 삽입과는 반대로 자식노드들과 값을 비교해 자신의 위치를 결정합니다.

 

최대힙의 경우, 자신보다 자식노드의 값이 크다면 계속해서 스위칭하면서 내려갑니다.

최소힙의 경우, 자신보다 자식노드의 값이 작다면 계속해서 스위칭하면서 내려가게 됩니다.

 

func pop<T : data>() -> T {
    // pop하려는 데이터를 저장
    var popItem = heap[1]
    // 루트노드의 값을 가장 마지막 노드로 바꿔줍니다.
    heap[1] = heap[heap.count - 1] 
    
    heap.popLast()
    heapifyDown(index: 1)
    
    return popItem
}

func heapifyDown(index: Int) {

    var left = index * 2
    var right = index * 2 + 1
    var max = index
    
    // 왼쪽 노드의 값이 자신보다 크다면 해당 인덱스를 넣어줍니다.
    if left <= heap.count - 1 && heap[left] > heap[max] { 
    	max = left
    }
	// 오른쪽 노드의 값이 자신보다 크다면 해당 인덱스를 넣어줍니다.
    if right <= heap.count - 1 && heap[right] > heap[max] {
    	max = right
    }
	
    // 기존의 자신의 인덱스와 다른 인덱스를 가지게 되었다면
    if max != index {
        heap.swapAt(index, max)
        heapifyDown(index: max) 
        // 변경된 인덱스부터 다시 heapify
    }
}

 

더 좋은 글로 찾아뵙겠습니다 ~

 

그럼 안녕 ~ 👋🏻👋🏻👋🏻