[알고리즘] Heap 힙 데이터구조 : 필수 기본정리 - Min Heap, Max Heap, 삽입, 제거, 탐색 구현

목차

힙(Heap) 개념

힙은 우선 우선순위의 개념을 대입한 자료구조입니다. 전포스트에서 다뤘던 Stack,Queue와 같이 자료가 들어오고 나가는 순서를 정할수있습니다. 우선순위개념과 Stack Queue에대하여 자세히 알고싶으시다면 아래 포스트를 참고해주세요.

[알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin

[알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐),ArrayList, Stack으

다른 우선순위 개념을 가진 큐들과 힙은 어떻게 다를까요?

 

힙을 사용하는 이유

 

우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능합니다. 이중에 힙으로 구현하는게 가장 효율적입니다. 각각 다른 데이터 구조를 사용했을때 시간복잡도를 나타낸 테이블입니다. 

우선순위 큐를 표현하는 방법	삽입	삭제
순서없는 배열	O(1)	O(n)
순서없는 연결 리스트	O(1)	O(n)
정리된 배열(sorted)	O(n)	O(1)
정리된 연결리스트(sorted)	O(n)	O(1)
힙(heap)	O(logn)	O(logn)

힙이 삽입 삭제면에서 가장 효율적이고 빠른 속도를 가진것을 확인할수있습니다. 

 

힙의 종류

힙에는 두가지 종류가있습니다 : 

1. 최대힙(Maxheap): 높은값을 가진 element가 우선순위 위에있습니다. 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같습니다. 

2. 최소힙(Minheap): 낮은값을 가진 element가 우선순위 위에있습니다. 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같습니다. 

여기서 힙의 특징을 알아 볼수있는데요, 루트값이 노드중에 가장 큰값이거나 가장 작은값이기만하면되고, 왼쪽 오른쪽 따질필요없이 그냥 자식으로 넣기만 하면됩니다. 아래에서 좀더 자세히 다루겠습니다. 

 

힙의 특징

힙의 대표적인 특징으로 3가지가 있습니다. 

 

1. 반정렬 구조 

Min Max힙을 보면 알다싶이, 아래로 갈수록 커지거나(Min Heap) 아래로갈수록 작아지거나(Max Heap)인 반정렬 상태를 유지하면됩니다. 이러한 특징은 여러개 값들중 최댓값과 최소값을 빠르게찾는데 최적화 되어있습니다. 힙트리에서는 중복된 값을 허용합니다

 

2. 힙은 완전 이진트리구조 

 

힙 데이터 구조는 완전이진트리 구조 입니다.여기서 말하는 완전 이진 트리구조의 뜻은 가장 아래 레벨을 제외한 모든 레벨에 노드로 차있는 동시에 한 노드는 항상 자식을 2개만 가지고있을수있습니다.  

 

3. 힙은 Array 구조

위 다이어그램은 트리모양을 array구조로 나타낸 것입니다. 보시다싶이 힙데이터 구조는 array를 통해 만들게 됩니다. index 0값에는 root노드가 들어오고 다음레벨에 자식 노드들이 들어오게됩니다. 자식 노드를 찾는데 특별한 방법이있습니다. Array는 위치를 찾을 때 index(i) 값을 통해 찾습니다. 

 

어떤 노드의 배열 인덱스를 parent라고할떄 자식을 구하는 식은 다음과 같습니다. 

왼쪽 자식 = 2i + 1
오른쪽 자식 = 2i + 2

그렇다면 반대로 자식노드의 부모노드를 찾고싶다면 반대로 i 값을 찾으면됩니다. 

왼쪽/오른쪽 자식의 부모 i = ( 자식노드의 i - 1 ) / 2

 

힙 Class 구현

위에서 알아보았던 힙의 특징으로 leftChildIndex, rightChildIndex, parentIndex 함수들을 추가해주겠습니다. 

var elements: ArrayList<Element> = ArrayList<Element>()

override val count : Int
	get() = elements.size
    
override fun peek(): Element? = elements.first()

private fun leftChildIndex(index : Int) = (2 * index) + 1

private fun rightChildIndex(index : Int) = (2 * index) + 2

private fun parentIndex(index: Int) = (index - 1) / 2

 

 

삽입(Insert) 함수 구현

구현하기전 개념먼저 알아보겠습니다. 아래 다이어그램에서 7을 추가해야한다고 가정해봅시다.

먼저 가장 아래에 추가해줘야합니다. 

이예제는 MaxHeap 이기때문에 아래로내려갈수록 노드의 값이 작아져야합니다. 그러므로 7을 상위노드로 옮겨줘야합니다.

이 과정을 코드로 나타내보겠습니다. 

override fun insert(element: Element) {
	elements.add(element) //1
    shiftUp(count - 1) //2
}

private fun shiftUp(index: Int) {
	var child = index
    var parent = parentIndex(child)
    while (child > 0 && compare(elements[child], elements[parent]) > 0 ){
    
   Collections.swap(elements, child, parent)
   child = parent
   parent = parentIndex(child)
   }
}

abstract class AbstractHeap<Element>() : Heap<Element> {
 abstract fun compare(a: Element, b: Element): Int
}

1. insert 함수안에서 노드를 추가해주고, node를 알맞은 위치로 이동해주는 shiftUp을 실행해주세요.

2. shiftUp함수를 만들어줘야합니다. 

3. shiftUp함수 내부를 살펴보면, child가 root노드가 아니거나, 부모노드보다, 자식 노드가 우선순위에있다면, shiftUp을 반복해서 실행하게 하게 됩니다. 

 

삽입 함수는 O(log n) 속도를 가지고있습니다. 

 

제거(Remove) 함수 구현

우선 root노드를 제거하는 법을 알아보겠습니다. 루트노드를 제거하기위해 먼저 가장 마지막 노드와, 루트노드의 위치를 바꿔줍니다. 

그리고 가장 마지막노드로된 부모노드를 삭제합니다. 그리고이제 MaxHeap의 특징에따라 shiftDown을 실행해서 3을 알맞는 위치로 이동해야합니다. 

부모노드가된 3을 자식노드와 비교하며 자식노드가 작은수가 나올때까지 shiftDown을 실행합니다. 여기서 중요한점은 오른쪽 왼쪽 두 노드를 비교해서 가장 큰값을 부모노드로 올려야합니다. 아래 예제에서는 4 6 모두 3보다 크지만 6이 더 크기때문에 위로 올라온것을 알수있습니다. 

제거함수를 코드로 구현해보겠습니다. 

override fun remove(): Element? {
	if(isEmpty) return null//1
    
    Collections.swap(elements, 0, count -1) //2
    val item = elements.removeAt(count -1)//3
    shiftDown(0)//4
    return item
    
}

코드를 설명해보겠습니다. 

1. 힙이 비어있는지 확인합니다. 비어있다면 null을 리턴합니다.

2. 마지막 element와 root노드위치를 바꿔줍니다. 

3. 마지막 element를 제거해줍니다. 

4. 현재는 maxheap/minheap이 아닐수있습니다. 그러므로 0위치 즉 root노드에있는 element를 shiftDown을 통해 maxheap/minheap을 만들어줍니다. 

 

노드 정렬 (ShiftDown) 함수 구현

ShiftDown함수는 위에서 설명했듯이 min/max heap에서 element가 알맞는 위치로 이동시킬때 실행되는 함수입니다. 

private fun shiftDown(index: Int) {
	var parent = index//1
    while(true) { //2
    	val left = leftChilIndex(parent)//3
        val right = rightChildIndex(parent)
        var candidate = parent//4
        if(left < count && 
        compare(elements[left], elements[candidate]) > 0) {
        	candidate = left //5
        }
        if(right < count &&
        compare(elements[right], elements[candidate]) > 0) {
        	candidate = right//6
        }
        if(candidate ==parent){
        	return//7
        }
        Collections.swap(elements, parent, candidate)//8
        parent = candidate
    }
}

shiftDown() 은 매개 변수로 parent노드의 index를 받습니다. 

1. parent Index를 선언해줍니다. 

2. shiftDown을 값이 반환될때까지 계속 반복해줍니다. 

3. 부모의 오른쪽/왼쪽 자식 노드들의 index를 찾습니다. 

4. 이 값들을 이용해서 어디로 swap할것인지 찾아줍니다. 

5. 왼쪽자식 값이 더크다면, 왼쪽자식이 우선순위에 있음을 의미합니다. 그러기때문에 왼쪽자식을 candidate로 지정합니다. 

6. 오른쪽자식 값이 더 크다면 오른쪽 자식이 우선순위에 있음을 의미합니다. 그러기때문에 왼쪽자식을 candidate로 지정합니다. 

7. candidate가 아직도 부모노드라면 shifting은 끝납니다. 

8. candidate와 부모와 위치를 바꾸고 새로운 부모를 지정합니다. 그리고 shifting을 계속 이어갑니다. 

 

이렇게 shiftDown까지 구현을 하면 제거함수가 완성됩니다. 제거함수는 O(log n) 속도를 가지고있습니다. 

 

제거하려는 노드가 루트노드가 아닐때

제거하려는 노드가 루트노드가 아니라면 루트노드를 삭제했을때와 다르게 코드를 구성해야합니다. 

override fun remove(index: Int): Element? {
	if(index >= count ) return null//1
    
    return if(index == count - 1) {
    	elements.removeAt(count - 1) //2
    } else {
    	Collections.swap(elements, index, count - 1 )//3
        val item = elements.removeAt(count -1)//4
        shiftDown(index)//5
        shiftUp(index)
        item
    }
}

heap에서 어떤 위치에있는 element를 지우기위해서는 index값이 필요합니다. 위 코드를 구간별로 자세히 보겠습니다. 

 

1. 매개변수로 받은 index가 array바운더리 안에있는지 확인합니다. 만약 아니라면 null을 반환합니다. 

2. 만약 가장 마지막에 위치한 element를 지운다면 그냥 그값을 지우면됩니다. 

3. 만약 지우려는 element가 가장 마지막에 위치하지않는다면 가장 마지막에있는 값과 위치를 바꿉니다. 

4. 그리고 마지막 element를 삭제해줍니다. 

5. 마지막으로 shiftDown과 shiftUp을 통해 heap 형태로 조정해줍니다. 왜 두 함수모두 실행해야할까요? 아래 그림으로 확인해 보겠습니다. 

왼쪽부터 보시면 5를 지운다고 가정합시다. 가장 마지막 element인 8과 위치를 바꾼후 보면 maxHeap이여야하는데 7이 8을 자식노드로 가지고있는것을 볼수있습니다. 그러므로 shifting up을 해줘야합니다. 

 

루트노드위치가 아닌 노드 제거를 하는 작업또한 O(log n) 속도를 가지고있습니다. 

 

탐색(Search) 구현

index값 위치에있는 element를 지우기위해서 탐색을 사용해야합니다. 하지만 힙은 좋은 탐색 성능을 가지고있지않습니다. 이진 탐색 트리에서는 O(Log n) 속도로 탐색이 가능했지만, 힙은 이진 트리형식을 가지고있어도 array를 통해 만들어지기때문에 이진탐색을 구현할수없습니다. 그러므로 힙에서의 탐색은 O(n)속도를 가집니다. 

 

그러면 탐색을 구현해보겠습니다. 

private fun index(element: Element, i: Int): Int?{
	if(i >= count){
    	return null //1
    }
    if(sort(element, elements[i])){
    	return null //2
    }
    if(element == elements[i]) {
    	return i //3
    }
    val leftChildIndex = index(element, leftChildIndex(i))
    if (leftChildIndex != null) return leftChildIndex //4
    
    val rightChildIndex = index(element, rightChildIndex(i))
    if(rightChildIndex != null) return rightChildIndex //5
    
    return null//6
}

1. 만약 index가 array사이즈보다 크다면 검색할수없기때문에 null을 반환합니다. 

2. 찾는 element가 현재 element index보다 우선순위인지 비교합니다. 

3. 만약 찾는 eleement가 i위치에있는 element와 같다면 i를 리턴합니다. 

4. 왼쪽 자식부터 확인합니다. 

5. 그리고 오른쪽 자식을 확인합니다. 

6. 만약 양쪽다 없다면 null을 리턴합니다. 

 

힙데이터 형식 (Heapify) 구현

주어진 데이터를 힙 성질을 만족하도록 만드는것을 뜻합니다.

 

Heapify를 코드로 구현해보겠습니다. 

protected fun heapify(values: ArrayList<Element>) {
	elements = values
    if(!elements.isEmpty()){
    	(count / 2 downTo 0).forEach {
        	shiftDown(it)
        }
    }
}