최솟값 또는 최댓값을 빠르게 찾아내기 위해 이진트리 형태로 만들어진 자료구조

[ 자바로 배우는 자료구조 ] 힙 (Heap) / 최대힙(MaxHeap), 최소힙(MinHeap) / 코드 포함 강의

자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기

완전이진트리란?


  1. 마지막 레벨을 제외한 모든 노드가 채워져 있어야 한다
  2. 모든 노드들은 왼쪽부터 채워져있어야 한다.

[출처] https://st-lab.tistory.com/205

[출처] https://st-lab.tistory.com/205

👮 힙의 종류


부모 노드의 키 값이 자식노드 키 값보다 작다.

부모 노드의 키 값이 자식노드 키 값보다 크다.

✂️ 힙의 구현 (최대힙)


class MaxHeap() {

    private val heap: ArrayList<Int> = arrayListOf()

    init {
        heap.add(Int.MAX_VALUE) // index를 1부터 사용하기 위함
    }

    fun print() {
        for(idx in 1 until heap.size) {
            print("${heap[idx]} ")
        }
        println()
    }

    fun insert(value: Int) {
        heap.add(value)
        var index = heap.lastIndex

        while(index > 1 && heap[index/2] < heap[index]) {
            println("swap")
            swap(index, index/2)

            index /= 2
        }
    }

    fun delete(): Int {
        if(heap.lastIndex < 1) {
            return 0
        }

        val deletedItem = heap[FIRST]
        heap[FIRST] = heap.lastIndex
        heap.remove(heap.lastIndex)

        var index = 1
        while(index * 2 < heap.size) {
            // 우선 노드의 왼쪽 인덱스와 키값을 저장한다.
            var max = heap[index * 2]
            var maxIndex = index * 2

            // 오른쪽 노드가 존재하는지와 왼쪽 값과 오른쪽 값을 비교하고 오른쪽이 더 크다면
            // 오른쪽 노드의 인덱스와 키값을 넣어준다.
            if(index * 2 + 1 <heap.size && max < heap[index * 2 + 1]) {
                max = heap[index * 2 + 1]
                maxIndex = index * 2 + 1
            }

            // 루트노드가 양쪽보다 클 경우 따로 스왑이 필요가 없다.
            if(heap[index] > max) {
                break
            }

            swap(index, maxIndex)
            index = maxIndex
        }
        return deletedItem
    }

    private fun swap(from: Int, to: Int) {
        val temp = heap[from]
        heap[from] = heap[to]
        heap[to] = temp
    }

    companion object {
        const val FIRST = 1
    }
}

[출처] https://st-lab.tistory.com/219

[출처] https://st-lab.tistory.com/219

[힙의 삽입연산]

<aside> 💡 노드가 N개일 때 수행시간은 O(logN) 이다.

</aside>

fun insert(value: Int) {
        heap.add(value)
        var index = heap.lastIndex

        while(index > 1 && heap[index/2] < heap[index]) {
            println("swap")
            swap(index, index/2)

            index /= 2
        }
    }

[힙의 삭제연산]

<aside> 💡 노드가 N개일 때 수행시간은 O(logN) 이다.

</aside>

fun delete(): Int {
        if(heap.lastIndex < 1) {
            return 0
        }

        val deletedItem = heap[FIRST]
        heap[FIRST] = heap.lastIndex
        heap.remove(heap.lastIndex)

        var index = 1
        while(index * 2 < heap.size) {
            // 우선 노드의 왼쪽 인덱스와 키값을 저장한다.
            var max = heap[index * 2]
            var maxIndex = index * 2

            // 오른쪽 노드가 존재하는지와 왼쪽 값과 오른쪽 값을 비교하고 오른쪽이 더 크다면
            // 오른쪽 노드의 인덱스와 키값을 넣어준다.
            if(index * 2 + 1 <heap.size && max < heap[index * 2 + 1]) {
                max = heap[index * 2 + 1]
                maxIndex = index * 2 + 1
            }

            // 루트노드가 양쪽보다 클 경우 따로 스왑이 필요가 없다.
            if(heap[index] > max) {
                break
            }

            swap(index, maxIndex)
            index = maxIndex
        }
        return deletedItem
    }