자료구조 (2) 썸네일형 리스트형 힙 정렬 Heap - 큰 키에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조. - 한 노드가 최대 두 개의 자식노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전 이진 트리를 기본으로 함. Heap 이 되기 위한 조건 1. 구조 조건 - 완전 이진 트리 2. 순서 조건 - Partial Order, 값의 순서가 직계 관계(부모-자식)에서만 성립. 이진 탐색 트리와의 비교 - 힙은 각 자식 < 부모. (최대 힙 트리라 가정.) - 이진 탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식. 따라서, 힙은 우선순위 정렬에, 이진 탐색 트리는 탐색에 강점을 지닌 자료구조. def heapify(unsorted, index, heap_size) : larg.. 우선순위 큐 (priority queue), 힙 정렬 (heap sort) 우선순위 큐 (priority queue)- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다.- 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다. 배열을 사용하는 방법 1. 정렬이 안 되어 있는 배열의 경우삽입 시간 복잡도 \(O(1)\)삭제 시간 복잡도 \(O(n)\) 2. 정렬이 되어 있는 배열의 경우삽입 시간 복잡도 \(O(n)\)삭제 시간 복잡도 \(O(1)\) 연결 리스트를 사용하는 방법 1. 정렬이 안된 리스트- 삽입 시에 첫번째 노드로 삽입시키는 것이 유리하다. 다른 노드를 이동할 필요가 없다. 포인터만 변경하면 된다. 삽입 시간 복잡도 \(O(1)\)- 삭제 시에 포인터를 따라서 모든 노드를 뒤져보아야 한다. 삭제.. 이전 1 다음
