최솟값 또는 최댓값을 빠르게 찾아내기 위해 이진트리 형태로 만들어진 자료구조
[ 자바로 배우는 자료구조 ] 힙 (Heap) / 최대힙(MaxHeap), 최소힙(MinHeap) / 코드 포함 강의
자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기
![[출처] https://st-lab.tistory.com/205](https://s3-us-west-2.amazonaws.com/secure.notion-static.com/af4de555-e852-4428-9a35-b75ea207c0f9/img1.daumcdn.png)
[출처] 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://s3-us-west-2.amazonaws.com/secure.notion-static.com/98bfe85b-6718-4868-bbc9-aa99514263ab/img1.daumcdn-2.png)
[출처] 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
}