[바미] Go - Heap에 대해 알아보자2!

지난 시간에 최대 값과 최소 값을 빠르게 가져오기 위해 Heap을 사용한다고 했었고, Heap의 추가 방법, 삭제 방법에 대해 알아 보았습니다.

이 Heap을 Tree로 만들려고 하면 상당히 어렵습니다 부모와 자식간 Linked list로 연결되어 있기 때문에 각각 층간에 연결되어야 하기 때문에 보통 Heap의 같은 경우 Array를 많이 사용합니다.

이것을 Go에서는 Slice라고 합니다.

 

보통 맨 앞을 Root Node로 두는데 아래와 같이 Heap이 구성되어 있다고 가정할 때

 

이걸 배열로 표시를 하면 맨 앞이 Root니까 9인데 BFS하듯이 돈다고 생각 하면 됩니다.

 

그래서 아래와 같은 배열이 구성 됩니다.

9

7

8

3

4

6

7

그리고 그 다음에 추가되는 값은 빈 공간에 추가되고, 뺄 때는 맨 앞에서 빠지고, 맨 뒤에 있는 값이 맨 앞으로 오게 됩니다.

그래서 이와 같이 배열로 하게 되면 Tree와 다르게 맨 뒤의 값을 쉽게 알 수 있게 되죠.

9

7

8

3

4

6

7

그러면 9는 Root Node인데 9가 가지고 있는 자식 Node는 7, 8이 되고,  7의 자식 Node는 3, 4이 되고, 8의 자식 Node는 6, 7이 됩니다.

 

그리고 이 배열의 Index를 보게 되면

9	7	8	3	4	6	7
0	1	2	3	4	5	6

 

이렇게 되죠.

그러면 N번째 Left Node의 자식은 2N + 1이 되고, 9를 보면 9의 Index는 0이고, 0의 Left 자식 Node는 1이다. 2 * 0(N) + 1을 하면 1이 됩니다.

7의 Left 자식 Node를 살펴보자 7은 Index가 1이고, 2N + 1을 하게 되면 3이 됩니다.

8을 보면 8의 Index는 2이고, 2 * 2 + 1을 하게되면 5가 됩니다.

그러면 Right 자식 Node는 어떻게 될까요? 2N + 2가 됩니다.

그래서 현재 나의 Index가 몇번인지 알면 나의 Left, Right 자식의 Node를 가져올 수 있습니다.

그리고 N번째 Node의 부모는 N - 1 / 2가 됩니다.
3의 부모는 7인데 3은 Index가 3이고, 2을 2로 나누면 1이 되어 7이 부모라는 것을 알 수 있고, 
4의 부모도 알아보기 위해 4의 Index값인 4 - 1 / 2를 해줘서 1.5가 되는데 소수점을 버리고 1의 Index를 가진 7이

부모 Node임을 알 수 있죠.

6은 5 - 1 / 2가 되기 때문에 2가 되어 8이 부모 Node가 되는 것을 알 수 있고, 7의 경우 6 - 1 / 2가 되기 때문에 2.5가 되고, 소수점 날려 2가 되어 8이 부모라는 것을 알 수 있습니다.

 

그래서 Tree를 표현할 때 배열을 사용하게 되면 내가 알고자 하는 Node의 Index만 알게 되면 Left 자식 Node와 Right 자식 Node, 부모의 Node를 알 수 있게 됩니다.

이 부분을 코드로 구현해보죠!

 

dataStruct 폴더에 Heap.go라는 파일을 추가 해줍니다!

dataStruct/Heap.go

  package dataStruct

import "fmt"

type Heap struct { // 1
    list []int
}

func (h *Heap) Push(v int) { // 2
    h.list = append(h.list, v) // 1

    idx := len(h.list) - 1 // 2
    for idx >= 0 { // 3
        parantIdx := (idx - 1) / 2 // 4
        if parantIdx < 0 { // 5
            break
        }
        if h.list[idx] > h.list[parantIdx] { // 6
            h.list[idx], h.list[parantIdx] = h.list[parantIdx], h.list[idx]
            idx = parantIdx // 7
        } else { // 8 
            break
        }
    }
}

func (h *Heap) Print() { // 3
    fmt.Println(h.list)
}

1 : Heap이란 타입을 정의 해주고, int형 Slice를 가지도록 합니다.

2 : Heap 포인터의 메소드 Push를 정의하고, 새로운 int형 값 v를 받도록 합니다.
2-1 : 새로운 값을 넣을 때는 맨 뒤에 추가하므로 append()를 사용하여 추가해 줍니다.
2-2 : 그리고 현재 Index를 가져오는데 list의 길이의 -1 입니다. (길이는 Index보다 하나 큰 것이기 때문이죠.)
2-3 : Index가 0보다 크거나 같은 경우 부모로 올라가면서 비교하는데
2-4 : 부모 Index는 아까 공식에 따라 (Index-1)/2이 됩니다.
2-5 : 부모 Index가 -값일 경우에 Break를 시켜 줍니다.
2-6 : 현재 자식Node 값이 부모 Index에 있는 값보다 크다면 서로 Swap시켜 줍니다.
2-7 : 현재 Node의 Index값을 parantIdx로 바꾸어 줍니다.
2-8 : 크지 않은 경우 바꿀 필요가 없기 때문에 Break로 빠져 나옵니다. 그렇게 되면 Push가 끝이 납니다.
3 : list를 출력해주는 함수 입니다.

 

