힙(heap) 과 힙정렬, 그리고 우선순위 큐

힙(Heap) 힙은 완전 이진트리에서 기반한 자료구조 부모노드와 자식노드 간의 관계에 따라 최대힙과 최소힙으로 나뉜다. 데이터에서 최대값, 최소값을 빠르게 찾아내기 위한 자료구조이다. 최대힙(maxheap) - 자식 노드는 무조건 부모보다 작다. 최소힙(minheap) - 자식 노드는 무조건 부모보다 크다. 힙 정렬 (Heap sort) 위에서 말한 최대힙과 최소힙을 구성하며 정렬하는 방법이다. 최대힙 구성 힙 검증 부모와 자식간의 관계를 검사하여 위치를 바꿔준다. 이 과정을 레벨의 끝까지 이어서 검증 정렬 우선 순위 큐 말 그대로 우선 순위를 매겨 정렬하는 것으로 뽑아 낼때 마다 재정렬을 해야하는 배열보다 강한 장점을 가진 트리 구조를 이용한다. 구현에는 두가지 방법이 있다. stl의 priority_..

원문링크 : 힙(heap) 과 힙정렬, 그리고 우선순위 큐