[자료구조#9] 힢

우선순위 큐

큐 : 먼저 들어간 데이터가 먼저 삭제되는 자료구조

우선순위 큐

- 대기 리스트에서 항상 우선순위가 높은 순대로 먼저 서비스를 받는 구조

- 순서와 상관없이 대기리스트에서 우선순위가 높은 순으로

 

 

 

 

힢

부모-자식 노드 사이에 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높음

최소 힢 : 루트가 전체 노드 중에서 최소값인 힙	최대 힢 : 루트가 최대값을 가짐
트리의 모든 노드가 자식 노드보다 작은 값을 가짐 트리의 레벨에 따라 데이터가 순서를 갖지는 않음 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐	트리의 모든 노드가 자식 노드보다 큰 값을 가짐 트리의 레벨에 따라 데이터가 순서를 갖지는 않음 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음 루트가 가장 작은 값을 갖고 부모는 자식보다 큰 값을 가짐

 

힢 노드의 삭제 및 삽입

힢 구현을 위한 자료구조

배열을 이용한 힙의 구현 : 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음

연결 리스트보다 실행 속도 면에서 효율적

기억장소 측면에서도 장점을 가짐

 

힙에서 삭제 (루트에서 삭제)

 

---

 

	정답 4