힙 구현

[자료구조] Heap 힙, 우선순위 큐

힙(Heap) 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙에는 두가지 종류가 있다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 : 최대 힙(Max Heap) 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 : 최소 힙(Min Heap) 우선 순위 큐(Priority queue)를 위해서 만들어졌다. - 힙 자체가 우선순위 큐이다. 큐는 FIFO(First In First Out, 선입선출) 자료구조인데, 우선순위큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. Queue의 시간 복잡도는 enqueue = O(1), dequeue O(1) 이고 Priority queue 의 시간 복잡도는 push(삽..