이제 Push를 만들었기 때문에 제대로 동작하는지 확인해보죠!

main.go

package main

import (
    "./dataStruct"
)

func main() {
    h := &dataStruct.Heap{}

    h.Push(9)
    h.Push(8)
    h.Push(7)
    h.Push(6)
    h.Push(5)

    h.Print()
}

잘 들어갔는지만 확인해보죠!

그래서 지금까지의 Data를 Tree로 표현하면 아래와 같습니다.

이제 Pop을 구현해보죠!

func (h *Heap) Pop() int { // 1
    if len(h.list) == 0 { // 2
        return 0
    }

    top := h.list[0] // 3
    last := h.list[len(h.list)-1] // 4
    h.list = h.list[:len(h.list)-1] // 5

    h.list[0] = last // 6
    idx := 0 // 7
    for idx < len(h.list) { // 8
        leftIdx := idx*2 + 1 // 14

        if leftIdx >= len(h.list) { // 19
            break
        }

        left := h.list[leftIdx] // 9
        rightIdx := idx*2 + 2 // 14
        right := h.list[rightIdx] // 10

        if left > last && left >= right { // 11
            h.list[idx], h.list[leftIdx] = h.list[leftIdx], h.list[idx] // 12
            idx = leftIdx // 13
        } else if right > last { // 15
            h.list[idx], h.list[rightIdx] = h.list[rightIdx], h.list[idx] // 16
            idx = rightIdx // 17
        } else { // 18
            break
        }
    }
}

1 : Pop()의 함수를 만들어주는데 return값은 Pop된 값이 나오게 됩니다.
2 : Heap이 아예 비어있는 경우. 0을 return 시켜 줍니다.
3 : 맨 위에 있는 값(h.list[0])을 가져 옵니다.
4 : 맨 마지막에 있는 값을 가져옵니다. last의 값은 heap의 항목 길이 -1번째가 가장 뒤에 있는 값입니다.
5 : heap 끝을 잘라내서 list를 하나 줄여줍니다. 이렇게 하면 맨 마지막 애를 잘라내는 효과를 냅니다.
6 : 맨 마지막에 있는 애를 맨 처음에 올려주고,
7 : 현재 index는 맨 처음으로 해줍니다.
8 : index가 전체 길이보다 작은 경우. 자식 노드로 가면서 자식 중에 가장 큰 애랑 바꾸게 됩니다.
9 : 왼쪽 자식 Node를 가져옵니다.
10 : 오른쪽 자식 Node를 가져옵니다.
11 : 이랬을 때 현재 나의 Node보다 내 자식 노드가 큰 경우 바꾸게 되는데
12 : h의 list의 현재 Node값과 Swap하게 됩니다.
13 : Index를 leftIdx로 바꾸어 줍니다.
14 : idx * 2 + 1, idx * 2 + 2 부분이 반복되므로 변수로 묶어서 관리하도록 해줍니다.
15 : 만약에 right가 last보다 큰 경우 이 때는 left가 last보다 크지 않거나 left가 right보다 크지 않는 경우입니다.
      즉, 부모 Node보다 크고, left보다 크다는 이야기인데
16 : 이 때는 right랑 바꾸어 줍니다.
17 : 그 후 Index값은 rightIdx값으로 바꾸어 줍니다.
18 : 현재 값이 자식노드보다 작지 않은경우 바꿀 필요가 없기 때문에 break로 나갑니다.
19 : 내 자식Node가 현재 길이보다 더 큰 경우에도 비교할 필요가 없으므로(자식이 없기 때문입니다.) break로 빠져 나옵니다.

 

그 이후에도 right부분도 없을 경우도 19번과 마찬가지로 바꾸어주어야 하는데 코드가 복잡해지기 때문에 다시 코드를 수정해 줍니다.

func (h *Heap) Pop() int {
    if len(h.list) == 0 {
        return 0
    }

    top := h.list[0]
    last := h.list[len(h.list)-1]
    h.list = h.list[:len(h.list)-1]

    h.list[0] = last
    idx := 0
    for idx < len(h.list) {
        swapIdx := -1 // 4
        leftIdx := idx*2+1 // 1
        if leftIdx >= len(h.list) { // 2    
                break
        }
        if h.list[leftIdx] > h.list[idx] { // 3
                swapIdx = leftIdx // 5
        }

        rightIdx := idx*2+2 // 6
      if rightIdx < len(h.list) { // 7
                if h.list[rightIdx] > h.list[idx] { // 8
                        if swapIdx < 0 || swapIdx >= 0 && h.list[swapIdx] < h.list[rightIdx] { // 9
                                swapIdx = rightIdx // 10
                        }
                }
        }

        if swapIdx < 0 { // 11
            break
        }
        h.list[idx], h.list[swapIdx] = h.list[swapIdx], h.list[idx] // 12
        idx = swapIdx // 13
    }
    return top // 14
}

