PostAddsense


태그 : heapsort 요약보기전체보기목록닫기

1

6 Problems

Problems6-1 Building a heap using insertionWe can build a heap by repeatedly calling MAX-HEAP-INSERT to insert the elements into the heap. Consider the following variation on the BUILD-MAX-HEAP proc...

6.5 Priority queues

Summary우선순위 큐(Priority queues)는 힙과 마찬가지로 두 가지 형태로 나타난다. 최대우선순위(max-priority queue)와 최소우선순위(min-priority queue). 이것들은 차례로 최대힙(max-heap)을 기반으로 한다. 우선순위 큐는 집합 S의 요소를 유지하는 자료 구조이며, 각 요소는 키(key)라고 불...

6.4 The heapsort algorithm

SummaryHEAPSORT(A)BUILD-MAX-HEAP(A)for i = A.length downto 2 exchange A[1] with A[i] A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A,1)실행시간 : O(n lg n) ⇒ The call to BUILD-MAX-HEAP takes time...

6.3 Building a heap

SummaryBUILD-MAX-HEAP(A)A.heap-size = A.lengthfor i = ⌊A.length/2⌋ downto 1 MAX-HEAPIFY(A,i)Figure 6.3 The operation of BUILD-MAX-HEAP, showing the data structure before the call toMAX-HEAPIF...

6.1 Heaps

SummaryHeapsort(binary) heap 자료구조는 거의 완전한 이진트리로 볼 수 있는 배열 객체이다. (그림 6.1)실행 시간: O(n lg n)정렬 방식: in-place ( 새로운 배열의 공간 할당 없이 배열 내에서 정렬되는 방식)설계 기술1. heap data structure2. priority queue그림 6.1 (a) 이진 트리...
1