#DataStructure #DataStructure-Heap #DataStructure-Tree #Algorithm-Heap_Sort

관련 문제: 506. Relative Ranks

1. Heap?

(*자료구조의 Heap과 Heap 메모리는 다릅니다.)
=>부모노드와 자식노드의 키값 간에 대소관계가 존재하는 완전 이진 트리 형태의 자료구조

대소 관계라고 했으니, 부모노드의 값 > 자식노드의 값(최대 힙), 부모노드의 값 < 자식노드의 값(최소 힙)의 두가지 경우가 있다. 최대 힙과 최소 힙의 용어는 부모노드와 자식노드를 루트까지 끌어올려서 생각하면 되는데, 최대 힙의 경우 루트의 값은 자식과 자손 노드의 어떤것보다 크기 때문에 최대 힙이라는 이름이 붙는다. 최소 힙의 경우도 마찬가지로 생각하면 된다.

힙은 부모와 자식 노드의 값에 대소관계가 있기 때문에 최대값과 최소값을 찾기에 적합한 자료구조이다. (형제 노드 간에는 대소관계를 생각하지 않는다.)

1-1. 배열을 힙으로서 생각하기 (= 배열을 완전 이진 트리로서 생각하기)

완전 이진 트리는 배열을 가지고 만들 수 있다. (노드 객체를 만드는 방법도 있지만 알고리즘 문제에서는 배열로 제시해주는 경우도 있기 때문에 이렇게 생각하는데 익숙해지는것도 필요하다.)
[0, 1, 2, 3, 4, 5, 6]이라는 완전 이진트리의 구성은 아래와 같이 된다.

				0
		1              2
	3       4      5       6

인덱스 0을 루트로 하고, 왼쪽 부터 인덱스가 낮은 값이 정렬된다.

깊이 N인 노드의 갯수는: 2^N 이기 때문에

[0] // Depth0: 2^0개
[1, 2] // Depth1: 2^1개
[3, 4, 5, 6] // Depth2: 2^2개

으로 생각할 수 있고, 이에 따라서 인덱스 x의 깊이를 알아낼 수 있다.

또한 자식 노드의 인덱스도 알아낼 수 있는데,
0의 왼쪽 자식 노드의 인덱스는 1이고, 오른쪽 자식 노드 인덱스는 2이다.
1의 왼쪽 자식 노드의 인덱스는 3이고, 오른쪽 자식 노드 인덱스는 4이다.
2의 왼쪽 자식 노드의 인덱스는 5이고, 오른쪽 자식 노드 인덱스는 6이다.
이것을 일반화하면

• 인덱스 a의 왼쪽 자식 노드 인덱스: 2*a+1
• 오른쪽 자식 노드의 인덱스: 2*a+2
  이다.

그리고 부모 노드의 인덱스도 알아낼 수 있는데,

• (자식노드 인덱스+1)/2-1
  이다.

2. Heap 만들기

2-1. Heap에 원소 추가하기

fun ArrayList<Int>.insertToMaxHeap(num: Int) {  
    // 1. 리스트의 가장 마지막에 숫자를 추가한다.  
    this.add(num)  
  
    var idx = this.size-1  
    while(idx > 0) {  
        // 2. 추가한 노드의 부모 노드를 찾는다.  
        val parentIdx = (idx+1)/2-1  
  
        // 3-1. 부모 노드의 값이 자식 노드의 값보다 작으면 값을 바꾼다.  
        if (this[parentIdx] < this[idx]) {  
            swap(this, parentIdx, idx)  
            // 이것을 3-2.인 부모를 만날때까지 부모의 부모 노드로 거슬러 올라가면서 확인한다.  
            idx = parentIdx  
        } else {  
            // 3-2. 작지 않으면 이 노드의 위치는 결정되었다. 1.로 돌아간다.  
            break  
        }  
    }  
}

fun swap(array: MutableList<Int>, parent: Int, child: Int) {  
    val temp = array[parent]  
    array[parent] = array[child]  
    array[child] = temp  
}  

2-1. Heap에 원소 삭제하기

