목록힙 구조 (1)

DevBoi

알고리즘 공부 [힙]

힙에 대한 알고리즘 공부를 해보자. 힙은 heap이라고 해서, 다른 의미로 생각할 수 있지만, 쉽게 말하면 단순히 완전 이진 탐색 트리이다. 완전 이진 트리라고 생각하면 된다. 특징으로는 아래와 같다. - 하위의 자식 노드는 무조건 2개가 있다. - 왼쪽이 작거나 오른쪽이 크거나 할 것없이, 단순히 부모가 자식보다 큰게 다이다. - 0의 index는 비워두고 1부터 계산한다. 해당 이유는, 부모는 자식노드 /2 , 오른쪽 은 /2+1 이런식으로 간단하게 구하기 위해서이다. - 최대힙, 최소힙이 존재하여, 데이터를 탐색하는용도 보다 최대값 최소값을 빠르게 찾기 위해서 사용한다. 우선 힙과, 힙에 데이터를 넣는 메소드를 재구현 해보자 데이터를 넣을때, 항상 넣은 데이터와 부모의 데이터를 비교해서, 두개의 s..
Algorithm/[Etc] 2021. 9. 27. 23:31
이전 Prev 1 Next 다음