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

힙(Heap)

 힙은 완전 이진트리에서 기반한 자료구조 부모노드와 자식노드 간의 관계에 따라 최대힙과 최소힙으로 나뉜다.

데이터에서 최대값, 최소값을 빠르게 찾아내기 위한 자료구조이다.

• 최대힙(maxheap) - 자식 노드는 무조건 부모보다 작다.
• 최소힙(minheap) - 자식 노드는 무조건 부모보다 크다.

---

힙 정렬 (Heap sort)

 위에서 말한 최대힙과 최소힙을 구성하며 정렬하는 방법이다.

• 최대힙 구성

• 힙 검증

  • 부모와 자식간의 관계를 검사하여 위치를 바꿔준다.

  • 이 과정을 레벨의 끝까지 이어서 검증

 

• 정렬

힙 재구성

힙 재구성

힙 재구성

힙 재구성

---

우선 순위 큐

 말 그대로 우선 순위를 매겨 정렬하는 것으로 뽑아 낼때 마다 재정렬을 해야하는 배열보다 강한 장점을 가진 트리 구조를 이용한다. 구현에는 두가지 방법이 있다.  stl의 priority_queue<type>과 힙으로 구현하는 방법

queue 해더에 priority_queue가 포함되어있다.