2. 최대 힙의 삭제, [알고리즘] 힙 정렬(heap sort)이란, heejeong Kwon
위의 블로그 포스트에 그림으로 삭제 후 정비 과정에 대해서 이해하기 쉽게 기술하고 있으니 참고.
Heap의 원소 삭제는 루트에서 일어나며 (다른 노드가 먼저 삭제될 수는 없다.), 삭제 후 Heap의 성질을 유지해주기 위해서 정비 과정이 일어나야 한다.

fun ArrayList<Int>.deleteFromMaxHeap(): Int {  
    // 1. 가장 마지막 노드의 값을 루트 노드의 값으로 변경하고 위치하고 노드를 삭제한다. (= 루트 노드를 삭제하고 마지막 노드를 루트노드로 만든다)  
    val maxItem = this[0]  
    val minItem = this[this.size-1]  
    this[0] = minItem  
  
    this.removeAt(this.size - 1)  
  
    var idx = 0  
    while((idx*2+1) < this.size) {  
        // 2. 왼쪽과 오른쪽 자식 노드 중 노드 값이 큰 노드를 선택한다.  
        val leftChildIdx = idx*2+1  
        val rightChildIdx = idx*2+2  
  
        val childIdxToCompare = if (rightChildIdx < this.size) {  
            if (this[leftChildIdx] < this[rightChildIdx]) {  
                rightChildIdx  
            } else {  
                leftChildIdx  
            }  
        } else {  
            leftChildIdx  
        }  
  
        // 3-1. 비교 대상 자식 노드 값보다 부모 노드 값이 더 작으면 노드를 바꾼다.  
        if (this[idx] < this[childIdxToCompare]) {  
            swap(this, idx, childIdxToCompare)  
            // 4. 3-2.의 경우가 생길 때 까지 정비 작업을 계속 진행한다.  
            idx = childIdxToCompare  
        } else { // 3-2. 비교 대상 자식 노드 값이 부모 노드 값보다 작으면 정비 작업을 끝낸다.  
            break  
        }  
    }  
  
    println("deletedItem: $maxItem, sortedHeap: ${this.toString()}")  
  
    return maxItem  
}

2-3. 완전 이진 트리를 힙으로 바꾸기

fun Array<Int>.maxHeapify(): ArrayList<Int> {  
    val list: ArrayList<Int> = arrayListOf()  
  
    for (num in this) {  
        list.insertToMaxHeap(num)  
    }  
  
    return list  
}
  
fun main() {  
    val arrayList: Array<Int> = arrayOf(10, 3, 69, 32, 29, 88, 2, 100)  
  
    println(arrayList.maxHeapify().contentToString())  
}

3. 힙 정렬

=>힙 자료구조에 담긴 값을 오름차순 혹은 내림차순으로 정렬하는 것.

힙은 부모와 자식 노드 사이의 대소 관계가 있을 뿐, 형제 노드끼리의 대소 관계는 없다. 이것을 좀 더 확대해서 해석하면 (최대 힙을 생각할 때) 부모 노드 보다는 작지만, 부모 노드의 형제 노드 보다는 큰 값을 가진 노드가 있을 수 있다. 따라서 힙 정렬은 힙의 삽입 과정이 아닌, 힙의 삭제 과정에 의해서 이루어진다. 왜냐하면, 힙에서 보장할 수 있는 특징은 최대, 최소값의 위치 즉, 루트는 어떤 자손 노드들보다 가장 크거나 작다. 이기 때문이다.

fun ArrayList<Int>.sortHeap(): Array<Int> {  
    val sortedArray: Array<Int> = Array(this.size){0}  
  
    while(this.size > 0) {  
        val deletedItem = this.deleteFromMaxHeap()  
        sortedArray[this.size] = deletedItem  
    }  
  
    return sortedArray  
}


fun main() {  
    val arrayList: Array<Int> = arrayOf(10, 3, 69, 32, 29, 88, 2, 100)  
    val heap = arrayList.maxHeapify()  
  
    println(heap.toString())  
  
    val sortedArray = heap.sortHeap()  
  
    println(sortedArray.contentToString())  
}