힙(Heap)

🥪

🥅목표

우선 순위 큐를 위하여 만들어진 자료구조, 힙(Heap)에 대해 이해한다.

배열을 사용하여 힙(Heap)을 구현할 수 있다.

힙(Heap)의 삽입과 삭제를 이해한다.

🤔시작 전…

---

우선순위 큐(Priority-Queue)란?

• 데이터틀이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다.

  자료구조	삭제되는 요소
  스택(Stack)	가장 최근에 추가된 데이터
  큐(Queue)	가장 먼저 들어온 데이터
  우선순위 힙(Priority-Queue)	가장 우선순위가 높은 데이터

• 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이 중에서 힙(Heap)으로 구현하는 것이 가장 효율적이다.

  표	삽입	삭제
  순서 없는 배열	O(1)	O(n)
  순서 없는 연결 리스트	O(1)	O(n)
  정렬된 배열	O(n)	O(1)
  정렬된 연결리스트	O(n)	O(1)
  힙	O(log n)	O(log n)

📖개념

---

• 완전 이진 트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.

• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

• 힙은 일종의 반정렬 상태(==느슨한 정렬 상태)를 유지한다.
  • 큰 값이 레벨에 있고 작은 값이 하위 레벨에 있다는 정도라고 이해하면 편합니다.
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리

• 힙 트리에서는 중복된 값을 허용한다(이진 탐색 트리에서는 허용되지 않음)

🎋종류

---

최대 힙(Max Heap)

다음 그림은 Max Heap을 나타내는 예시이다.

      90
     /  \\
   80     85
  /  \\   / \\
 70  75 60  20

위 그림은 다음과 같은 특징을 가진다.

• 완전 이진 트리(CBT) 형태를 가진다.

• 부모 노드의 값이 자식 노드의 값보다 크거나 같다.

• 트리의 최상위 노드는 최댓값을 가진다.

이러한 특징 때문에 Max Heap에서는 빠르게 최댓값을 찾을 수 있다.

최소 힙(Min Heap)

다음 그림은 Min Heap을 나타내는 예시이다.

      10
     /  \\
    15  30
   / \\
  40  50

위 그림은 다음과 같은 특징을 가진다.

• 완전 이진 트리(CBT) 형태를 가진다.

• 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

• 트리의 최상위 노드는 최솟값을 가진다.

이러한 특징 때문에 Min Heap에서는 빠르게 최솟값을 찾을 수 있다.

⚒️구현

---

kotlin으로 구현한 heap

class Heap(private val type: HeapType = HeapType.MIN) {
    private val list = mutableListOf<Int>()

    fun insert(value: Int) {
        list.add(value)
        heapifyUp(list.lastIndex)
    }

    fun delete(): Int? {
        if (list.isEmpty()) return null

        val root = list[0]
        val last = list.last()
        list[0] = last
        list.removeAt(list.lastIndex)
        heapifyDown(0)

        return root
    }

    private fun heapifyUp(index: Int) {
        if (index <= 0) return

        val parentIndex = (index - 1) / 2
        if (compare(index, parentIndex)) {
            swap(index, parentIndex)
            heapifyUp(parentIndex)
        }
    }

    private fun heapifyDown(index: Int) {
        val leftChildIndex = index * 2 + 1
        val rightChildIndex = index * 2 + 2
        var targetIndex = index

        if (leftChildIndex < list.size && compare(leftChildIndex, targetIndex)) {
            targetIndex = leftChildIndex
        }

        if (rightChildIndex < list.size && compare(rightChildIndex, targetIndex)) {
            targetIndex = rightChildIndex
        }

        if (targetIndex != index) {
            swap(index, targetIndex)
            heapifyDown(targetIndex)
        }
    }

    private fun compare(index1: Int, index2: Int): Boolean {
        val value1 = list[index1]
        val value2 = list[index2]

        return if (type == HeapType.MIN) {
            value1 < value2
        } else {
            value1 > value2
        }
    }

    private fun swap(index1: Int, index2: Int) {
        val temp = list[index1]
        list[index1] = list[index2]
        list[index2] = temp
    }
}

enum class HeapType {
    MIN,
    MAX
}

위 코드는 코틀린으로 구현한 Heap이다. Min Heap에 해당하며, 제네릭을 사용하지 않고 Int타입의 정수만 노드로 사용할 수 있도록 작성하였다.

Heap 클래스를 정의하고, insert와 delete 메서드를 구현하였다.

insert 메서드는 값을 추가하는 메서드로 리스트의 마지막에 값을 추가하고, heapifyUp 메서드를 호출하여 heap의 성질을 유지한다.

delete 메서드는 heap에서 값을 삭제하는 메서드로, 루트 노드를 삭제하고, 리스트의 마지막 노드를 루트 노드로 이동시킨다. 이후 heapifyDown 메서드를 호출하여 heap의 성질을 유지합니다.

heapifyUp 메서드는 특정 노드의 부모 노드와 값을 비교하여, heap의 성질을 유지하는 메서드이다.

heapifyDown 메서드는 특정 노드의 자식 노드와 값을 비교하여, heap의 성질을 유지하는 메서드이다.

heapifyUp와 heapifyDown는 재귀이다.

compare 메서드는 heap의 유형에 따라 값을 비교하여, 해당하는 값인지를 반환한다.

swap 메서드는 두 노드의 값을 서로 바꾸는 메서드다.

HeapTypeenum 클래스로 Heap의 종류를 사용자가 선택할 수 있도록 하였다.

아래 예시는 앞서 작성한 Min Heap을 사용하는 예시이다.

fun main() {
    val heap = Heap()

    heap.insert(10)
    heap.insert(50)
    heap.insert(30)
    heap.insert(20)
    heap.insert(40)

    println(heap.delete()) // 10
    println(heap.delete()) // 20
    println(heap.delete()) // 30
    println(heap.delete()) // 40
    println(heap.delete()) // 50
}

Heap 클래스의 인스턴스를 생성하고, insert 메서드를 통해 값을 추가하고, delete 메서드를 통해 값을 삭제한다.

해당 코드는 Min Heap을 사용하고 있으므로, heap에서 delete 메서드를 호출할 때마다 최솟값이 반환된다.

python으로 구현한 heap

class Heap:
    def __init__(self, heap_type='min'):
        self.heap_type = heap_type
        self.heap = []

    def insert(self, val):
        self.heap.append(val)
        self.heapify_up(len(self.heap) - 1)

    def delete(self):
        if not self.heap:
            return None
        root = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify_down(0)
        return root

    def heapify_up(self, index):
        if index <= 0:
            return
        parent_index = (index - 1) // 2
        if self.compare(index, parent_index):
            self.swap(index, parent_index)
            self.heapify_up(parent_index)

    def heapify_down(self, index):
        left_child_index = index * 2 + 1
        right_child_index = index * 2 + 2
        target_index = index

        if left_child_index < len(self.heap) and self.compare(left_child_index, target_index):
            target_index = left_child_index
        if right_child_index < len(self.heap) and self.compare(right_child_index, target_index):
            target_index = right_child_index

        if target_index != index:
            self.swap(index, target_index)
            self.heapify_down(target_index)

    def compare(self, index1, index2):
        val1 = self.heap[index1]
        val2 = self.heap[index2]
        if self.heap_type == 'min':
            return val1 < val2
        else:
            return val1 > val2

    def swap(self, index1, index2):
        self.heap[index1], self.heap[index2] = self.heap[index2], self.heap[index1]

👀 전체적인 함수의 구현 및 흐름은 kotlin으로 작성한 heap 코드와 동일합니다.

Uploaded by N2T