1 : leftIdx 값.
2 : leftIdx가 길이보다 크거나 같다면 -> 자식노드가 없다면 break를 해줍니다.
3 : leftIdx가 현재꺼보다 큰 경우 바꾸어 줍니다.
4 : 바꾼 것을 표시해주기 위해 swapIdx를 추가 해준 뒤에
5 : 여기어 넣어 줍니다.
6 : rightIdx 추가.
7 : 마찬가지로 rightIdx가 list길이보다 작은 경우.
8 : 안에 right 자식 Node가 있는 경우를 비교합니다.
9 : swapIdx가 0보다 작거나 swapIdx에 해당하는 값이 현재 내 값과 작은 경우를 비교 합니다.
10 : 그 때 swapIdx를 왼쪽이 아닌 오른쪽 값으로 바꾸도록 하고,
11 : swapIdx가 0보다 작은 경우 swap할 값이 없다는 뜻이기 때문에 break를 해주고,
12 : 그렇지 않은경우 서로 swap 시켜 줍니다.
13 : 위에서 바꾸었기 때문에 Index값을 swapIdx로 바꾸어 준 뒤 for문으로 다시 돌아 갑니다.
14 : 이렇게 for문에 돌아가 다시 비교를 해준 뒤 마지막에 아까 뽑아놓았던 top값을 retrun하여 끝냅니다.

 

그 후 print를 확인해보죠.

main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    h := &dataStruct.Heap{}

    h.Push(9)
    h.Push(8)
    h.Push(7)
    h.Push(6)
    h.Push(5)

    h.Print()

    fmt.Println(h.Pop())
    fmt.Println(h.Pop())
    fmt.Println(h.Pop())

}

출력값을 확인해줍니다.

맨 앞의 값부터 나오는 것을 확인할 수 있습니다.
어떻게 보면 list에 값을 넣고, list에 있는 값을 순서대로 뽑아내는거 아니냐?고 생각할 수 있는데 이걸 확인하는 방법은
처음에 넣을 때 값을 무작위로 넣어보겠습니다.

main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    h := &dataStruct.Heap{}

    h.Push(2)
    h.Push(7)
    h.Push(1)
    h.Push(4)
    h.Push(9)

    h.Print()

    fmt.Println(h.Pop())
    fmt.Println(h.Pop())
    fmt.Println(h.Pop())

}

이렇게 하고 값을 확인해보면

Heap 처리 되어 나오는 것을 알 수 있습니다.

풀소스

---

Haep.go

package dataStruct

import "fmt"

type Heap struct {
 list []int
}

func (h *Heap) Push(v int) {
 h.list = append(h.list, v)

 idx := len(h.list) - 1
 for idx >= 0 {
  parentIdx := (idx - 1) / 2
  if parentIdx < 0 {
   break
  }
  if h.list[idx] > h.list[parentIdx] {
   h.list[idx], h.list[parentIdx] = h.list[parentIdx], h.list[idx]
   idx = parentIdx
  } else {
   break
  }
 }
}

func (h *Heap) Print() {
 fmt.Println(h.list)
}

func (h *Heap) Pop() int {
 if len(h.list) == 0 {
  return 0
 }

 top := h.list[0]
 last := h.list[len(h.list)-1]
 h.list = h.list[:len(h.list)-1]

 h.list[0] = last
 idx := 0
 for idx < len(h.list) {
  swapIdx := -1
  leftIdx := idx*2 + 1
  if leftIdx >= len(h.list) {
   break
  }
  if h.list[leftIdx] > h.list[idx] {
   swapIdx = leftIdx
  }

  rightIdx := idx*2 + 2
  if rightIdx < len(h.list) {
   if h.list[rightIdx] > h.list[idx] {
    if swapIdx < 0 || h.list[swapIdx] < h.list[rightIdx] {
     swapIdx = rightIdx
    }
   }
  }

  if swapIdx < 0 {
   break
  }
  h.list[idx], h.list[swapIdx] = h.list[swapIdx], h.list[idx]
  idx = swapIdx
 }
 return top
}

Main.go

package main

import (
    "fmt"

    "./dataStruct"
)

func main() {
    h := &dataStruct.Heap{}

    h.Push(2)
    h.Push(7)
    h.Push(1)
    h.Push(4)
    h.Push(9)

    h.Print()

    fmt.Println(h.Pop())
    fmt.Println(h.Pop())
    fmt.Println(h.Pop())

}