반응형
1. 배경
중요도별로 작업순서 정렬할때 필요하다.
우선순위큐를 대표적으로 구현하는 자료구조가 힙.
2. 우선순위큐 정의
우선순위를 가진 원소를 삽입, pop할 수 있으면 우선순위큐라고 한다.
3. ADT
원소삽입,
최대원소 알려주기,
최대원소 알려주면서 삭제하기.
4. 트리
트리 = 사이클을 만들지 않는 연결된 그래프
루트 = 부모가 없는노드
이진트리 = 2개이하의 자식 노드
포화 이진트리 --> 2^k -1 개인 모두다 있는 이진트리
완전 이진트리 --> 마지막 레벨 직전까지 꽉채웠고왼쪽부터 채워진것
힙은 완전 이진트리구조를 가져야한다.
5. 힙의 조건
1, 완전이진트리
2. 힙특성 : 모든 노드는 값을 갖고, 자식노드들 값보다 크거나 같다.
반응형