힙
-
[Data Structure] 힙 (heap)알고리즘 & 자료구조 2021. 6. 14. 17:47
힙(heap)이란? 힙은 일종의 트리로 수의 집합에서 가장 작은 수(키)나 가장 큰 수만을 자주 꺼내올때 유용한 자료구조 힙은 완전 이진 트리를 사용하는데 완전이진트리는 자식은 항상 2개, leaf의 가장 왼쪽부터 채우는 트리구조이다. 힙에는 최대힙과 최소힙이 있는데 최소힙은 가장 작은 값이 루트이고 최대힙은 가장 큰 값이 루트이다. 1.힙이 삽입(insert) 되는 과정 here 는 현재 삽입될 위치, 인덱스는 8 5와 1을 비교한다. 1이 더작으므로 5는 here의 자리에 오게된다. 이제 here의 인덱스는 4, 4와 1을 비교한다. 1이 더 작으므로 here의 자리는 4가 들어간다. 마찬가지로 동일하게 1과 2를 비교, 2가 더 크기 때문에 here에는 2가 들어가게 된다. 이제 더이상의 부모는 없..