프로그래밍/알고리즘
[Algorithm] 힙
힙 (Heap) 힙(Heap)은 완전 이진트리인 특별한 트리를 기반으로 한 자료구조이다. 힙에는 최대힙과 최소힙이 있는데, 최대힙은 최대값을 다루는데 특화되어 있고 최소힙은 최소값을 다루는데 특화되어 있다. 각 힙은 일련의 원소들이 주어졌을 때 최대 or 최소 원소를 빠르게 조회, 삭제할 수 있다. 또한 각 힙 모두 임의의 원소를 빠르게 삽입할 수 있다. 최대, 최소 원소를 다루는 특수적인 상황에 있어 효율적이고, 의외로 최대 최소 원소를 활용해야 하는 상황이 많이 발생하기 때문에 굉장히 중요한 자료구조에 속한다. (우선순위큐도 힙으로 제작된다.) 힙에서 제공하는 연산들을 배열과 비교해보자. 값 삽입 배열 : O(1) 힙 : O(log N) 최대값 or 최소값 삭제 배열 : O(N) 힙 : O(logN)..
