반응형 힙1 우선순위 큐와 힙은 뭘까? 23.1 도입 우선순위 큐 선입선출이 아니고, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다. 연결 리스트나 동적 배열로 구현 가능하다 O(n) 시간 소요되며 비효율적이다. 힙을 통해 구현하는 것이 가장 적합하다. 힙 가장 큰 또는 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리 O(lgN) 시간 소요 23.2 힙의 정의와 구현 특정한 규칙을 만족하는 이진 트리 대소 관계 규칙: 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다. 힙의 모양 규칙 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있어야 한다. 배열을 이용한 힙의 구현 트리에 포함된 노드의 개수만 알면 트리 전체의 구조를 알 수 있다. 배열을 제일.. 2024. 4. 17. 이전 1 다음 728x90 반응형