GoベースTree, BST, Heap
18179 ワード
Tree
treeにはルートのRootノードがあり,その底部はChildノードである.
Childノードの真上のノードをParentノードと呼び,相対的である.
同じ段階にあるものをSiblingと言います.
最末端にChildノードを持たないノードをLeafノードと呼ぶ.
代表的な例はFolderです.
ex)package dataStruct
type TreeNode struct {
Val int
Childs []*TreeNode // 포인터형 배열
}
type Tree struct {
Root *TreeNode
}
func (t *Tree) AddNode(val int) {
if t.Root == nil {
t.Root = &TreeNode{Val: val} //루트가 없을 때 루트를 하나 만든다
} else {
t.Root.Childs = append(t.Root.Childs, &TreeNode{Val: val}) //루트가 있으면 Childs에 노드를 추가한다.
}
}
Tree DFS
Depth First Search
深度優先ナビゲーション
最初のサブノードからそのノードのサブノードまで延長し、サブノードがない場合は親ノードに戻り、他のサブノードがない場合は親ノードに戻ります.
Dijkstraアルゴリズム
DFS原理に基づいて、開始ノードからサブノードに沿って最小値を検索し、最短距離を検索するアルゴリズム.
1.再帰呼び出しを利用する方法
ex) packagepackage dataStruct
import "fmt"
type TreeNode struct {
Val int
Childs []*TreeNode
}
type Tree struct {
Root *TreeNode
}
func (t *TreeNode) AddNode(val int) {
t.Childs = append(t.Childs, &TreeNode{Val: val})
} // child 노드를 추가하는 매소드
func (t *Tree) AddNode(val int) {
if t.Root == nil {
t.Root = &TreeNode{Val: val} //루트가 없을 때 루트를 하나 만든다
} else {
t.Root.Childs = append(t.Root.Childs, &TreeNode{Val: val}) //루트가 있으면 Childs에 노드를 추가한다.
}
}
func (t *Tree) DFS1() { // Tree의 매소드
DFS1(t.Root) // t.Root를 인자로 아래의 함수 DFS1을 콜함
}
func DFS1(node *TreeNode) {
fmt.Printf("%d->", node.Val) // Val 값 출력
for i := 0; i < len(node.Childs); i++ { // child노드의 길이 만큼큼
DFS1(node.Childs[i]) // 재귀 호출
}
// childs[0]번째 인덱스 Val = 2 를 출력하고
// 그 child 노드의 [0]번 째 인덱스를 또 출력 하는 방식
// 만약 없으면 한단계 위로 올라가서 다른 child 노드를 찾는다
}
ex) mainpackage main
import (
"Golesson/dataStruct"
)
func main() {
tree := dataStruct.Tree{}
val := 1
tree.AddNode(val) // Root 를 만듦
val++ //Val을 증가 시킴 = 2
for i := 0; i < 3; i++ { // Root의 child 노드에 3개의 노드를 추가
tree.Root.AddNode(val) // Val = 2 ~ 4 까지의 child 노드가 만들어짐
val++ //Val을 증가 시킴 = 3
}
for i := 0; i < len(tree.Root.Childs); i++ { // Root의 child 노드를 돌면서
for j := 0; j < 2; j++ {
tree.Root.Childs[i].AddNode(val) // 2개 씩 child노드를 추가해줌
val++
}
}
tree.DFS1() // DFS 탐색을 진행
}
-----------------------------
1->2->5->6->3->7->8->4->9->10->
2.スタックを使用する方法
ex)<생략>
func (t *Tree) DFS2() {
s := []*TreeNode{} // *TreeNode 슬라이스 생성
s = append(s, t.Root) // 슬라이스에 Root의 주소 추가
for len(s) > 0 {
var last *TreeNode
last, s = s[len(s)-1], s[:len(s)-1]
// last = s의 길이 -1 즉 마지막 인덱스 를 last로 초기화
// 처음 last에 들어가는건 Root
// s = 0 ~ s의 길이 -1 즉 마지막 인덱스를 제거
// 2번째 왔을때 s 는 3개가 되고 마지막 인덱스가 last{Val:4}
// 3번째 왔을때 s 는 2개 마지막 인덱스 last{Val:10}
fmt.Printf("%d->", last.Val) // 1 -> 4 -> 10
for i := 0; i < len(last.Childs); i++ {
s = append(s, last.Childs[i])
// last.Childs = Root.Childs 만큼 반복 = 3번
// child 노드를 다시 s로 집어 넣는다. 3개
// 2번째 last.Childs = 4번째 노드의 Childs개수 만큼 반복 = 2번
// child 노드를 다시 s로 집어 넣는다. 2개
// 3번째 last.childs = 10번째 노드의 Childs개수 만큼 반복 = 0번
// for문은 진행 되지 않고 다시 위로 넘어감
}
------------------------------------ <생략>
tree.DFS1()
-----------------------------------
1->4->10->9->3->8->7->2->6->5->
順番に<생략>
for i := len(last.Childs)-1; i >= 0; i-- {
s = append(s, last.Childs[i])
// 뒤에서 부터가 아닌 순서대로 출력 가능
}
}
-------------------------------------
<생략>
tree.DFS1()
-----------------------------------
1->2->5->6->3->7->8->4->9->10->
Tree BFS
Breadth First Search
幅優先ナビゲーション
兄弟順に探索する.
Queueの使用方法
ex)<생략>
func (t *Tree) BFS() {
queue := []*TreeNode{} //슬라이스 생성
queue = append(queue, t.Root) // 루트를 넣음
for len(queue) > 0 {
var first *TreeNode
first, queue = queue[0], queue[1:]
// 맨처음 인덱스를 first로 넣고 queue에서 제거
// 2번째 돌때 2번째 인덱스를 first로 {Val:2}
// 3번째 돌때 3번째 인덱스를 first로 {Val:3}
fmt.Printf("%d->", first.Val) //1->2->
for i := 0; i < len(first.Childs); i++ {
queue = append(queue, first.Childs[i])
// first.Childs = root.childs 만큼 = 3번 반복
// queue에 root의 child 노드 2번 노드 부터 4번 노드까지 들어감
// 2번째 queue에 2번 노드의 child 노드 2개 들어감
// 3번째 queue에 3번 노드의 child 노드가 2개 들어감
//뒤에 쌓아놓고 선입 선출 하는 방식
}
}
}
---------------------------
1->2->3->4->5->6->7->8->9->10->
BST
Binary Search Tree
バイナリナビゲーションツリー
rootを基準に、左はrootより小さい値、右は大きな値です.
childに移動しても、親ノードの値よりも左側で、大きな値は右側です.
DFSまたはBFSの欠点は、特定のノードを検索するために、そのノードが現れる前のすべてのノードを巡回しなければならないことである.O(N)
BSTでは、特定のノードを検索するときに親ノードと比較し、小さい場合は左に大きくなると右に素早く検索できます.O(logN)
そくどず
赤色O(N)
青色O(logn)
ex) packagepackage dataStruct
import "fmt"
type BinaryTreeNode struct {
Val int
left *BinaryTreeNode
right *BinaryTreeNode
} // 자식을 2개 밖에 같지 않는 이진 트리
type BinaryTree struct {
Root *BinaryTreeNode
}
func NewBinaryTree(v int) *BinaryTree {
tree := &BinaryTree{}
tree.Root = &BinaryTreeNode{Val: v}
return tree //Root를 생성하는 함수
}
func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode {
if n.Val > v { // 현재 노드의 Val 보다 작으면
if n.left == nil { // 왼쪽이 nil 일때
n.left = &BinaryTreeNode{Val: v} // 왼쪽에 노드 생성해서 주소 저장
return n.left
} else { // 왼쪽이 nil이 아닐때
return n.left.AddNode(v)
// 재귀 호출로 왼쪽 노드와 비교하여 작으면 해당 노드의 왼쪽에 집어 넣음
}
} else { // 현재 노드의 Val 보다 크면
if n.right == nil { // 오른쪽 값이 nil 일때
n.right = &BinaryTreeNode{Val: v} // 오른쪽에 노드 생성후 주소 저장
return n.right
} else {
return n.right.AddNode(v)
// 재귀 호출로 오른쪽 노드와 비교하여 크면 해당 노드의 오른쪽에 집어 넣음
}
}
}
type depthNode struct {
depth int
node *BinaryTreeNode
} // 깊이(줄)를 나타내기 위해 만든 구조체
// BFS를 통해 출력하기
func (t *BinaryTree) Print() {
q := []depthNode{}
q = append(q, depthNode{depth: 0, node: t.Root})
currentDepth := 0 // 현재 줄을 나타내기 위한 변수
for len(q) > 0 {
var first depthNode
first, q = q[0], q[1:] // queue 방식을 이용 선입선출
if first.depth != currentDepth { //현재 줄에 해당 되지 않으면
fmt.Println() // sibling이 늘 때 마다 띄어쓰기
currentDepth = first.depth
}
fmt.Print(first.node.Val, " ") // 현재 노드의 Val값 출력
if first.node.left != nil {
q = append(q, depthNode{depth: currentDepth + 1, node: first.node.left})
// 현재 노드의 왼쪽 값이 nil이 아닐때 currentDepth +1
// first.node.left = root.left 값을 집어 넣음
}
if first.node.right != nil {
q = append(q, depthNode{depth: currentDepth + 1, node: first.node.right})
// 현재 노드의 왼쪽 값이 nil이 아닐때 currentDepth +1
// first.node.right = root.right 값을 집어 넣음
}
}
}
ex) mainpackage main
import (
"Golesson/dataStruct"
)
func main() {
tree := dataStruct.NewBinaryTree(5)
tree.Root.AddNode(3)
tree.Root.AddNode(2)
tree.Root.AddNode(4)
tree.Root.AddNode(8)
tree.Root.AddNode(7)
tree.Root.AddNode(6)
tree.Root.AddNode(10)
tree.Root.AddNode(9)
tree.Print()
}
----------------------------
5
3 8
2 4 7 10
6 9
ノードの検索
ex) package<생략>
func (t *BinaryTree) Search(v int) bool {
return t.Root.Search(v) // bool 값으로 참 거짓을 반환
}
func (n *BinaryTreeNode) Search(v int) bool {
if n.Val == v { // 찾는값이 현재노드와 같을 경우
return true // true 반환
} else if n.Val > v { // 찾는값이 현재 노드보다 작을 경우
if n.left != nil { // 왼쪽값이 nil 이 아닐때
return n.left.Search(v) // 계속해서 왼쪽값을 탐색함
}
return false // 왼쪽에 더이상 없을 경우 false 숫자가 없다는 얘기
} else { // 찾는값이 현재노드 보다 클 경우
if n.right != nil { //오른쪽 값이 nil 이 아닐때
return n.right.Search(v) // 계속해서 오른쪽 값을 탐색
}
return false // 오른쪽에 더이상 없을 경우 false
}
}
ex) main<생략>
if tree.Search(6) {
fmt.Println("found 6")
} else {
fmt.Println("not found 6")
}
---------------------------------
5
3 8
2 4 7 10
6 9
found 6
何回見つけたの?
ex) packagefunc (t *BinaryTree) Search(v int) (bool, int) {
return t.Root.Search(v, 1) // bool 값으로 참 거짓을 반환, 카운트 초기 값 1
}
func (n *BinaryTreeNode) Search(v int, cnt int) (bool, int) {
// 검색할 숫자와 현재 카운트를 인자로 받음
if n.Val == v { // 찾는값이 현재노드와 같을 경우
return true, cnt // true,cnt 반환
} else if n.Val > v { // 찾는값이 현재 노드보다 작을 경우
if n.left != nil { // 왼쪽값이 nil 이 아닐때
return n.left.Search(v, cnt+1) // 계속해서 왼쪽값을 탐색하고 카운트업
}
return false, cnt // 왼쪽에 더이상 없을 경우 false 숫자가 없다는 얘기
} else { // 찾는값이 현재노드 보다 클 경우
if n.right != nil { //오른쪽 값이 nil 이 아닐때
return n.right.Search(v, cnt+1) // 계속해서 오른쪽 값을 탐색하고 카운트업
}
return false, cnt // 오른쪽에 더이상 없을 경우 false,cnt
}
}
ex) main<생략>
if found, cnt := tree.Search(6); found {
// Search(6) 함수를 먼저 실행하고 반환값을
// found, cnt 에 초기화시킨다.
// ; found 의 값이 true일 경우에 출력한다.
fmt.Println("found 6 cnt:", cnt)
} else {
fmt.Println("not found 6 cnt", cnt)
}
----------------------------------
5
3 8
2 4 7 10
6 9
found 6 cnt: 4
BSTバランス
もし二叉木の根が順番に並んでいたら?
1～10の数値を持つバイナリツリーを作成します.
右側にのみ続行します.
10～1個の数字を含むツリーを作成します.
左に進むしか見えません.
この場合,BSTの優勢O(logN)は消失し,O(N)となる.
したがって,BSTの中間値が高いほどよい.これにより高さは低下するが,BSTの構造は,高さが低ければ低いほどよい.これは最小身長木と呼ばれています.
Heap
heapには最大のお尻と最小のお尻があります.
package dataStruct
type TreeNode struct {
Val int
Childs []*TreeNode // 포인터형 배열
}
type Tree struct {
Root *TreeNode
}
func (t *Tree) AddNode(val int) {
if t.Root == nil {
t.Root = &TreeNode{Val: val} //루트가 없을 때 루트를 하나 만든다
} else {
t.Root.Childs = append(t.Root.Childs, &TreeNode{Val: val}) //루트가 있으면 Childs에 노드를 추가한다.
}
}
Depth First Search
深度優先ナビゲーション
最初のサブノードからそのノードのサブノードまで延長し、サブノードがない場合は親ノードに戻り、他のサブノードがない場合は親ノードに戻ります.
Dijkstraアルゴリズム
DFS原理に基づいて、開始ノードからサブノードに沿って最小値を検索し、最短距離を検索するアルゴリズム.
1.再帰呼び出しを利用する方法
ex) package
package dataStruct
import "fmt"
type TreeNode struct {
Val int
Childs []*TreeNode
}
type Tree struct {
Root *TreeNode
}
func (t *TreeNode) AddNode(val int) {
t.Childs = append(t.Childs, &TreeNode{Val: val})
} // child 노드를 추가하는 매소드
func (t *Tree) AddNode(val int) {
if t.Root == nil {
t.Root = &TreeNode{Val: val} //루트가 없을 때 루트를 하나 만든다
} else {
t.Root.Childs = append(t.Root.Childs, &TreeNode{Val: val}) //루트가 있으면 Childs에 노드를 추가한다.
}
}
func (t *Tree) DFS1() { // Tree의 매소드
DFS1(t.Root) // t.Root를 인자로 아래의 함수 DFS1을 콜함
}
func DFS1(node *TreeNode) {
fmt.Printf("%d->", node.Val) // Val 값 출력
for i := 0; i < len(node.Childs); i++ { // child노드의 길이 만큼큼
DFS1(node.Childs[i]) // 재귀 호출
}
// childs[0]번째 인덱스 Val = 2 를 출력하고
// 그 child 노드의 [0]번 째 인덱스를 또 출력 하는 방식
// 만약 없으면 한단계 위로 올라가서 다른 child 노드를 찾는다
}
package main
import (
"Golesson/dataStruct"
)
func main() {
tree := dataStruct.Tree{}
val := 1
tree.AddNode(val) // Root 를 만듦
val++ //Val을 증가 시킴 = 2
for i := 0; i < 3; i++ { // Root의 child 노드에 3개의 노드를 추가
tree.Root.AddNode(val) // Val = 2 ~ 4 까지의 child 노드가 만들어짐
val++ //Val을 증가 시킴 = 3
}
for i := 0; i < len(tree.Root.Childs); i++ { // Root의 child 노드를 돌면서
for j := 0; j < 2; j++ {
tree.Root.Childs[i].AddNode(val) // 2개 씩 child노드를 추가해줌
val++
}
}
tree.DFS1() // DFS 탐색을 진행
}
-----------------------------
1->2->5->6->3->7->8->4->9->10->
2.スタックを使用する方法
ex)
<생략>
func (t *Tree) DFS2() {
s := []*TreeNode{} // *TreeNode 슬라이스 생성
s = append(s, t.Root) // 슬라이스에 Root의 주소 추가
for len(s) > 0 {
var last *TreeNode
last, s = s[len(s)-1], s[:len(s)-1]
// last = s의 길이 -1 즉 마지막 인덱스 를 last로 초기화
// 처음 last에 들어가는건 Root
// s = 0 ~ s의 길이 -1 즉 마지막 인덱스를 제거
// 2번째 왔을때 s 는 3개가 되고 마지막 인덱스가 last{Val:4}
// 3번째 왔을때 s 는 2개 마지막 인덱스 last{Val:10}
fmt.Printf("%d->", last.Val) // 1 -> 4 -> 10
for i := 0; i < len(last.Childs); i++ {
s = append(s, last.Childs[i])
// last.Childs = Root.Childs 만큼 반복 = 3번
// child 노드를 다시 s로 집어 넣는다. 3개
// 2번째 last.Childs = 4번째 노드의 Childs개수 만큼 반복 = 2번
// child 노드를 다시 s로 집어 넣는다. 2개
// 3번째 last.childs = 10번째 노드의 Childs개수 만큼 반복 = 0번
// for문은 진행 되지 않고 다시 위로 넘어감
}
------------------------------------ <생략>
tree.DFS1()
-----------------------------------
1->4->10->9->3->8->7->2->6->5->
<생략>
for i := len(last.Childs)-1; i >= 0; i-- {
s = append(s, last.Childs[i])
// 뒤에서 부터가 아닌 순서대로 출력 가능
}
}
-------------------------------------
<생략>
tree.DFS1()
-----------------------------------
1->2->5->6->3->7->8->4->9->10->Tree BFS
Breadth First Search
幅優先ナビゲーション
兄弟順に探索する.
Queueの使用方法
ex)<생략>
func (t *Tree) BFS() {
queue := []*TreeNode{} //슬라이스 생성
queue = append(queue, t.Root) // 루트를 넣음
for len(queue) > 0 {
var first *TreeNode
first, queue = queue[0], queue[1:]
// 맨처음 인덱스를 first로 넣고 queue에서 제거
// 2번째 돌때 2번째 인덱스를 first로 {Val:2}
// 3번째 돌때 3번째 인덱스를 first로 {Val:3}
fmt.Printf("%d->", first.Val) //1->2->
for i := 0; i < len(first.Childs); i++ {
queue = append(queue, first.Childs[i])
// first.Childs = root.childs 만큼 = 3번 반복
// queue에 root의 child 노드 2번 노드 부터 4번 노드까지 들어감
// 2번째 queue에 2번 노드의 child 노드 2개 들어감
// 3번째 queue에 3번 노드의 child 노드가 2개 들어감
//뒤에 쌓아놓고 선입 선출 하는 방식
}
}
}
---------------------------
1->2->3->4->5->6->7->8->9->10->
BST
Binary Search Tree
バイナリナビゲーションツリー
rootを基準に、左はrootより小さい値、右は大きな値です.
childに移動しても、親ノードの値よりも左側で、大きな値は右側です.
DFSまたはBFSの欠点は、特定のノードを検索するために、そのノードが現れる前のすべてのノードを巡回しなければならないことである.O(N)
BSTでは、特定のノードを検索するときに親ノードと比較し、小さい場合は左に大きくなると右に素早く検索できます.O(logN)
そくどず
赤色O(N)
青色O(logn)
ex) packagepackage dataStruct
import "fmt"
type BinaryTreeNode struct {
Val int
left *BinaryTreeNode
right *BinaryTreeNode
} // 자식을 2개 밖에 같지 않는 이진 트리
type BinaryTree struct {
Root *BinaryTreeNode
}
func NewBinaryTree(v int) *BinaryTree {
tree := &BinaryTree{}
tree.Root = &BinaryTreeNode{Val: v}
return tree //Root를 생성하는 함수
}
func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode {
if n.Val > v { // 현재 노드의 Val 보다 작으면
if n.left == nil { // 왼쪽이 nil 일때
n.left = &BinaryTreeNode{Val: v} // 왼쪽에 노드 생성해서 주소 저장
return n.left
} else { // 왼쪽이 nil이 아닐때
return n.left.AddNode(v)
// 재귀 호출로 왼쪽 노드와 비교하여 작으면 해당 노드의 왼쪽에 집어 넣음
}
} else { // 현재 노드의 Val 보다 크면
if n.right == nil { // 오른쪽 값이 nil 일때
n.right = &BinaryTreeNode{Val: v} // 오른쪽에 노드 생성후 주소 저장
return n.right
} else {
return n.right.AddNode(v)
// 재귀 호출로 오른쪽 노드와 비교하여 크면 해당 노드의 오른쪽에 집어 넣음
}
}
}
type depthNode struct {
depth int
node *BinaryTreeNode
} // 깊이(줄)를 나타내기 위해 만든 구조체
// BFS를 통해 출력하기
func (t *BinaryTree) Print() {
q := []depthNode{}
q = append(q, depthNode{depth: 0, node: t.Root})
currentDepth := 0 // 현재 줄을 나타내기 위한 변수
for len(q) > 0 {
var first depthNode
first, q = q[0], q[1:] // queue 방식을 이용 선입선출
if first.depth != currentDepth { //현재 줄에 해당 되지 않으면
fmt.Println() // sibling이 늘 때 마다 띄어쓰기
currentDepth = first.depth
}
fmt.Print(first.node.Val, " ") // 현재 노드의 Val값 출력
if first.node.left != nil {
q = append(q, depthNode{depth: currentDepth + 1, node: first.node.left})
// 현재 노드의 왼쪽 값이 nil이 아닐때 currentDepth +1
// first.node.left = root.left 값을 집어 넣음
}
if first.node.right != nil {
q = append(q, depthNode{depth: currentDepth + 1, node: first.node.right})
// 현재 노드의 왼쪽 값이 nil이 아닐때 currentDepth +1
// first.node.right = root.right 값을 집어 넣음
}
}
}
ex) mainpackage main
import (
"Golesson/dataStruct"
)
func main() {
tree := dataStruct.NewBinaryTree(5)
tree.Root.AddNode(3)
tree.Root.AddNode(2)
tree.Root.AddNode(4)
tree.Root.AddNode(8)
tree.Root.AddNode(7)
tree.Root.AddNode(6)
tree.Root.AddNode(10)
tree.Root.AddNode(9)
tree.Print()
}
----------------------------
5
3 8
2 4 7 10
6 9
ノードの検索
ex) package<생략>
func (t *BinaryTree) Search(v int) bool {
return t.Root.Search(v) // bool 값으로 참 거짓을 반환
}
func (n *BinaryTreeNode) Search(v int) bool {
if n.Val == v { // 찾는값이 현재노드와 같을 경우
return true // true 반환
} else if n.Val > v { // 찾는값이 현재 노드보다 작을 경우
if n.left != nil { // 왼쪽값이 nil 이 아닐때
return n.left.Search(v) // 계속해서 왼쪽값을 탐색함
}
return false // 왼쪽에 더이상 없을 경우 false 숫자가 없다는 얘기
} else { // 찾는값이 현재노드 보다 클 경우
if n.right != nil { //오른쪽 값이 nil 이 아닐때
return n.right.Search(v) // 계속해서 오른쪽 값을 탐색
}
return false // 오른쪽에 더이상 없을 경우 false
}
}
ex) main<생략>
if tree.Search(6) {
fmt.Println("found 6")
} else {
fmt.Println("not found 6")
}
---------------------------------
5
3 8
2 4 7 10
6 9
found 6
何回見つけたの?
ex) packagefunc (t *BinaryTree) Search(v int) (bool, int) {
return t.Root.Search(v, 1) // bool 값으로 참 거짓을 반환, 카운트 초기 값 1
}
func (n *BinaryTreeNode) Search(v int, cnt int) (bool, int) {
// 검색할 숫자와 현재 카운트를 인자로 받음
if n.Val == v { // 찾는값이 현재노드와 같을 경우
return true, cnt // true,cnt 반환
} else if n.Val > v { // 찾는값이 현재 노드보다 작을 경우
if n.left != nil { // 왼쪽값이 nil 이 아닐때
return n.left.Search(v, cnt+1) // 계속해서 왼쪽값을 탐색하고 카운트업
}
return false, cnt // 왼쪽에 더이상 없을 경우 false 숫자가 없다는 얘기
} else { // 찾는값이 현재노드 보다 클 경우
if n.right != nil { //오른쪽 값이 nil 이 아닐때
return n.right.Search(v, cnt+1) // 계속해서 오른쪽 값을 탐색하고 카운트업
}
return false, cnt // 오른쪽에 더이상 없을 경우 false,cnt
}
}
ex) main<생략>
if found, cnt := tree.Search(6); found {
// Search(6) 함수를 먼저 실행하고 반환값을
// found, cnt 에 초기화시킨다.
// ; found 의 값이 true일 경우에 출력한다.
fmt.Println("found 6 cnt:", cnt)
} else {
fmt.Println("not found 6 cnt", cnt)
}
----------------------------------
5
3 8
2 4 7 10
6 9
found 6 cnt: 4
BSTバランス
もし二叉木の根が順番に並んでいたら?
1～10の数値を持つバイナリツリーを作成します.
右側にのみ続行します.
10～1個の数字を含むツリーを作成します.
左に進むしか見えません.
この場合,BSTの優勢O(logN)は消失し,O(N)となる.
したがって,BSTの中間値が高いほどよい.これにより高さは低下するが,BSTの構造は,高さが低ければ低いほどよい.これは最小身長木と呼ばれています.
Heap
heapには最大のお尻と最小のお尻があります.
<생략>
func (t *Tree) BFS() {
queue := []*TreeNode{} //슬라이스 생성
queue = append(queue, t.Root) // 루트를 넣음
for len(queue) > 0 {
var first *TreeNode
first, queue = queue[0], queue[1:]
// 맨처음 인덱스를 first로 넣고 queue에서 제거
// 2번째 돌때 2번째 인덱스를 first로 {Val:2}
// 3번째 돌때 3번째 인덱스를 first로 {Val:3}
fmt.Printf("%d->", first.Val) //1->2->
for i := 0; i < len(first.Childs); i++ {
queue = append(queue, first.Childs[i])
// first.Childs = root.childs 만큼 = 3번 반복
// queue에 root의 child 노드 2번 노드 부터 4번 노드까지 들어감
// 2번째 queue에 2번 노드의 child 노드 2개 들어감
// 3번째 queue에 3번 노드의 child 노드가 2개 들어감
//뒤에 쌓아놓고 선입 선출 하는 방식
}
}
}
---------------------------
1->2->3->4->5->6->7->8->9->10->
Binary Search Tree
バイナリナビゲーションツリー
rootを基準に、左はrootより小さい値、右は大きな値です.
childに移動しても、親ノードの値よりも左側で、大きな値は右側です.
DFSまたはBFSの欠点は、特定のノードを検索するために、そのノードが現れる前のすべてのノードを巡回しなければならないことである.O(N)
BSTでは、特定のノードを検索するときに親ノードと比較し、小さい場合は左に大きくなると右に素早く検索できます.O(logN)
そくどず
赤色O(N)
青色O(logn)
ex) package
package dataStruct
import "fmt"
type BinaryTreeNode struct {
Val int
left *BinaryTreeNode
right *BinaryTreeNode
} // 자식을 2개 밖에 같지 않는 이진 트리
type BinaryTree struct {
Root *BinaryTreeNode
}
func NewBinaryTree(v int) *BinaryTree {
tree := &BinaryTree{}
tree.Root = &BinaryTreeNode{Val: v}
return tree //Root를 생성하는 함수
}
func (n *BinaryTreeNode) AddNode(v int) *BinaryTreeNode {
if n.Val > v { // 현재 노드의 Val 보다 작으면
if n.left == nil { // 왼쪽이 nil 일때
n.left = &BinaryTreeNode{Val: v} // 왼쪽에 노드 생성해서 주소 저장
return n.left
} else { // 왼쪽이 nil이 아닐때
return n.left.AddNode(v)
// 재귀 호출로 왼쪽 노드와 비교하여 작으면 해당 노드의 왼쪽에 집어 넣음
}
} else { // 현재 노드의 Val 보다 크면
if n.right == nil { // 오른쪽 값이 nil 일때
n.right = &BinaryTreeNode{Val: v} // 오른쪽에 노드 생성후 주소 저장
return n.right
} else {
return n.right.AddNode(v)
// 재귀 호출로 오른쪽 노드와 비교하여 크면 해당 노드의 오른쪽에 집어 넣음
}
}
}
type depthNode struct {
depth int
node *BinaryTreeNode
} // 깊이(줄)를 나타내기 위해 만든 구조체
// BFS를 통해 출력하기
func (t *BinaryTree) Print() {
q := []depthNode{}
q = append(q, depthNode{depth: 0, node: t.Root})
currentDepth := 0 // 현재 줄을 나타내기 위한 변수
for len(q) > 0 {
var first depthNode
first, q = q[0], q[1:] // queue 방식을 이용 선입선출
if first.depth != currentDepth { //현재 줄에 해당 되지 않으면
fmt.Println() // sibling이 늘 때 마다 띄어쓰기
currentDepth = first.depth
}
fmt.Print(first.node.Val, " ") // 현재 노드의 Val값 출력
if first.node.left != nil {
q = append(q, depthNode{depth: currentDepth + 1, node: first.node.left})
// 현재 노드의 왼쪽 값이 nil이 아닐때 currentDepth +1
// first.node.left = root.left 값을 집어 넣음
}
if first.node.right != nil {
q = append(q, depthNode{depth: currentDepth + 1, node: first.node.right})
// 현재 노드의 왼쪽 값이 nil이 아닐때 currentDepth +1
// first.node.right = root.right 값을 집어 넣음
}
}
}
package main
import (
"Golesson/dataStruct"
)
func main() {
tree := dataStruct.NewBinaryTree(5)
tree.Root.AddNode(3)
tree.Root.AddNode(2)
tree.Root.AddNode(4)
tree.Root.AddNode(8)
tree.Root.AddNode(7)
tree.Root.AddNode(6)
tree.Root.AddNode(10)
tree.Root.AddNode(9)
tree.Print()
}
----------------------------
5
3 8
2 4 7 10
6 9ノードの検索
ex) package
<생략>
func (t *BinaryTree) Search(v int) bool {
return t.Root.Search(v) // bool 값으로 참 거짓을 반환
}
func (n *BinaryTreeNode) Search(v int) bool {
if n.Val == v { // 찾는값이 현재노드와 같을 경우
return true // true 반환
} else if n.Val > v { // 찾는값이 현재 노드보다 작을 경우
if n.left != nil { // 왼쪽값이 nil 이 아닐때
return n.left.Search(v) // 계속해서 왼쪽값을 탐색함
}
return false // 왼쪽에 더이상 없을 경우 false 숫자가 없다는 얘기
} else { // 찾는값이 현재노드 보다 클 경우
if n.right != nil { //오른쪽 값이 nil 이 아닐때
return n.right.Search(v) // 계속해서 오른쪽 값을 탐색
}
return false // 오른쪽에 더이상 없을 경우 false
}
}<생략>
if tree.Search(6) {
fmt.Println("found 6")
} else {
fmt.Println("not found 6")
}
---------------------------------
5
3 8
2 4 7 10
6 9
found 6何回見つけたの?
ex) package
func (t *BinaryTree) Search(v int) (bool, int) {
return t.Root.Search(v, 1) // bool 값으로 참 거짓을 반환, 카운트 초기 값 1
}
func (n *BinaryTreeNode) Search(v int, cnt int) (bool, int) {
// 검색할 숫자와 현재 카운트를 인자로 받음
if n.Val == v { // 찾는값이 현재노드와 같을 경우
return true, cnt // true,cnt 반환
} else if n.Val > v { // 찾는값이 현재 노드보다 작을 경우
if n.left != nil { // 왼쪽값이 nil 이 아닐때
return n.left.Search(v, cnt+1) // 계속해서 왼쪽값을 탐색하고 카운트업
}
return false, cnt // 왼쪽에 더이상 없을 경우 false 숫자가 없다는 얘기
} else { // 찾는값이 현재노드 보다 클 경우
if n.right != nil { //오른쪽 값이 nil 이 아닐때
return n.right.Search(v, cnt+1) // 계속해서 오른쪽 값을 탐색하고 카운트업
}
return false, cnt // 오른쪽에 더이상 없을 경우 false,cnt
}
}<생략>
if found, cnt := tree.Search(6); found {
// Search(6) 함수를 먼저 실행하고 반환값을
// found, cnt 에 초기화시킨다.
// ; found 의 값이 true일 경우에 출력한다.
fmt.Println("found 6 cnt:", cnt)
} else {
fmt.Println("not found 6 cnt", cnt)
}
----------------------------------
5
3 8
2 4 7 10
6 9
found 6 cnt: 4
BSTバランス
もし二叉木の根が順番に並んでいたら?
1～10の数値を持つバイナリツリーを作成します.
右側にのみ続行します.
10～1個の数字を含むツリーを作成します.
左に進むしか見えません.
この場合,BSTの優勢O(logN)は消失し,O(N)となる.
したがって,BSTの中間値が高いほどよい.これにより高さは低下するが,BSTの構造は,高さが低ければ低いほどよい.これは最小身長木と呼ばれています.
Heap
heapには最大のお尻と最小のお尻があります.
最大ヒップ:親ノード以上の子ノードです.
最小臀部:親ノードは常に子ノード以下です.
Push:新しいノードを追加した後、最下層に入り、親ノードをその値と比較し、最大臀部の場合は大きな数字を上に、最小臀部の場合は小さい数字を上にする原理を得ます.
Pop:最大のお尻であれば、最大の数字が先に落ちて、最後にノードを一番上に置きます.次のサブノードに比べて、最も高い数値は上に、より低い数値は下になります.最小お尻の場合は逆です.
*priority queue
優先キュー
通常のキューは先入先出ですが、優先度キューは優先度のあるキューで、優先度から終了します.
この優先キューを実装するときにheapを使用します.
Max Heap実施
heapを実装する場合は、上部ノードと上部ノードを知る必要があるため、sliceを使用します.
rootからBFS順にsliceを入れます.
sliceの利点は,現在のノードのインデックスを知るだけで親ノードと左右のサブノードを知ることができることである.
N個のノードLeft=2 N+1
N個のノードRight=2 N+2
N番目の親=(N-1)/2
ex) push packagepackage dataStruct
import "fmt"
type Heap struct {
list []int
}
func (h *Heap) Push(v int) {
h.list = append(h.list, v) // 인자로 받은 값을 h.list에 append
idx := len(h.list) - 1 // 현재 인덱스 = 맨 마지막 인덱스
for idx >= 0 {
parentIdx := (idx - 1) / 2 //현재 인덱스의 부모 인덱스
if parentIdx < 0 {
break
//만약 부모 인덱스가 마이너스인 경우 즉 부모가 없을 경우 break
}
if h.list[idx] > h.list[parentIdx] {
h.list[idx], h.list[parentIdx] = h.list[parentIdx], h.list[idx]
// 부모노드와 비교하여 현재노드가 클경우 서로 의 값을 바꿔 줌
idx = parentIdx
// 현재 인덱스를 부모인 덱스로 바꿔준다.
} else {
break
// 크지 않을 경우 바꿀 필요가 없기 때문에 바로 break
}
}
}
func (h *Heap) Print() {
fmt.Println(h.list)
}
ex) push mainpackage main
import (
"Golesson/dataStruct"
)
func main() {
h := &dataStruct.Heap{}
h.Push(9)
h.Push(8)
h.Push(7)
h.Push(6)
h.Push(5)
h.Print()
}
-------------------------
[9 8 7 6 5]
ex) pop Package<생략>
func (h *Heap) Pop() int {
if len(h.list) == 0 {
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
// left 인덱스가 현재 길이보다 길때는 자식 노드가 없다는 말
// left 인덱스가 없으면 right는 당연히 없다.
}
if h.list[leftIdx] > h.list[idx] {
swapIdx = leftIdx
// left와 현재값을 비교했을때 left가 더 크면
// swapIdx 를 leftIdx로 넣고 right와 비교
}
rightIdx := idx*2 + 2
if rightIdx < len(h.list) { // right 노드가 있을 경우
if h.list[rightIdx] > h.list[idx] { // right 인덱스가 현재값보다 큰 경우
if swapIdx < 0 || h.list[swapIdx] < h.list[rightIdx] {
// swapIdx = leftIdx가 0보다 작 거나 , 그값이 right노드 보다 작을떄
swapIdx = rightIdx // left와 right를 바꿔준다.
}
}
}
if swapIdx < 0 { // 바꿀 노드가 없을때
break
}
h.list[idx], h.list[swapIdx] = h.list[swapIdx], h.list[idx]
// 바꿀 노드가 있을 때 스왑
idx = swapIdx // idx 갱신해서 for문으로
}
return top
}
ex) pop mainpackage main
import (
"Golesson/dataStruct"
"fmt"
)
func main() {
h := &dataStruct.Heap{}
h.Push(2)
h.Push(6)
h.Push(5)
h.Push(1)
h.Push(9)
h.Print()
fmt.Println(h.Pop())
fmt.Println(h.Pop())
fmt.Println(h.Pop())
}
-----------------------------
[9 6 5 1 2]
9
6
5
Heapで質問に答える 정수 배열(int array)과 정수 N이 주어지면
N번째로 큰 배열 원소를 찾으시오.
예제)
Input: [-1, 3, -1, 5, 4] , 2
Output: 4
Input: [2, 4, -2, -3, 8], 1
Output: 8
Input: [-5, -3, 1], 3
Output: -5
package dataStruct
import "fmt"
type Heap struct {
list []int
}
func (h *Heap) Push(v int) {
h.list = append(h.list, v) // 인자로 받은 값을 h.list에 append
idx := len(h.list) - 1 // 현재 인덱스 = 맨 마지막 인덱스
for idx >= 0 {
parentIdx := (idx - 1) / 2 //현재 인덱스의 부모 인덱스
if parentIdx < 0 {
break
//만약 부모 인덱스가 마이너스인 경우 즉 부모가 없을 경우 break
}
if h.list[idx] > h.list[parentIdx] {
h.list[idx], h.list[parentIdx] = h.list[parentIdx], h.list[idx]
// 부모노드와 비교하여 현재노드가 클경우 서로 의 값을 바꿔 줌
idx = parentIdx
// 현재 인덱스를 부모인 덱스로 바꿔준다.
} else {
break
// 크지 않을 경우 바꿀 필요가 없기 때문에 바로 break
}
}
}
func (h *Heap) Print() {
fmt.Println(h.list)
}
package main
import (
"Golesson/dataStruct"
)
func main() {
h := &dataStruct.Heap{}
h.Push(9)
h.Push(8)
h.Push(7)
h.Push(6)
h.Push(5)
h.Print()
}
-------------------------
[9 8 7 6 5]<생략>
func (h *Heap) Pop() int {
if len(h.list) == 0 {
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
// left 인덱스가 현재 길이보다 길때는 자식 노드가 없다는 말
// left 인덱스가 없으면 right는 당연히 없다.
}
if h.list[leftIdx] > h.list[idx] {
swapIdx = leftIdx
// left와 현재값을 비교했을때 left가 더 크면
// swapIdx 를 leftIdx로 넣고 right와 비교
}
rightIdx := idx*2 + 2
if rightIdx < len(h.list) { // right 노드가 있을 경우
if h.list[rightIdx] > h.list[idx] { // right 인덱스가 현재값보다 큰 경우
if swapIdx < 0 || h.list[swapIdx] < h.list[rightIdx] {
// swapIdx = leftIdx가 0보다 작 거나 , 그값이 right노드 보다 작을떄
swapIdx = rightIdx // left와 right를 바꿔준다.
}
}
}
if swapIdx < 0 { // 바꿀 노드가 없을때
break
}
h.list[idx], h.list[swapIdx] = h.list[swapIdx], h.list[idx]
// 바꿀 노드가 있을 때 스왑
idx = swapIdx // idx 갱신해서 for문으로
}
return top
}package main
import (
"Golesson/dataStruct"
"fmt"
)
func main() {
h := &dataStruct.Heap{}
h.Push(2)
h.Push(6)
h.Push(5)
h.Push(1)
h.Push(9)
h.Print()
fmt.Println(h.Pop())
fmt.Println(h.Pop())
fmt.Println(h.Pop())
}
-----------------------------
[9 6 5 1 2]
9
6
5정수 배열(int array)과 정수 N이 주어지면
N번째로 큰 배열 원소를 찾으시오.
예제)
Input: [-1, 3, -1, 5, 4] , 2
Output: 4
Input: [2, 4, -2, -3, 8], 1
Output: 8
Input: [-5, -3, 1], 3
Output: -5小要素配列検索時=Max Heap
大型アレイ要素を検索する場合=Min Heap
Min Heap
上記の例は、N番目の大きな配列の要素を検索するためminheapによって展開されます.
ex) min heap packagepackage dataStruct
import "fmt"
type Heap struct {
list []int
}
func (h *Heap) Push(v int) {
h.list = append(h.list, v) // 인자로 받은 값을 h.list에 append
idx := len(h.list) - 1 // 현재 인덱스 = 맨 마지막 인덱스
for idx >= 0 {
parentIdx := (idx - 1) / 2 //현재 인덱스의 부모 인덱스
if parentIdx < 0 {
break
//만약 부모 인덱스가 마이너스인 경우 즉 부모가 없을 경우 break
}
if h.list[idx] < h.list[parentIdx] {
h.list[idx], h.list[parentIdx] = h.list[parentIdx], h.list[idx]
// 부모노드와 비교하여 현재노드가 작을 경우 서로의 값을 바꿔 줌
idx = parentIdx
// 현재 인덱스를 부모인 덱스로 바꿔준다.
} else {
break
// 크지 않을 경우 바꿀 필요가 없기 때문에 바로 break
}
}
}
func (h *Heap) Print() {
fmt.Println(h.list)
}
func (h *Heap) Count() int {
return len(h.list)
} // 힙의 갯수를 카운트
func (h *Heap) Pop() int {
if len(h.list) == 0 {
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] // 맨 마지막 노드를 잘라냄
if len(h.list) == 0 {
return top //자식노드가 없을 경우 리턴
}
h.list[0] = last // 맨뒤의 애를 맨위로 바꿈
idx := 0
for idx < len(h.list) { // 맨위 부터 끝까지 내려가면서 비교
swapIdx := -1 // 바꿀 인덱스
leftIdx := idx*2 + 1
if leftIdx >= len(h.list) {
break
// left 인덱스가 현재 길이보다 길때는 자식 노드가 없다는 말
// left 인덱스가 없으면 right는 당연히 없다.
}
if h.list[leftIdx] < h.list[idx] {
swapIdx = leftIdx
// left와 현재값을 비교했을때 left가 더 작으면
// swapIdx 를 leftIdx로 넣고 right와 비교
}
rightIdx := idx*2 + 2
if rightIdx < len(h.list) { // right 노드가 있을 경우
if h.list[rightIdx] < h.list[idx] { // right 인덱스가 현재값보다 작은 경우
if swapIdx < 0 || h.list[swapIdx] > h.list[rightIdx] {
// swapIdx = leftIdx가 0보다 작 거나 , 그값이 right노드 보다 클떄
swapIdx = rightIdx // left와 right를 바꿔준다.
}
}
}
if swapIdx < 0 { // 바꿀 노드가 없을때
break
}
h.list[idx], h.list[swapIdx] = h.list[swapIdx], h.list[idx]
// 바꿀 노드가 있을 때 스왑
idx = swapIdx // idx 갱신해서 for문으로
}
return top
}
ex) min heap mainpackage main
import (
"Golesson/dataStruct"
"fmt"
)
func main() {
h := &dataStruct.Heap{}
//Input: [-1, 3, -1, 5, 4] , 2
//Output: 4
nums := []int{-1, 3, -1, 5, 4}
for i := 0; i < len(nums); i++ {
h.Push(nums[i])
if h.Count() > 2 { // 힙의 갯수를 2개로 제한함
h.Pop() // 2개가 넘어가면 빼냄
}
}
fmt.Println(h.Pop())
// Input: [2, 4, -2, -3, 8], 1
// Output: 8
h = &dataStruct.Heap{}
nums = []int{2, 4, -2, -3, 8}
for i := 0; i < len(nums); i++ {
h.Push(nums[i])
if h.Count() > 1 { // 힙의 갯수를 1개로 제한함
h.Pop() // 1개가 넘어가면 빼냄
}
}
fmt.Println(h.Pop())
// Input: [-5, -3, 1], 3
// Output: -5
h = &dataStruct.Heap{}
nums = []int{-5, -3, 1}
for i := 0; i < len(nums); i++ {
h.Push(nums[i])
if h.Count() > 3 { // 힙의 갯수를 3개로 제한함
h.Pop() // 3개가 넘어가면 빼냄
}
}
fmt.Println(h.Pop())
}
Reference
この問題について(GoベースTree, BST, Heap), 我々は、より多くの情報をここで見つけました
https://velog.io/@jinzza456/go-언어-기초-강좌-7
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
package dataStruct
import "fmt"
type Heap struct {
list []int
}
func (h *Heap) Push(v int) {
h.list = append(h.list, v) // 인자로 받은 값을 h.list에 append
idx := len(h.list) - 1 // 현재 인덱스 = 맨 마지막 인덱스
for idx >= 0 {
parentIdx := (idx - 1) / 2 //현재 인덱스의 부모 인덱스
if parentIdx < 0 {
break
//만약 부모 인덱스가 마이너스인 경우 즉 부모가 없을 경우 break
}
if h.list[idx] < h.list[parentIdx] {
h.list[idx], h.list[parentIdx] = h.list[parentIdx], h.list[idx]
// 부모노드와 비교하여 현재노드가 작을 경우 서로의 값을 바꿔 줌
idx = parentIdx
// 현재 인덱스를 부모인 덱스로 바꿔준다.
} else {
break
// 크지 않을 경우 바꿀 필요가 없기 때문에 바로 break
}
}
}
func (h *Heap) Print() {
fmt.Println(h.list)
}
func (h *Heap) Count() int {
return len(h.list)
} // 힙의 갯수를 카운트
func (h *Heap) Pop() int {
if len(h.list) == 0 {
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] // 맨 마지막 노드를 잘라냄
if len(h.list) == 0 {
return top //자식노드가 없을 경우 리턴
}
h.list[0] = last // 맨뒤의 애를 맨위로 바꿈
idx := 0
for idx < len(h.list) { // 맨위 부터 끝까지 내려가면서 비교
swapIdx := -1 // 바꿀 인덱스
leftIdx := idx*2 + 1
if leftIdx >= len(h.list) {
break
// left 인덱스가 현재 길이보다 길때는 자식 노드가 없다는 말
// left 인덱스가 없으면 right는 당연히 없다.
}
if h.list[leftIdx] < h.list[idx] {
swapIdx = leftIdx
// left와 현재값을 비교했을때 left가 더 작으면
// swapIdx 를 leftIdx로 넣고 right와 비교
}
rightIdx := idx*2 + 2
if rightIdx < len(h.list) { // right 노드가 있을 경우
if h.list[rightIdx] < h.list[idx] { // right 인덱스가 현재값보다 작은 경우
if swapIdx < 0 || h.list[swapIdx] > h.list[rightIdx] {
// swapIdx = leftIdx가 0보다 작 거나 , 그값이 right노드 보다 클떄
swapIdx = rightIdx // left와 right를 바꿔준다.
}
}
}
if swapIdx < 0 { // 바꿀 노드가 없을때
break
}
h.list[idx], h.list[swapIdx] = h.list[swapIdx], h.list[idx]
// 바꿀 노드가 있을 때 스왑
idx = swapIdx // idx 갱신해서 for문으로
}
return top
}
package main
import (
"Golesson/dataStruct"
"fmt"
)
func main() {
h := &dataStruct.Heap{}
//Input: [-1, 3, -1, 5, 4] , 2
//Output: 4
nums := []int{-1, 3, -1, 5, 4}
for i := 0; i < len(nums); i++ {
h.Push(nums[i])
if h.Count() > 2 { // 힙의 갯수를 2개로 제한함
h.Pop() // 2개가 넘어가면 빼냄
}
}
fmt.Println(h.Pop())
// Input: [2, 4, -2, -3, 8], 1
// Output: 8
h = &dataStruct.Heap{}
nums = []int{2, 4, -2, -3, 8}
for i := 0; i < len(nums); i++ {
h.Push(nums[i])
if h.Count() > 1 { // 힙의 갯수를 1개로 제한함
h.Pop() // 1개가 넘어가면 빼냄
}
}
fmt.Println(h.Pop())
// Input: [-5, -3, 1], 3
// Output: -5
h = &dataStruct.Heap{}
nums = []int{-5, -3, 1}
for i := 0; i < len(nums); i++ {
h.Push(nums[i])
if h.Count() > 3 { // 힙의 갯수를 3개로 제한함
h.Pop() // 3개가 넘어가면 빼냄
}
}
fmt.Println(h.Pop())
}Reference
この問題について(GoベースTree, BST, Heap), 我々は、より多くの情報をここで見つけました https://velog.io/@jinzza456/go-언어-기초-강좌-7テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol