[Data Structure] 힙(Heap)이란? (feat. Swift)

안녕하세요 Foma 💻  입니다!

 

요즘 알고리즘을 공부하고 있는데 그 중 힙소트에 대해 알게 되었습니다.

 

힙소트를 하려면 힙이라는 자료구조가 필요하더라구요.

 

그래서 힙이 무엇이고 어떻게 구현하는지에 대해 정리하려고 합니다!

 

바로 시작할게요~

---

완전 이진트리(Complete Binary Tree)란? ⛓

 

먼저 힙에 대해 알아보기 전에 완전이진트리에 대해서 알아보겠습니다.

 

이유는 힙이 완전이진트리로 되어있기 떄문입니다.

 

완전 이진 트리에서, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h 에서 1부터 2h-1 개의 노드를 가질 수 있다. 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다. - 위키 백과 -

 

즉, 맨 마지막 노드의 자식 빼고 모든 노드가 두개씩 자식을 가지고 있어야 하는 구조입니다.

 

아래 그림을 보시면 이해하기가 수월하실거에요!

 

 

출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jerrypoiu&logNo=221038260559

---

힙(Heap)이란? 📘

 

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. - 위키 백과 -

 

즉, 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조 입니다.

 

최대힙(MaxHeap) 👍🏻

 

최대힙은 최댓값을 빠르게 찾아내기 위한 자료구조로,

 

부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 의미합니다.

 

최소힙(MinHeap) 👎🏻

 

최소힙은 최대힙과 반대로 최솟값을 빠르게 찾아내기 위한 자료구조로,

 

부모노드의 키값이 자식노드의 키값보다 항상 더 작은 힙을 의미합니다.

 

특징

 

배열 형태로 구현할 수 있다.

---

시간복잡도

 

힙은 전체 높이가 logN입니다.

 

고로, 삽입이나 삭제 시에 노드들을 재정렬 할 때 최대 logN의 시간이 걸린다.

 

모든 N개의 노드들이 최대 logN의 시간이 걸린다면 NlogN의 시간이 걸리므로 시간복잡도는 O(nlogn) 입니다.

---

Heapify란? 

 

Heapify는 말 그대로 힙의 성질로 바꿔주는 과정입니다.

 

삽입

 

아래와 같이 특정한 값을 가진 노드가 새롭게 들어왔을 때 힙의 성질에 맞게 구현하는 과정입니다.

 

간단히 말하면 가장 마지막에 새롭게 들어온 노드를 삽입하고 부모 노드와 비교하면서 바꿔가주는 과정입니다.

 

 

 

 

삭제

 

삭제는 가장 최댓값을 가지고 있는 루트노드를 삭제해줍니다.

 

그리고 루트 노드 위치에 가장 마지막에 있는 노드를 대신해주고 자식노드들을 비교해가면서 바꿔가는 과정입니다.

 

 

 

 

---

코드 구현

 

보통 힙으로 많이 쓰이는 MaxHeap을 구현해보겠습니다.

 

초기에 배열이 주어진다면 insert를 통해 힙을 만드는 초기화 과정을 미리 만들어놓고

 

기본적으로 사용될 부모,자식의 인덱스를 알아내는 함수와 부모나

 

자식의 유무를 확인할 함수를 미리 만들어놓겠습니다.

 

struct MaxHeap {
    var nodes:[Int] = []
    
    init(nodes:[Int]) {
        nodes.forEach {
            insert($0)
        }
    }
    
    private func getLeftChildIndex(_ parentIndex: Int) -> Int {
        return 2 * parentIndex + 1
    }
    private func getRightChildIndex(_ parentIndex: Int) -> Int {
        return 2 * parentIndex + 2
    }
    private func getParentIndex(_ childIndex: Int) -> Int {
        return (childIndex - 1) / 2
    }
    
    private func hasLeftChild(_ index: Int) -> Bool {
        return getLeftChildIndex(index) < nodes.count
    }
    private func hasRightChild(_ index: Int) -> Bool {
        return getRightChildIndex(index) < nodes.count
    }
    private func hasParent(_ index: Int) -> Bool {
        return getParentIndex(index) >= 0
    }
    
    ...

 

삽입

 

먼저 새로운 노드를 기존의 nodes에 넣어줍니다.

 

맨 마지막 노드부터 차례로 위의 부모와 현재 node를 비교해줍니다.

 

만약 현재 노드가 더 크다면 부모와 자신을 swap해줍니다.

 

이것을 root노드가 되거나 부모가 더 클 때까지 heapify 과정을 위로 반복합니다.

 

 mutating private func heapifyUp() {
        var index = nodes.count - 1
        while hasParent(index) && nodes[getParentIndex(index)] < nodes[index] {
            nodes.swapAt(getParentIndex(index),index)
            index = getParentIndex(index)
        }
    }
    
    mutating func insert(_ node:Int) {
        nodes.append(node)
        heapifyUp()
    }

 

삭제

 

nodes가 아무것도 없다면 실행하지 않습니다.

 

만약 존재한다면 가장 첫번째와 가장 마지막 번째 노드를 서로 바꿔주고

 

가장 마지막 노드를 삭제해줍니다. (이렇게 하면 가장 큰 값을 삭제한 것과 똑같겠죠?)

 

그리곤 가장 위(0)부터 차례로 자식들이 더 작을 때까지 heapify를 아래로 반복해줍니다.

 

  mutating private func heapifyDown() {
        var index = 0
        while hasLeftChild(index) {
            let leftIndex:Int = getLeftChildIndex(index)
            let rightIndex:Int = getRightChildIndex(index)
            var biggerChildIndex = leftIndex
            if hasRightChild(index) && nodes[leftIndex] < nodes[rightIndex] {
                biggerChildIndex = rightIndex
            }
            
            if nodes[index] > nodes[biggerChildIndex] {
                break
            } else {
                nodes.swapAt(index, biggerChildIndex)
            }
            index = biggerChildIndex
        }
    }
    
    mutating func remove()  {
        if nodes.isEmpty {
            return
        }
        nodes.swapAt(0, nodes.count - 1)
        nodes.removeLast()
        heapifyDown()
    }

 

 

삽입하고 삭제를 하는 과정을 출력해보면 아래와 같습니다.

 

 

     	var heap = MaxHeap(nodes: [1,5,3]) //[5,1,3]
        heap.insert(4) //[5,4,3,1]
        heap.insert(2) //[5,4,3,1,2]
        heap.insert(1) //[5,4,3,1,2,1]
        heap.insert(2) //[5,4,3,1,2,1,2]
        heap.remove() //[4,2,3,1,2,1]
        heap.remove() //[3,2,1,1,2]
        heap.remove() //[2,2,1,1]
        heap.insert(7) //[7, 2, 1, 1, 2]
        heap.insert(5) //[7, 2, 5, 1, 2, 1]

---

전체 코드

 

 

 

---

Reference

 

아래 블로그를 참고했습니다.

 

Swift Data Structures: Heap